Guest User

SecondThread GYM B WA 4

a guest
Aug 17th, 2020
438
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. #define ll long long
  3. #define pii pair<int,int>
  4. #define pll pair<ll,ll>
  5. #define pli pair<ll,int>
  6. #define pil pair<int,ll>
  7. #define fi first
  8. #define se second
  9. #define inf (INT_MAX/2-1)
  10. #define infl (1LL<<60)
  11. #define vi vector<int>
  12. #define vl vector<ll>
  13. #define pb push_back
  14. #define sz(a) (int)(a).size()
  15. #define all(a) begin(a),end(a)
  16. #define y0 y5656
  17. #define y1 y7878
  18. #define aaa system("pause");
  19. #define dbg(x) cerr<<(#x)<<": "<<(x)<<'\n',aaa
  20. #define dbga(x,n) cerr<<(#x)<<"[]: ";for(int _=0;_<n;_++)cerr<<x[_]<<' ';cerr<<'\n',aaa
  21. #define dbgs(x) cerr<<(#x)<<"[stl]: ";for(auto _:x)cerr<<_<<' ';cerr<<'\n',aaa
  22. #define dbgp(x) cerr<<(#x)<<": "<<x.fi<<' '<<x.se<<'\n',aaa
  23. #define maxn 300000
  24.  
  25. using namespace std;
  26.  
  27. vi g[maxn+5];
  28. int dep[maxn+5], dx[maxn+5], dy[maxn+5];
  29. int best, dm;
  30.  
  31. /**
  32. !!intotdeauna cel mai departat nod de 'a' intr-un arbore este un capat al diametrului(x/y)
  33. daca ar fi u != x, u != y cel mai departat nod de a => e ca si cum facem primul df
  34. pentru diametru, de unde rezulta ca si u ar fi un capat de diametru, mai bun decat x sau y!
  35. (pt ca e la distanta mai mare de u)
  36. deci daca rulam df(u) acum vom obtine alte capete de diametru (printre care si x/y)
  37. noul diametru e mai mare decat cele anterioare, pentru ca x/y erau mai apropriate de a,
  38. iar apelurile df(x) si df(y) ar da un rezultat mai prost decat df(u), mai departat de a
  39. deci avem doua capete legitime de diametru distincte ca lungime, contradictie
  40. **/
  41.  
  42. void df (int nod, int t) {
  43.   dep[nod] = 1 + dep[t];
  44.   if (dep[nod] > dm) {
  45.     dm = dep[nod];
  46.     best = nod;
  47.   }
  48.   for (int nn: g[nod])
  49.     if (nn != t) df(nn, nod);
  50. }
  51.  
  52. void bf (int nod, int d[]) {
  53.   queue<int> qu;
  54.   fill(d, d+maxn+1, inf);
  55.   d[nod] = 0;
  56.   qu.push(nod);
  57.   while (!qu.empty()) {
  58.     int now = qu.front();
  59.     qu.pop();
  60.     for (int nn: g[now])
  61.       if (d[nn] > 1+d[now]) {
  62.         d[nn] = 1 + d[now];
  63.         qu.push(nn);
  64.       }
  65.   }
  66. }
  67.  
  68. int main () {
  69.   ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
  70.   int n; cin >> n;
  71.   int i, j, z;
  72.   for (i = 0; i < n-1; i++) {
  73.     int a, b; cin >> a >> b;
  74.     g[a].pb(b);
  75.     g[b].pb(a);
  76.   }
  77.   df(1, 0);
  78.   dm = 0;
  79.   int x = best;
  80.   fill(all(dep), 0);
  81.   df(best, 0);
  82.   int y = best;
  83.   bf(x, dx);
  84.   bf(y, dy);
  85.   for (i = 1; i <= n; i++) cout << 1 + max(dx[i], dy[i]) << '\n';
  86.   return 0;
  87. }
RAW Paste Data