oj.uz

Submission #609143

# Submission time Handle Problem Language Result Execution time Memory
609143 2022-07-27T12:27:03 Z MohammadAghil Dynamic Diameter (CEOI19_diameter) C++17
31 / 100
 5000 ms 353116 KB 
      #include <bits/stdc++.h>
  #pragma GCC optimize ("Ofast,unroll-loops")
#pragma GCC target ("avx2")
    using namespace std;
  typedef long long ll;
   typedef pair<ll, int> pp;
    #define er(args ...) cerr << __LINE__ << ": ", err(new istringstream(string(#args)), args), cerr << endl
      #define per(i,r,l) for(int i = (r); i >= (l); i--)
        #define rep(i,l,r) for(int i = (l); i < (r); i++)
           #define all(x) begin(x), end(x)
              #define sz(x) (int)(x).size()
                  #define pb push_back
                      #define ss second
                           #define ff first
                                   void err(istringstream *iss){}template<typename T,typename ...Args> void err(istringstream *iss,const T &_val, const Args&...args){string _name;*iss>>_name;if(_name.back()==',')_name.pop_back();cerr<<_name<<" = "<<_val<<", ",err(iss,args...);}
void IOS(){
     cin.tie(0) -> sync_with_stdio(0);
     // #ifndef ONLINE_JUDGE
     //      freopen("in.in", "r", stdin);
     //      freopen("out.out", "w", stdout);
     // #endif
}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const ll mod = 1e9 + 7, maxn = 1e5 + 5, lg = 22, inf = ll(1e18) + 5;
ll pw(ll a,ll b,ll md=mod){if(!b)return 1;ll k=pw(a,b>>1ll);return k*k%md*(b&1ll?a:1)%md;}

struct Segment{
     vector<ll> laz, seg;
     int n;
     Segment(){}
     Segment(vector<ll> a): n(sz(a)){
          laz.assign(n<<2, 0), seg.assign(n<<2, 0);
          build(1, 0, n, a);
     }
     void build(int x, int lx, int rx, vector<ll>& a){
          if(lx + 1 == rx){
               seg[x] = a[lx];
               return;
          }
          int mid = (lx + rx)>>1;
          build(x<<1, lx, mid, a), build(x<<1|1, mid, rx, a);
          seg[x] = max(seg[x<<1], seg[x<<1|1]);
     }
     void updNode(int x, ll k){
          seg[x] += k, laz[x] += k;
     }
     void shift(int x){
          if(laz[x]){
               updNode(x<<1, laz[x]);
               updNode(x<<1|1, laz[x]);
               laz[x] = 0;
          }
     }
     void upd(int l, int r, ll k, int x, int lx, int rx){
          if(l <= lx && r >= rx){
               updNode(x, k);
               return;
          } 
          shift(x);
          int mid = (lx + rx)>>1;
          if(l < mid) upd(l, r, k, x<<1, lx, mid);
          if(mid < r) upd(l, r, k, x<<1|1, mid, rx);
          seg[x] = max(seg[x<<1], seg[x<<1|1]);
     }
     void upd(int l, int r, ll k){ upd(l, r, k, 1, 0, n); }
     ll get(int l, int r, int x, int lx, int rx){
          if(l <= lx && r >= rx) return seg[x];
          shift(x);
          int mid = (lx + rx)>>1;
          ll res = 0;
          if(l < mid) res = get(l, r, x<<1, lx, mid);
          if(mid < r) res = max(res, get(l, r, x<<1|1, mid, rx));
          return res;
     }
     ll get(int l, int r){ return get(l, r, 1, 0, n); }
} seg[maxn];

int cnt[maxn], par[maxn];
vector<pair<int, ll>> adj[maxn];
map<int, int> st[maxn], en[maxn], id[maxn]; int t;
bool ban[maxn];
set<pp> mx[maxn];

#define chk (c-p&&ban[c]^1)

void dfs(int r, int p){
     cnt[r] = 1;
     for(auto[c, d]: adj[r]) if(chk){
          dfs(c, r);
          cnt[r] += cnt[c];
     }
}

int find_center(int r, int p, int tot){
     for(auto[c, d]: adj[r]) if(chk && (cnt[c]<<1) > tot) return find_center(c, r, tot);
     return r;
}

vector<ll> tmp;
void dfs2(int r, int p, int cen, ll dist, int ref){
     if(p == cen) ref = r;
     id[cen][r] = ref;
     tmp.pb(dist);
     st[cen][r] = t++;
     for(auto[c, d]: adj[r]) if(chk) dfs2(c, r, cen, dist + d, ref);
     en[cen][r] = t;
}

void reset(int r){
     ban[r] = true;
     t = 0;
     tmp.clear();
}

void dec(int r, int p = -1){
     dfs(r, -1);
     r = find_center(r, -1, cnt[r]);
     par[r] = p;
     dfs2(r, -1, r, 0, r);
     seg[r] = Segment(tmp);
     reset(r);
     for(auto[c, d]: adj[r]) if(ban[c]^1) {
          dec(c, r), mx[r].insert({seg[r].get(st[r][c], en[r][c]), c});
     }
}

