Bungmint

nikgaevoy ORZ

Jul 28th, 2021 (edited)
131
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 5.83 KB | None | 0 0
  1. // Problem: D. LWDB
  2. // Contest: Codeforces - 2015 ICL, Finals, Div. 1
  3. // URL: https://codeforces.com/gym/100633/problem/D
  4. // Memory Limit: 256 MB
  5. // Time Limit: 3000 ms
  6. //
  7. // Powered by CP Editor (https://cpeditor.org)
  8.  
  9. #pragma GCC optimize("O3")
  10. #pragma GCC target("sse4")
  11. #include <bits/stdc++.h>
  12. using namespace std;
  13.  
  14. using ll = long long;
  15. using vi = vector<int>;
  16. using pi = pair<int, int>;
  17. using vpi = vector<pair<int, int>>;
  18. using pl = pair<ll, ll>;
  19. using vl = vector<ll>;
  20. using vpl = vector<pl>;
  21. using ld = long double;
  22.  
  23. #define all(v) (v).begin(), (v).end()
  24. #define ar array
  25. #define pb push_back
  26. #define sz(x) (int)(x).size()
  27. #define fi first
  28. #define se second
  29. #define lb lower_bound
  30. #define ub upper_bound
  31.  
  32. const int INF = 1e9;
  33. const ll LINF = 1e18;
  34. const int MOD = 1e9 + 7; //998244353;
  35. const ld PI = acos((ld)-1.0);
  36. const int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
  37. mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
  38. template <typename T>
  39. using pqg = priority_queue<T, vector<T>, greater<T>>;
  40. template <typename T>
  41. bool ckmin(T &a, const T &b) { return b < a ? a = b, 1 : 0; }
  42. template <typename T>
  43. bool ckmax(T &a, const T &b) { return b > a ? a = b, 1 : 0; }
  44.  
  45. template <typename A, typename B>
  46. ostream &operator<<(ostream &os, const pair<A, B> &p)
  47. {
  48.     return os << '(' << p.first << ", " << p.second << ')';
  49. }
  50. template <typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type>
  51. ostream &operator<<(ostream &os, const T_container &v)
  52. {
  53.     os << '{';
  54.     string sep;
  55.     for (const T &x : v)
  56.         os << sep << x, sep = ", ";
  57.     return os << '}';
  58. }
  59. void dbg_out()
  60. {
  61.     cerr << endl;
  62. }
  63. template <typename Head, typename... Tail>
  64. void dbg_out(Head H, Tail... T)
  65. {
  66.     cerr << ' ' << H;
  67.     dbg_out(T...);
  68. }
  69. #ifdef LOCAL
  70. #define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
  71. #else
  72. #define dbg(...)
  73. #endif
  74.  
  75. struct chash
  76. {
  77.     static uint64_t splitmix64(uint64_t x)
  78.     {
  79.         x += 0x9e3779b97f4a7c15;
  80.         x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
  81.         x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
  82.         return x ^ (x >> 31);
  83.     }
  84.  
  85.     size_t operator()(uint64_t x) const
  86.     {
  87.         static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
  88.         return splitmix64(x + FIXED_RANDOM);
  89.     }
  90. };
  91.  
  92. void setIO(string s)
  93. {
  94.     freopen((s + ".in").c_str(), "r", stdin);
  95.     freopen((s + ".out").c_str(), "w", stdout);
  96. }
  97.  
  98. //WeakestTopology ORZ (From his solution to 342E) https://codeforces.com/contest/342/submission/90467624
  99. //1-indexing
  100. struct CentroidDecomposition
  101. {
  102.     const vector<vpi>& E;
  103.     vi par, subsz, level;
  104.     vector<int> vis;
  105.     vector<vi> dist, child;
  106.     int dfs(int u, int p, int h, int W)
  107.     {
  108.         if (h != -1) dist[u][h] = dist[p][h] + W;
  109.         subsz[u] = 1;
  110.         for (auto [v, w] : E[u])
  111.             if (!vis[v] && v != p) subsz[u] += dfs(v, u, h, w);
  112.         return subsz[u];
  113.     }
  114.     int find_centroid(int u, int p, int sz)
  115.     {
  116.         for (auto [v,w] : E[u])
  117.             if (!vis[v] && v != p && subsz[v]*2 > sz)
  118.                 return find_centroid(v, u, sz);
  119.         return u;
  120.     }
  121.     void build(int u, int p, int w = 0)
  122.     {
  123.         int sz = dfs(u, p, p == -1 ? -1 : level[p], w);
  124.         int centroid = find_centroid(u, p, sz);
  125.         par[centroid] = p, vis[centroid] = 1;
  126.         if (p!=-1)child[p].pb(centroid);
  127.        
  128.         if (p != -1) level[centroid] = level[p] + 1;
  129.         for (auto [v,w] : E[centroid])
  130.             if (!vis[v]) build(v, centroid, w);
  131.     }
  132.     CentroidDecomposition(const vector<vpi>& E) : E(E)
  133.     {
  134.         int n = sz(E);
  135.         par.assign(n, -1LL), subsz.assign(n, 0LL), vis.assign(n, 0LL);
  136.         level.assign(n, 0LL), dist.assign(n, vector(31 - __builtin_clz(n), 0));
  137.         child.resize(n);
  138.         build(1, -1);
  139.     }
  140.     int operator[](int u) const { return par[u]; }
  141.     int lca(int u, int v) // centroid lca, not tree lca
  142.     {
  143.         if (level[u] < level[v]) swap(u, v);
  144.         while (level[u] > level[v]) u = par[u];
  145.         while (u != v) u = par[u], v = par[v];
  146.         return u;
  147.     }
  148.     int distance(int u, int v)
  149.     {
  150.         if (u==v) return 0;
  151.         int w = lca(u, v);
  152.         return dist[u][level[w]] + dist[v][level[w]];
  153.     }
  154. };
  155.  
  156. struct Query{
  157.     vector<ar<int,3>> vec;
  158. };
  159.  
  160. void solve()
  161. {
  162.     int n;
  163.     cin >> n;
  164.     vector<vpi> g(n+1);
  165.     for (int i=0;i<n-1;++i){
  166.         int u,v, w;
  167.         cin >> u >> v >> w;
  168.         g[u].pb({v,w}), g[v].pb({u,w});
  169.     }
  170.     CentroidDecomposition cd(g);
  171.     vector<Query> ans(n+1);
  172.     function<void(int, int, int, int)> pop = [&](int v, int d, int c, int time){
  173.         while(!ans[v].vec.empty()&&ans[v].vec.back()[0]<=d){
  174.             ans[v].vec.pop_back();
  175.         }
  176.         ans[v].vec.pb({d,c,time});
  177.     };
  178.     function<pi(int,int)> search = [&](int d, int u){
  179.         pi p = {-1,0};
  180.         int l = 0, r = sz(ans[u].vec)-1;
  181.         while(l<=r){
  182.             int m = l + (r-l)/2;
  183.             if (ans[u].vec[m][0]>=d){
  184.                 l = m+1, p.fi = ans[u].vec[m][2], p.se = ans[u].vec[m][1];
  185.             }else r = m-1;
  186.         }
  187.         return p;
  188.     };
  189.    
  190.     auto upd = [&](int v, int d, int c, int time){
  191.         pop(v, d,c, time);
  192.         for (int u = cd[v];u!=-1;u=cd[u]){
  193.             pop(u, d-cd.distance(u,v),c, time);
  194.         }
  195.     };
  196.     auto query = [&](int v){
  197.         pi p;
  198.         p = search(0, v);
  199.         for (int u=cd[v];u!=-1;u=cd[u]){
  200.             pi tmp = search(cd.distance(u,v), u);
  201.             if (ckmax(p.fi, tmp.fi)){
  202.                 p = tmp;
  203.             }
  204.         }
  205.         return p.se;
  206.     };
  207.     int q;
  208.     cin >> q;
  209.     for (int i=0;i<q;++i){
  210.         int op, v;
  211.         cin >> op>> v;
  212.         if (op==1){
  213.             int d, c;
  214.             cin >> d >> c;
  215.             upd(v,d, c,i);
  216.         }else{
  217.             cout << query(v)<<"\n";
  218.         }
  219.     }
  220. }
  221.  
  222. int main()
  223. {
  224.     ios_base::sync_with_stdio(false);
  225.     cin.tie(NULL);
  226.     int testcase=1;
  227.     // cin >> testcase;
  228.     while (testcase--)
  229.     {
  230.         solve();
  231.     }
  232. }
Add Comment
Please, Sign In to add comment