fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <cmath>
  5. #include <map>
  6. #include <numeric>
  7.  
  8. using namespace std;
  9.  
  10. #define MAX 1000100
  11.  
  12. vector<int> adj[MAX];
  13. int cnt[MAX]; 
  14. char res[MAX]; 
  15. int n; 
  16.  
  17. void dfsPrepare(int u, int par) {
  18.     cnt[u] = 1;
  19.     for (int v : adj[u]) {
  20.         if (v != par) {
  21.             dfsPrepare(v, u);
  22.             cnt[u] += cnt[v];
  23.         }
  24.     }
  25. }
  26.  
  27. void dfsTrace(int u, int par, char c) {
  28.     res[u] = c;
  29.     for (int v : adj[u]) {
  30.         if (v != par) {
  31.             dfsTrace(v, u, c);
  32.         }
  33.     }
  34. }
  35.  
  36. bool canSplit(int r) {
  37.     vector<pair<int, int>> values; 
  38.     int max_limit = n / 2;
  39.  
  40.     for (int c : adj[r]) {
  41.         int branch_size;
  42.  
  43.         if (cnt[c] < cnt[r]) {
  44.             branch_size = cnt[c];
  45.         } 
  46.         else {
  47.             branch_size = n - cnt[r];
  48.         }
  49.  
  50.         if (branch_size > max_limit) return false;
  51.  
  52.         values.push_back({branch_size, c});
  53.     }
  54.  
  55.     // 1. Sắp xếp giảm dần (Tham lam: Xử lý nhánh lớn trước)
  56.     sort(values.begin(), values.end(), greater<pair<int, int>>());
  57.  
  58.     int sum[3] = {0, 0, 0};
  59.     pair<int, int> p[3]; // {sum, index}
  60.  
  61.     // 2. Thực hiện chia tham lam (Ưu tiên nhóm CÓ TỔNG NHỎ NHẤT)
  62.     for (const auto& x : values) {
  63.         int branch_size = x.first;
  64.         int branch_root_node = x.second;
  65.  
  66.         for (int i = 0; i < 3; ++i) {
  67.             p[i] = {sum[i], i};
  68.         }
  69.         // Sắp xếp TĂNG DẦN theo tổng hiện tại (Ưu tiên nhóm NHỎ NHẤT để giữ cân bằng)
  70.         sort(p, p + 3); 
  71.  
  72.         bool assigned = false;
  73.  
  74.         // Duyệt từ nhóm nhỏ nhất đến lớn nhất
  75.         for (int i = 0; i < 3; ++i) {
  76.             int j = p[i].second;
  77.  
  78.             if (sum[j] + branch_size <= max_limit) {
  79.                 sum[j] += branch_size;
  80.                 res[branch_root_node] = '1' + j; 
  81.                 assigned = true;
  82.                 break; 
  83.             }
  84.         }
  85.  
  86.         if (!assigned) {
  87.             return false;
  88.         }
  89.     }
  90.  
  91.     return true;
  92. }
  93.  
  94. int main() {
  95.     ios_base::sync_with_stdio(false);
  96.     cin.tie(NULL);
  97.  
  98.     if (!(cin >> n)) return 0;
  99.  
  100.     if (n == 1) {
  101.         cout << "0\n";
  102.         return 0;
  103.     }
  104.  
  105.     for (int i = 0; i < n - 1; ++i) {
  106.         int u, v;
  107.         if (!(cin >> u >> v)) return 0;
  108.         adj[u].push_back(v);
  109.         adj[v].push_back(u);
  110.     }
  111.  
  112.     dfsPrepare(1, 0);
  113.  
  114.     for (int r = 1; r <= n; ++r) {
  115.         fill(res + 1, res + n + 1, 0); 
  116.  
  117.         if (canSplit(r)) {
  118.             res[r] = '0'; 
  119.  
  120.             for (int c : adj[r]) {
  121.                 dfsTrace(c, r, res[c]);
  122.             }
  123.  
  124.             res[n + 1] = '\0';
  125.             cout << (res + 1) << "\n";
  126.             return 0;
  127.         }
  128.     }
  129.  
  130.     cout << "-1\n"; 
  131.     return 0;
  132. }
  133.  
Success #stdin #stdout 0.01s 28464KB
comments (?)
stdin
copy 
3
1 2
1 3
stdout
copy 
021
https://ideone.com/EB7R0A
language:
C++14 (gcc 8.3)
created:
3 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!