oj.uz

Submission #697319

# Submission time Handle Problem Language Result Execution time Memory
697319 2023-02-09T08:42:30 Z NintsiChkhaidze Dynamic Diameter (CEOI19_diameter) C++17
73 / 100
 5000 ms 135848 KB 
#include <bits/stdc++.h>
#define ll long long
#define left (h<<1),l,((l+r)>>1)
#define right ((h<<1)|1),((l+r)>>1) + 1,r
#define pb push_back
#define pii pair<int,int>
#define s second
#define f first
using namespace std;

const int N = 100005,M=25; // ?
vector <pii> v[N];
vector <int> con[N];
multiset <ll> st[N],bigset;
ll value[N],wi[N];
int vis[N],xi[N],yi[N],comp[M],DP[N];
int n,centroid,CH,L;
int tin[M][N],tout[M][N],PAR[M][N],dep[M][N];
ll t[M][4*N],add[M][4*N];
multiset <ll> :: iterator it;

void push(int k,int h){
    if (!add[k][h]) return;
    add[k][h*2] += add[k][h];
    t[k][h*2] += add[k][h];
    add[k][h*2+1] += add[k][h];
    t[k][h*2+1] += add[k][h];
    add[k][h] = 0LL;
}
void upd(int k,int h,int l,int r,int L,int R,ll val){
    if (r < L || R < l) return;
    if (L <= l && r <= R){
        t[k][h] += val;
        add[k][h] += val;
        return;
    }
    push(k,h);
    upd(k,left,L,R,val);
    upd(k,right,L,R,val);
    t[k][h] = max(t[k][h*2],t[k][h*2+1]);
}

ll get(int k,int h,int l,int r,int L,int R){
    if (r < L || R < l) return 0LL;
    if (L <= l && r <= R) return t[k][h];
    push(k,h);
    return max(get(k,left,L,R),get(k,right,L,R));
}
int dfs(int x,int par,int root,int m){
    int s = 1;
    for (auto [to,idx]: v[x])
        if (to != par && !vis[to]) s += dfs(to,x,root, m);
    if (centroid == -1 && (x == root || s*2 >= m)) centroid = x;
    return s;
}

void DFS(int x,int par,int id,int cent){
    tin[id][x] = ++comp[id];
    PAR[id][x] = CH;

    for (auto [to,q]: v[x]){
        if (to == par || vis[to]) continue;

        con[q].pb(cent);
        dep[id][to] = dep[id][x] + 1; 
        if (dep[id][x] == 1) CH = to;

        DFS(to,x,id,cent);
        upd(id,1,1,n,tin[id][to],tout[id][to],+wi[q]);
    }

    tout[id][x] = comp[id];
}
void C(int x,int m,int lvl){
    centroid = -1;
    dfs(x, x, x, m);
    vis[centroid] = 1;

    L = max(L,lvl);
    DP[centroid] = lvl;
    dep[lvl][centroid] = 1;
    DFS(centroid,centroid,lvl,centroid);

    for (auto [to,idx]: v[centroid])
        if (!vis[to]) C(to,m/2,lvl + 1);
}
signed main(){
    ios_base::sync_with_stdio(0),cin.tie(NULL),cout.tie(NULL);
    
    int q; ll W;
    cin>>n>>q>>W;

    for (int i = 1; i < n; i++){
        cin>>xi[i]>>yi[i]>>wi[i];
        v[xi[i]].pb({yi[i],i});
        v[yi[i]].pb({xi[i],i});
    }

    C(1,n,1);
    for (int id = 1; id <= L; id++){
        for (int root = 1; root <= n; root++){
            if (dep[id][root] != 1) continue;
        
            for (auto [to,p]: v[root]){
                if (dep[id][to] != 2) continue;
                st[root].insert(get(id,1,1,n,tin[id][to],tout[id][to]));
            }

            if (st[root].size() == 1) value[root] = *st[root].begin();
            else if (st[root].size() > 1){
                it = --st[root].end(); --it;
                value[root] = *(--st[root].end()) + *it;
            }
            bigset.insert(value[root]);
        }
    }

    ll last=0LL;
    while (q--){
        int d; ll len;
        cin>>d>>len;
        d = (d + last)%(n-1) + 1;
        len = (len + last)%W;

        int x = xi[d],y =yi[d]; ll delta = len - wi[d]; 
        wi[d] = len;

        for (int root: con[d]){
            bigset.erase(bigset.find(value[root]));
            int id = DP[root];
            if (dep[id][y] > dep[id][x]){
                int parent = PAR[id][y];
                st[root].erase(st[root].find(get(id,1,1,n,tin[id][parent],tout[id][parent])));
                upd(id,1,1,n,tin[id][y],tout[id][y],delta);
                st[root].insert(get(id,1,1,n,tin[id][parent],tout[id][parent]));
            }
            else{
                int parent = PAR[id][x]; 
                st[root].erase(st[root].find(get(id,1,1,n,tin[id][parent],tout[id][parent])));
                upd(id,1,1,n,tin[id][x],tout[id][x],delta);
                st[root].insert(get(id,1,1,n,tin[id][parent],tout[id][parent]));
            }

            if (st[root].size() == 1) value[root] = *st[root].begin();
            else if (st[root].size() > 1){
                it = --st[root].end(); --it;
                value[root] = *(--st[root].end()) + *it;
            }
            bigset.insert(value[root]);
        }
       
        cout<<(last = *(--bigset.end()))<<"\n"; 
    }
    
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9812 KB Output is correct
2 Correct 7 ms 9852 KB Output is correct
3 Correct 7 ms 9852 KB Output is correct
4 Correct 5 ms 9792 KB Output is correct
5 Correct 6 ms 9852 KB Output is correct
6 Correct 6 ms 9848 KB Output is correct
7 Correct 5 ms 9940 KB Output is correct
8 Correct 5 ms 9940 KB Output is correct
9 Correct 6 ms 9984 KB Output is correct
10 Correct 5 ms 9940 KB Output is correct
11 Correct 5 ms 9940 KB Output is correct
12 Correct 5 ms 9940 KB Output is correct
13 Correct 5 ms 10008 KB Output is correct
14 Correct 5 ms 9940 KB Output is correct
15 Correct 6 ms 9976 KB Output is correct
16 Correct 6 ms 10052 KB Output is correct
17 Correct 7 ms 9980 KB Output is correct
18 Correct 6 ms 10060 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9812 KB Output is correct
2 Correct 7 ms 9852 KB Output is correct
3 Correct 7 ms 9852 KB Output is correct
4 Correct 5 ms 9792 KB Output is correct
5 Correct 6 ms 9852 KB Output is correct
6 Correct 6 ms 9848 KB Output is correct
7 Correct 5 ms 9940 KB Output is correct
8 Correct 5 ms 9940 KB Output is correct
9 Correct 6 ms 9984 KB Output is correct
10 Correct 5 ms 9940 KB Output is correct
11 Correct 5 ms 9940 KB Output is correct
12 Correct 5 ms 9940 KB Output is correct
13 Correct 5 ms 10008 KB Output is correct
14 Correct 5 ms 9940 KB Output is correct
15 Correct 6 ms 9976 KB Output is correct
16 Correct 6 ms 10052 KB Output is correct
17 Correct 7 ms 9980 KB Output is correct
18 Correct 6 ms 10060 KB Output is correct
19 Correct 32 ms 10708 KB Output is correct
20 Correct 35 ms 10772 KB Output is correct
21 Correct 38 ms 10804 KB Output is correct
22 Correct 38 ms 10836 KB Output is correct
23 Correct 56 ms 14540 KB Output is correct
24 Correct 79 ms 15120 KB Output is correct
25 Correct 78 ms 15268 KB Output is correct
26 Correct 79 ms 15752 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9812 KB Output is correct
2 Correct 5 ms 9760 KB Output is correct
3 Correct 6 ms 9764 KB Output is correct
4 Correct 16 ms 9940 KB Output is correct
5 Correct 59 ms 10840 KB Output is correct
6 Correct 5 ms 9812 KB Output is correct
7 Correct 6 ms 9852 KB Output is correct
8 Correct 6 ms 9940 KB Output is correct
9 Correct 7 ms 9948 KB Output is correct
10 Correct 22 ms 10116 KB Output is correct
11 Correct 85 ms 11212 KB Output is correct
12 Correct 10 ms 11132 KB Output is correct
13 Correct 10 ms 11136 KB Output is correct
14 Correct 12 ms 11228 KB Output is correct
15 Correct 32 ms 11436 KB Output is correct
16 Correct 129 ms 12556 KB Output is correct
17 Correct 126 ms 36392 KB Output is correct
18 Correct 130 ms 36376 KB Output is correct
19 Correct 132 ms 36516 KB Output is correct
20 Correct 180 ms 36824 KB Output is correct
21 Correct 399 ms 38116 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 10708 KB Output is correct
2 Correct 54 ms 10828 KB Output is correct
3 Correct 194 ms 11472 KB Output is correct
4 Correct 388 ms 12104 KB Output is correct
5 Correct 49 ms 20300 KB Output is correct
6 Correct 118 ms 20364 KB Output is correct
7 Correct 392 ms 21076 KB Output is correct
8 Correct 787 ms 21860 KB Output is correct
9 Correct 241 ms 61260 KB Output is correct
10 Correct 355 ms 61460 KB Output is correct
11 Correct 813 ms 62088 KB Output is correct
12 Correct 1432 ms 62864 KB Output is correct
13 Correct 568 ms 117836 KB Output is correct
14 Correct 663 ms 117936 KB Output is correct
15 Correct 1254 ms 118720 KB Output is correct
16 Correct 2064 ms 119380 KB Output is correct
17 Correct 4030 ms 119248 KB Output is correct

Subtask #5
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 4112 ms 122848 KB Output is correct
2 Correct 3968 ms 123212 KB Output is correct
3 Correct 3962 ms 122984 KB Output is correct
4 Correct 3933 ms 122488 KB Output is correct
5 Correct 3997 ms 118940 KB Output is correct
6 Correct 3429 ms 96896 KB Output is correct
7 Correct 4402 ms 128936 KB Output is correct
8 Correct 4366 ms 128876 KB Output is correct
9 Correct 4402 ms 129016 KB Output is correct
10 Correct 4294 ms 128524 KB Output is correct
11 Correct 4205 ms 124220 KB Output is correct
12 Correct 3765 ms 101256 KB Output is correct
13 Correct 4562 ms 135832 KB Output is correct
14 Correct 4617 ms 135812 KB Output is correct
15 Correct 4551 ms 135848 KB Output is correct
16 Correct 4532 ms 135584 KB Output is correct
17 Correct 4545 ms 130240 KB Output is correct
18 Correct 3793 ms 104024 KB Output is correct
19 Correct 4639 ms 135652 KB Output is correct
20 Correct 4510 ms 135684 KB Output is correct
21 Correct 4579 ms 135808 KB Output is correct
22 Correct 4689 ms 135452 KB Output is correct
23 Correct 4423 ms 130432 KB Output is correct
24 Correct 3752 ms 103992 KB Output is correct

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9812 KB Output is correct
2 Correct 7 ms 9852 KB Output is correct
3 Correct 7 ms 9852 KB Output is correct
4 Correct 5 ms 9792 KB Output is correct
5 Correct 6 ms 9852 KB Output is correct
6 Correct 6 ms 9848 KB Output is correct
7 Correct 5 ms 9940 KB Output is correct
8 Correct 5 ms 9940 KB Output is correct
9 Correct 6 ms 9984 KB Output is correct
10 Correct 5 ms 9940 KB Output is correct
11 Correct 5 ms 9940 KB Output is correct
12 Correct 5 ms 9940 KB Output is correct
13 Correct 5 ms 10008 KB Output is correct
14 Correct 5 ms 9940 KB Output is correct
15 Correct 6 ms 9976 KB Output is correct
16 Correct 6 ms 10052 KB Output is correct
17 Correct 7 ms 9980 KB Output is correct
18 Correct 6 ms 10060 KB Output is correct
19 Correct 32 ms 10708 KB Output is correct
20 Correct 35 ms 10772 KB Output is correct
21 Correct 38 ms 10804 KB Output is correct
22 Correct 38 ms 10836 KB Output is correct
23 Correct 56 ms 14540 KB Output is correct
24 Correct 79 ms 15120 KB Output is correct
25 Correct 78 ms 15268 KB Output is correct
26 Correct 79 ms 15752 KB Output is correct
27 Correct 5 ms 9812 KB Output is correct
28 Correct 5 ms 9760 KB Output is correct
29 Correct 6 ms 9764 KB Output is correct
30 Correct 16 ms 9940 KB Output is correct
31 Correct 59 ms 10840 KB Output is correct
32 Correct 5 ms 9812 KB Output is correct
33 Correct 6 ms 9852 KB Output is correct
34 Correct 6 ms 9940 KB Output is correct
35 Correct 7 ms 9948 KB Output is correct
36 Correct 22 ms 10116 KB Output is correct
37 Correct 85 ms 11212 KB Output is correct
38 Correct 10 ms 11132 KB Output is correct
39 Correct 10 ms 11136 KB Output is correct
40 Correct 12 ms 11228 KB Output is correct
41 Correct 32 ms 11436 KB Output is correct
42 Correct 129 ms 12556 KB Output is correct
43 Correct 126 ms 36392 KB Output is correct
44 Correct 130 ms 36376 KB Output is correct
45 Correct 132 ms 36516 KB Output is correct
46 Correct 180 ms 36824 KB Output is correct
47 Correct 399 ms 38116 KB Output is correct
48 Correct 11 ms 10708 KB Output is correct
49 Correct 54 ms 10828 KB Output is correct
50 Correct 194 ms 11472 KB Output is correct
51 Correct 388 ms 12104 KB Output is correct
52 Correct 49 ms 20300 KB Output is correct
53 Correct 118 ms 20364 KB Output is correct
54 Correct 392 ms 21076 KB Output is correct
55 Correct 787 ms 21860 KB Output is correct
56 Correct 241 ms 61260 KB Output is correct
57 Correct 355 ms 61460 KB Output is correct
58 Correct 813 ms 62088 KB Output is correct
59 Correct 1432 ms 62864 KB Output is correct
60 Correct 568 ms 117836 KB Output is correct
61 Correct 663 ms 117936 KB Output is correct
62 Correct 1254 ms 118720 KB Output is correct
63 Correct 2064 ms 119380 KB Output is correct
64 Correct 4030 ms 119248 KB Output is correct
65 Correct 4112 ms 122848 KB Output is correct
66 Correct 3968 ms 123212 KB Output is correct
67 Correct 3962 ms 122984 KB Output is correct
68 Correct 3933 ms 122488 KB Output is correct
69 Correct 3997 ms 118940 KB Output is correct
70 Correct 3429 ms 96896 KB Output is correct
71 Correct 4402 ms 128936 KB Output is correct
72 Correct 4366 ms 128876 KB Output is correct
73 Correct 4402 ms 129016 KB Output is correct
74 Correct 4294 ms 128524 KB Output is correct
75 Correct 4205 ms 124220 KB Output is correct
76 Correct 3765 ms 101256 KB Output is correct
77 Correct 4562 ms 135832 KB Output is correct
78 Correct 4617 ms 135812 KB Output is correct
79 Correct 4551 ms 135848 KB Output is correct
80 Correct 4532 ms 135584 KB Output is correct
81 Correct 4545 ms 130240 KB Output is correct
82 Correct 3793 ms 104024 KB Output is correct
83 Correct 4639 ms 135652 KB Output is correct
84 Correct 4510 ms 135684 KB Output is correct
85 Correct 4579 ms 135808 KB Output is correct
86 Correct 4689 ms 135452 KB Output is correct
87 Correct 4423 ms 130432 KB Output is correct
88 Correct 3752 ms 103992 KB Output is correct
89 Correct 4086 ms 122224 KB Output is correct
90 Correct 4242 ms 123312 KB Output is correct
91 Correct 4703 ms 126184 KB Output is correct
92 Correct 4681 ms 127664 KB Output is correct
93 Correct 4571 ms 130476 KB Output is correct
94 Correct 4762 ms 131024 KB Output is correct
95 Execution timed out 5001 ms 132808 KB Time limit exceeded
96 Halted 0 ms 0 KB -