fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. typedef unsigned long long ull;
  5. using ld = long double;
  6. #define Youssef() ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
  7. #define endl "\n"
  8. #define unmap unordered_map
  9. #define all(x) x.begin(), x.end()
  10. #define rall(x) x.rbegin(), x.rend()
  11. #define vi vector<int>
  12. #define vvi vector<vi>
  13. #define vll vector<ll>
  14. #define vvl vector<vll>
  15. #define pii pair<int, int>
  16. #define si(x) ll(x.size())
  17. #define For(i, j, n) for(ll i = j; i < n; i++)
  18. #define rFor(i, j, n) for(ll i = j; i >= n; i--)
  19. #define read(a) For(i, 0, si(a)) cin >> a[i];
  20. #define readd(a) For(i, 0, si(a)) For(j, 0, si(a[0])) cin >> a[i][j];
  21. #define print(a) For(j, 0, si(a)) cout << a[j] << (j < si(a)-1 ? " " : ""); cout << endl;
  22. #define fi first
  23. #define se second
  24. #define int ll
  25. const int dx[] = {0, 1, 0, -1, -1, 1, -1, 1};
  26. const int dy[] = {1, 0, -1, 0, 1, 1, -1, -1};
  27.  
  28. struct DSU{
  29.     vi parent;
  30.     vi size;
  31.     DSU(int n){parent.resize(n+2);size.assign(n+2,1);For(i,0,n+2)parent[i]=i;}
  32.     void set_union(int a, int b)
  33.     {
  34.         a = find(a);
  35.         b = find(b);
  36.         if(a == b) return;
  37.         if(size[a] < size[b]) swap(a, b);
  38.         parent[b] = a;
  39.         size[a] += size[b];
  40.     }
  41.     int find(int a)
  42.     {
  43.         if(parent[a] == a || parent[a] == 0) return a;
  44.         return parent[a] = find(parent[a]);
  45.     }
  46. };
  47.  
  48. int n, powers[1000000];
  49. vector<vector<pii>> adj;
  50. int subtree[1000000];
  51.  
  52. int dfs1(int node, int parent)
  53. {
  54.     int cnt = 0;
  55.     for(auto [v, w] : adj[node])
  56.     {
  57.         if(v == parent) continue;
  58.         cnt = 1 + dfs1(v, node);
  59.         subtree[node] += cnt;
  60.     }
  61.     return subtree[node];
  62. }
  63.  
  64. void dfs2(int node, int parent)
  65. {
  66.     for(auto [v, w] : adj[node])
  67.     {
  68.         if(v == parent) continue;
  69.         int t = subtree[v] + 1;
  70.         powers[w] = t * (n - t);
  71.         dfs2(v, node);
  72.     }
  73. }
  74.  
  75. signed main()
  76. {
  77.     Youssef();
  78.     // freopen("lineup.out", "w", stdout);
  79.     // freopen("lineup.in", "r", stdin);
  80.     int tt = 1;
  81.     // cin >> tt;
  82.     while (tt--)
  83.     {
  84.         int m; cin >> n >> m;
  85.         vector<array<int, 3>> a(m);
  86.         adj = vector<vector<pii>>(n+1);
  87.         For(i, 0, m)
  88.             cin >> a[i][1] >> a[i][2] >> a[i][0];
  89.         sort(all(a));
  90.         DSU dsu(n);
  91.         For(i, 0, m)
  92.         {
  93.             if(dsu.find(a[i][1]) != dsu.find(a[i][2]))
  94.             {
  95.                 dsu.set_union(a[i][1], a[i][2]);
  96.                 adj[a[i][1]].push_back({a[i][2], a[i][0]});
  97.                 adj[a[i][2]].push_back({a[i][1], a[i][0]});
  98.             }
  99.         }
  100.         dfs1(1, 1);
  101.         dfs2(1, 1);
  102.         int l = 0;
  103.         For(i, 0, 1e6-1)
  104.         {
  105.             powers[i+1] += powers[i] / 2;
  106.             powers[i] %= 2;
  107.             if(powers[i+1]) l = i+1;
  108.         }
  109.         rFor(i, l, 0) cout << powers[i];
  110.     }
  111. }
Success #stdin #stdout 0.02s 11612KB
comments (?)
stdin
copy 
5 6
1 3 5
4 5 0
2 1 3
3 2 1
4 3 4
4 2 2
stdout
copy 
1000100
https://ideone.com/qWImFF
problem : https://v...content-available-to-author-only...e.net/problem/HackerRank-johnland
language:
C++14 (clang 8.0)
created:
12 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!