set<pp> ans;
ll get_ans(){
     return prev(end(ans))->ff;
}

ll get(int r){
     if(sz(mx[r]) < 1) return 0;
     if(sz(mx[r]) == 1) return begin(mx[r])->ff;
     return prev(end(mx[r]))->ff + prev(prev(end(mx[r])))->ff;
}

void upd(int u, int v, ll delta){
     auto lis = [&](int u){
          vector<int> res;
          while(u + 1) res.pb(u), u = par[u];
          return res;
     };
     vector<int> lsu = lis(u), lsv = lis(v);
     reverse(all(lsu)), reverse(all(lsv));
     vector<int> cand;
     rep(i,0,min(sz(lsu), sz(lsv))){
          if(lsu[i] - lsv[i]) break;
          cand.pb(lsu[i]); 
     }
     for(int r: cand){
          if(st[r][u] > st[r][v]) swap(u, v);
          int ref = id[r][v];
          
          ans.erase(pp(get(r), r));
          mx[r].erase(pp(seg[r].get(st[r][ref], en[r][ref]), ref));

          seg[r].upd(st[r][v], en[r][v], delta);

          mx[r].insert({seg[r].get(st[r][ref], en[r][ref]), ref});
          ans.insert(pp(get(r), r));
     }
}


pp edge[maxn];
ll vl[maxn];
int main(){ IOS();
     int n, q; cin >> n >> q;
     ll W; cin >> W;
     rep(i,0,n-1){
          int u, v; cin >> u >> v; u--, v--; 
          ll w; cin >> w;
          adj[u].pb({v, w}), adj[v].pb({u, w});
          edge[i] = {u, v}, vl[i] = w;
     } 
     
     dec(0);
     rep(i,0,n) ans.insert({get(i), i});

     ll lst = 0;
     while(q--){
          ll d, e; cin >> d >> e;
          d = (d + lst)%(n-1), e = (e + lst)%W;
          upd(edge[d].ff, edge[d].ss, e - vl[d]);
          vl[d] = e;
          cout << (lst = get_ans()) << '\n';
     }
     return 0; 
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 26964 KB Output is correct
2 Correct 14 ms 26900 KB Output is correct
3 Correct 18 ms 26956 KB Output is correct
4 Correct 16 ms 26960 KB Output is correct
5 Correct 16 ms 26964 KB Output is correct
6 Correct 15 ms 26916 KB Output is correct
7 Correct 16 ms 27004 KB Output is correct
8 Correct 15 ms 26964 KB Output is correct
9 Correct 14 ms 26960 KB Output is correct
10 Correct 15 ms 26908 KB Output is correct
11 Correct 13 ms 27024 KB Output is correct
12 Correct 15 ms 26952 KB Output is correct
13 Correct 16 ms 27064 KB Output is correct
14 Correct 16 ms 26964 KB Output is correct
15 Correct 14 ms 27032 KB Output is correct
16 Correct 14 ms 27028 KB Output is correct
17 Correct 17 ms 27092 KB Output is correct
18 Correct 16 ms 27092 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 26964 KB Output is correct
2 Correct 14 ms 26900 KB Output is correct
3 Correct 18 ms 26956 KB Output is correct
4 Correct 16 ms 26960 KB Output is correct
5 Correct 16 ms 26964 KB Output is correct
6 Correct 15 ms 26916 KB Output is correct
7 Correct 16 ms 27004 KB Output is correct
8 Correct 15 ms 26964 KB Output is correct
9 Correct 14 ms 26960 KB Output is correct
10 Correct 15 ms 26908 KB Output is correct
11 Correct 13 ms 27024 KB Output is correct
12 Correct 15 ms 26952 KB Output is correct
13 Correct 16 ms 27064 KB Output is correct
14 Correct 16 ms 26964 KB Output is correct
15 Correct 14 ms 27032 KB Output is correct
16 Correct 14 ms 27028 KB Output is correct
17 Correct 17 ms 27092 KB Output is correct
18 Correct 16 ms 27092 KB Output is correct
19 Correct 49 ms 28476 KB Output is correct
20 Correct 67 ms 28596 KB Output is correct
21 Correct 63 ms 28756 KB Output is correct
22 Correct 72 ms 29168 KB Output is correct
23 Correct 96 ms 35272 KB Output is correct
24 Correct 151 ms 37324 KB Output is correct
25 Correct 159 ms 38592 KB Output is correct
26 Correct 196 ms 40140 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 26880 KB Output is correct
2 Correct 14 ms 26880 KB Output is correct
3 Correct 17 ms 27004 KB Output is correct
4 Correct 35 ms 27220 KB Output is correct
5 Correct 100 ms 27504 KB Output is correct
6 Correct 15 ms 26964 KB Output is correct
7 Correct 17 ms 27220 KB Output is correct
8 Correct 17 ms 27168 KB Output is correct
9 Correct 22 ms 27336 KB Output is correct
10 Correct 44 ms 27408 KB Output is correct
11 Correct 168 ms 27876 KB Output is correct
12 Correct 23 ms 30296 KB Output is correct
13 Correct 23 ms 30300 KB Output is correct
14 Correct 30 ms 30284 KB Output is correct
15 Correct 90 ms 30412 KB Output is correct
16 Correct 283 ms 30792 KB Output is correct
17 Correct 268 ms 92116 KB Output is correct
18 Correct 323 ms 92084 KB Output is correct
19 Correct 294 ms 92156 KB Output is correct
20 Correct 371 ms 92184 KB Output is correct
21 Correct 833 ms 92740 KB Output is correct

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 28896 KB Output is correct
2 Correct 78 ms 29004 KB Output is correct
3 Correct 302 ms 29316 KB Output is correct
4 Correct 572 ms 29480 KB Output is correct
5 Correct 117 ms 52764 KB Output is correct
6 Correct 206 ms 52860 KB Output is correct
7 Correct 711 ms 53240 KB Output is correct
8 Correct 1293 ms 53520 KB Output is correct
9 Correct 599 ms 179856 KB Output is correct
10 Correct 770 ms 179716 KB Output is correct
11 Correct 1649 ms 180036 KB Output is correct
12 Correct 3148 ms 180232 KB Output is correct
13 Correct 1303 ms 352548 KB Output is correct
14 Correct 1537 ms 352592 KB Output is correct
15 Correct 2494 ms 352852 KB Output is correct
16 Correct 4366 ms 353104 KB Output is correct
17 Execution timed out 5109 ms 353116 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #5
0 / 24.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5074 ms 273992 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 26964 KB Output is correct
2 Correct 14 ms 26900 KB Output is correct
3 Correct 18 ms 26956 KB Output is correct
4 Correct 16 ms 26960 KB Output is correct
5 Correct 16 ms 26964 KB Output is correct
6 Correct 15 ms 26916 KB Output is correct
7 Correct 16 ms 27004 KB Output is correct
8 Correct 15 ms 26964 KB Output is correct
9 Correct 14 ms 26960 KB Output is correct
10 Correct 15 ms 26908 KB Output is correct
11 Correct 13 ms 27024 KB Output is correct
12 Correct 15 ms 26952 KB Output is correct
13 Correct 16 ms 27064 KB Output is correct
14 Correct 16 ms 26964 KB Output is correct
15 Correct 14 ms 27032 KB Output is correct
16 Correct 14 ms 27028 KB Output is correct
17 Correct 17 ms 27092 KB Output is correct
18 Correct 16 ms 27092 KB Output is correct
19 Correct 49 ms 28476 KB Output is correct
20 Correct 67 ms 28596 KB Output is correct
21 Correct 63 ms 28756 KB Output is correct
22 Correct 72 ms 29168 KB Output is correct
23 Correct 96 ms 35272 KB Output is correct
24 Correct 151 ms 37324 KB Output is correct
25 Correct 159 ms 38592 KB Output is correct
26 Correct 196 ms 40140 KB Output is correct
27 Correct 14 ms 26880 KB Output is correct
28 Correct 14 ms 26880 KB Output is correct
29 Correct 17 ms 27004 KB Output is correct
30 Correct 35 ms 27220 KB Output is correct
31 Correct 100 ms 27504 KB Output is correct
32 Correct 15 ms 26964 KB Output is correct
33 Correct 17 ms 27220 KB Output is correct
34 Correct 17 ms 27168 KB Output is correct
35 Correct 22 ms 27336 KB Output is correct
36 Correct 44 ms 27408 KB Output is correct
37 Correct 168 ms 27876 KB Output is correct
38 Correct 23 ms 30296 KB Output is correct
39 Correct 23 ms 30300 KB Output is correct
40 Correct 30 ms 30284 KB Output is correct
41 Correct 90 ms 30412 KB Output is correct
42 Correct 283 ms 30792 KB Output is correct
43 Correct 268 ms 92116 KB Output is correct
44 Correct 323 ms 92084 KB Output is correct
45 Correct 294 ms 92156 KB Output is correct
46 Correct 371 ms 92184 KB Output is correct
47 Correct 833 ms 92740 KB Output is correct
48 Correct 27 ms 28896 KB Output is correct
49 Correct 78 ms 29004 KB Output is correct
50 Correct 302 ms 29316 KB Output is correct
51 Correct 572 ms 29480 KB Output is correct
52 Correct 117 ms 52764 KB Output is correct
53 Correct 206 ms 52860 KB Output is correct
54 Correct 711 ms 53240 KB Output is correct
55 Correct 1293 ms 53520 KB Output is correct
56 Correct 599 ms 179856 KB Output is correct
57 Correct 770 ms 179716 KB Output is correct
58 Correct 1649 ms 180036 KB Output is correct
59 Correct 3148 ms 180232 KB Output is correct
60 Correct 1303 ms 352548 KB Output is correct
61 Correct 1537 ms 352592 KB Output is correct
62 Correct 2494 ms 352852 KB Output is correct
63 Correct 4366 ms 353104 KB Output is correct
64 Execution timed out 5109 ms 353116 KB Time limit exceeded
65 Halted 0 ms 0 KB -