Advertisement
cs-mshah

Untitled

Jan 7th, 2022
564
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 6.63 KB | None | 0 0
  1. // Problem: Tree Stepping Game
  2. // Contest: HackerRank - FizzBuzz'22 Round1
  3. // URL: https://www.hackerrank.com/contests/fizzbuzz22-round1/challenges/tree-stepping-game-medium
  4. // Memory Limit: 512 MB
  5. // Time Limit: 4000 ms
  6.  
  7. /*
  8.  
  9. WINNERS NEVER QUIT AND QUITTERS NEVER WIN!!
  10.  
  11. Falling down is an accident, Staying down is a choice.
  12.  
  13. */
  14. #pragma GCC optimize("O3,unroll-loops")
  15. #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
  16.  
  17. #include "bits/stdc++.h"
  18. /*#include <ext/pb_ds/assoc_container.hpp>
  19. #include <ext/pb_ds/tree_policy.hpp>*/
  20.  
  21. using namespace std;
  22. //using namespace __gnu_pbds;
  23.  
  24. typedef long long ll;
  25. typedef long double ld;
  26. typedef pair<ll,ll> pll;
  27. typedef vector<bool> vb;
  28. typedef vector<int> vi;
  29. typedef vector<ll> vll;
  30. typedef vector<vi> vvi;
  31. typedef vector<vb> vvb;
  32. typedef vector<vll> vvll;
  33. typedef vector<pll> vpll;
  34. typedef vector<string> vs;
  35. typedef unordered_map<ll,ll> umll;
  36. template<class T> using pq = priority_queue<T, vector<T>, greater<T>>;
  37. /*template <typename num_t>
  38. using ordered_set = tree<num_t, null_type, less<num_t>, rb_tree_tag, tree_order_statistics_node_update>;*/
  39. // find_by_order(k): iterator to the kth largest(0 indexed). order_of_key(k): no. of items < k
  40.  
  41. #define GET_MACRO(_1,_2,_3,_4,NAME,...) NAME
  42. #define FOR3(i,a,b) for(long long i=a;i<b;i++)
  43. #define FOR4(i,a,b,step) for(long long i=a;i<b;i=i+step)
  44. #define REV3(i,a,b) for(long long i=a;i>=b;i--)
  45. #define REV4(i,a,b,step) for(long long i=a;i>=b;i=i-step)
  46. #define FOR(...) GET_MACRO(__VA_ARGS__, FOR4, FOR3)(__VA_ARGS__)
  47. #define REV(...) GET_MACRO(__VA_ARGS__, REV4, REV3)(__VA_ARGS__)
  48. #define F first
  49. #define S second
  50. #define pb push_back
  51. #define ub upper_bound
  52. #define lb lower_bound
  53. #define all(v) v.begin(),v.end()
  54. #define rall(v) v.rbegin(),v.rend()
  55. #define tc ll tests;cin>>tests;while(tests--)
  56. #define io ios_base::sync_with_stdio(false);cin.tie(nullptr);
  57. #define coutv(v) for(auto it: (v))cout<<it<<" ";newl;
  58. #define cout2d(v) for(auto it: (v)) {for(auto j:it) cout<<j<<" ";newl;}
  59. #define cinv(v,n) vll (v)(n);FOR(i,0,(n)){cin>>v[i];}
  60. #define cinvg(v,n) (v).resize(n);FOR(i,0,(n)){cin>>v[i];}
  61. #define cin2d(v,n,m) vvll (v)(n,vll(m,0));FOR(i,0,n){FOR(j,0,m){cin>>v[i][j];}}
  62. #define cin2dg(v,n,m) (v).resize(n,vll(m));FOR(i,0,n){FOR(j,0,m){cin>>v[i][j];}}
  63. #define pyes(CONDITION) cout << (CONDITION ? "YES" : "NO") << '\n';
  64. #define newl cout<<"\n"
  65. #define MOD 1000000007
  66. #define INF LLONG_MAX/2
  67. #define m1(x) template<class T, class... U> void x(T&& a, U&&... b)
  68. #define m2(x) (int[]){(x forward<U>(b),0)...}
  69. m1(pr) { cout << forward<T>(a);  m2(cout << " " <<); cout << "\n"; }
  70. m1(re) { cin >> forward<T>(a); m2(cin >>); }
  71. template <class ...Args>
  72. auto &readd(Args &...args) { return (cin >> ... >> args); }
  73. #define re(...) __VA_ARGS__; readd(__VA_ARGS__)
  74.  
  75. const ll dx[4] = {0,1,0,-1}, dy[4] = {1,0,-1,0};
  76. // const ll dx[8] = {-2,-1,1,2,2,1,-1,-2}, dy[8] = {1,2,2,1,-1,-2,-2,-1}; //knight moves
  77.  
  78. // ************************DEBUG START********************************
  79. // #ifndef ONLINE_JUDGE
  80. // //#define cerr cout
  81. // #include "myprettyprint.hpp"
  82. // #else
  83. // #define dbg(...)
  84. // #endif
  85. // ************************DEBUG END**********************************
  86.  
  87. constexpr ll pct(ll x) { return __builtin_popcountll(x); } // # of bits set
  88. constexpr ll bits(ll x) {return x == 0LL ? 0LL : 63LL-__builtin_clzll(x); } // floor(log2(x))
  89. constexpr ll p2(ll x) { return 1LL<<x; }
  90. constexpr ll msk2(ll x) { return p2(x)-1LL; }
  91. mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
  92.  
  93. struct centroid
  94. {
  95.     const ll LOGN = 20;
  96.     ll n;
  97.     vvll g;
  98.     vb vis; //denotes deleted nodes
  99.     vll par, sz;
  100.    
  101.     void init(ll N)
  102.     {
  103.         n = N;
  104.         g.resize(n);
  105.         vis.resize(n, false);
  106.         par.resize(n);
  107.         sz.resize(n);
  108.     }
  109.  
  110.     void edge(ll a, ll b)
  111.     {
  112.         g[a].push_back(b);
  113.         g[b].push_back(a);
  114.     }
  115.  
  116.     ll find_size(ll v, ll p = -1)
  117.     {
  118.         if (vis[v]) return 0;
  119.         sz[v] = 1;
  120.         for (ll x: g[v])
  121.         {
  122.             if (x == p) continue;
  123.            
  124.             sz[v] += find_size(x, v);
  125.         }
  126.         return sz[v];
  127.     }
  128.  
  129.     ll find_centroid(ll v, ll p, ll n)
  130.     {
  131.         for (ll x: g[v])
  132.         {
  133.             if (x == p) continue;
  134.             if (!vis[x] && sz[x] > n / 2)
  135.             {
  136.                 return find_centroid(x, v, n);
  137.             }
  138.         }
  139.         return v;
  140.     }
  141.  
  142.     void init_centroid(ll v = 0, ll p = -1)
  143.     {
  144.         find_size(v);
  145.  
  146.         ll c = find_centroid(v, -1, sz[v]);
  147.         vis[c] = true;
  148.         par[c] = p;
  149.        
  150.         // process O(N) paths from centroid to all nodes in its subtree here
  151.  
  152.         // find centroids for the subtrees and make them children of current c.
  153.         for (ll x: g[c])
  154.         {
  155.             if (!vis[x])
  156.             {
  157.                 init_centroid(x, c);
  158.             }
  159.         }
  160.     }
  161. };
  162.  
  163. struct LCA
  164. {
  165.     ll n, LOG, timer = 0;
  166.     vvll g, up;
  167.     vll tin, tout;
  168.     vll lev;
  169.    
  170.     void init(ll x)
  171.     {
  172.         n=x;
  173.         timer=0;
  174.         LOG = ceil(log2(n));
  175.         g.resize(n);
  176.         up.resize(n, vll(LOG+1));
  177.         tin.assign(n,0);
  178.         tout.assign(n,0);
  179.         lev.assign(n,0);
  180.     }
  181.    
  182.     void edge(ll a, ll b)
  183.     {
  184.         g[a].push_back(b);
  185.         g[b].push_back(a);
  186.     }
  187.    
  188.     void dfs(ll u = 0, ll p = 0)
  189.     {
  190.         tin[u]=timer++;
  191.         up[u][0] = p;
  192.         FOR(i,1,LOG+1)
  193.         {
  194.             up[u][i] = up[up[u][i-1]][i-1];
  195.         }
  196.         for(auto v:g[u])
  197.         {
  198.             if(p==v) continue;
  199.             lev[v] = lev[u] + 1;
  200.             dfs(v,u);
  201.         }
  202.         tout[u]=timer++;
  203.     }
  204.    
  205.     bool is_ancestor(ll u, ll v)
  206.     {
  207.         return tin[u]<=tin[v] && tout[u]>=tout[v];
  208.     }
  209.    
  210.     ll lca(ll u, ll v)
  211.     {
  212.         if(is_ancestor(u,v)) return u;
  213.         if(is_ancestor(v,u)) return v;
  214.         REV(i,LOG,0)
  215.         {
  216.             if(!is_ancestor(up[u][i], v)) u = up[u][i];
  217.         }
  218.         return up[u][0];
  219.     }
  220.     ll dist(ll a, ll b)
  221.     {
  222.         ll l=lca(a,b);
  223.         return lev[a]+lev[b]-2*lev[l];
  224.     }
  225.  
  226.     ll lift(ll u, ll d)
  227.     {
  228.         while(d>0)
  229.         {
  230.             ll raise=log2(d);
  231.             u=up[u][raise];
  232.             d-=(1LL<<raise);
  233.         }
  234.         return u;
  235.     }
  236. };
  237.  
  238. vll best, mark;
  239.  
  240. void paint(ll u, LCA &lca, centroid &cd)
  241. {
  242.     ll v=u;
  243.     while(v!=-1)
  244.     {
  245.         //best[v]=min(best[v], lca.dist(u,v));
  246.         ll upd = lca.dist(u,v);
  247.         if(upd<best[v])
  248.         {
  249.             mark[v] = u;
  250.             best[v] = upd;
  251.         }
  252.         else if(upd==best[v] && mark[v]>u)
  253.         {
  254.             mark[v] = u;
  255.         }
  256.         v=cd.par[v];
  257.     }
  258. }
  259.  
  260. void test()
  261. {
  262.     ll re(n);
  263.     centroid cd;
  264.     LCA lca;
  265.     cd.init(n);
  266.     lca.init(n);
  267.     for(ll i=0;i<n-1;i++)
  268.     {
  269.         ll u, v;
  270.         cin>>u>>v;
  271.         u--;v--;
  272.         cd.edge(u,v);
  273.         lca.edge(u,v);
  274.     }
  275.     cd.init_centroid();
  276.     lca.dfs();
  277.     best.assign(n, INF);
  278.     mark.assign(n, -1);
  279.     tc
  280.     {
  281.         ll re(u);
  282.         u--;
  283.         if(best[u]==INF)
  284.         {
  285.             pr("NO");
  286.         }
  287.         else
  288.         {
  289.             pr("YES", mark[u]+1);
  290.         }
  291.         paint(u, lca, cd);
  292.     }
  293. }
  294.  
  295. int main()
  296. {
  297.     io;
  298.     ll tests=1;
  299.     cin>>tests;
  300.     while(tests--)
  301.     {
  302.         test();
  303.     }
  304.     return 0;
  305. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement