oj.uz

Submission #478138

# Submission time Handle Problem Language Result Execution time Memory
478138 2021-10-05T19:54:56 Z bonopo Dynamic Diameter (CEOI19_diameter) C++17
100 / 100
 4459 ms 197400 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC target ("avx2")
#define pb push_back
#define rc (i<<1)|1
#define lc (i<<1)
#define el "\n"
#define f first
#define s second

typedef long long ll;
const int MM=1e5+5, MOD=1e9+7, LOG=19;
int N, Q, sz[MM], bk[MM], pa[MM], in[LOG][MM], ot[LOG][MM], cp[LOG][MM], tp[LOG][MM], mp[MM], ct;
vector<int> adj[MM]; ll av[MM], W;
multiset<ll> ast;

struct node {
    ll lz;
    pair<ll,int> mx;
};

struct tree {
    vector<node> seg;
    int wt;

    inline void prop(int i, int l, int r) {
        if(l!=r) {
            seg[lc].lz+=seg[i].lz;
            seg[rc].lz+=seg[i].lz; }
        seg[i].mx.f+=seg[i].lz;
        seg[i].lz=0;
    }

    void build(int i, int sl, int sr) {
        if(sl==sr) {
            seg[i].mx=make_pair(0,mp[sl]);
            return; }
        int m=sl+sr>>1;
        build(rc, m+1, sr);
        build(lc, sl, m);
        calc(i);
    }

    inline void calc(int i) {
        seg[i].mx=max(seg[lc].mx, seg[rc].mx);
    }

    void upd(int i, int sl, int sr, int l, int r, ll v) {
        prop(i, sl, sr);
        if(l>sr || r<sl) return;
        if(l<=sl&&sr<=r) {
            seg[i].lz+=v;
            prop(i, sl, sr); return; }
        int m=sl+sr>>1;
        upd(rc, m+1, sr, l, r, v);
        upd(lc, sl, m, l, r, v);
        calc(i);
    }

    pair<ll,int> rmq(int i, int sl, int sr, int l, int r) {
        if(l>sr || r<sl) return {0,0};
        prop(i, sl, sr);
        if(l<=sl&&sr<=r) return seg[i].mx;
        int m=sl+sr>>1;
        return max(rmq(lc, sl, m, l, r), rmq(rc, m+1, sr, l, r));
    }

    void init(int n) {
        wt=n;
        seg.resize(4*n+4);
        build(1, 1, n);
    }
} st[MM];

int crt(int u, int th, int fa) {
    for(int &v:adj[u]) if(v!=fa&&!bk[v]&&sz[v]>th) {
        return crt(v, th, u); }
    return u;
}

void dfs(int u, int fa) {
    sz[u]=1;
    for(int &v:adj[u]) if(v!=fa&&!bk[v]) {
        dfs(v, u);
        sz[u]+=sz[v];
    }
}

void etr(int u, int fa, int lvl, int rt, int tv) {
    in[lvl][u]=++ct; cp[lvl][u]=rt; tp[lvl][u]=tv; mp[ct]=u;
    for(int &v:adj[u]) if(v!=fa&&!bk[v]) {
        etr(v, u, lvl, rt, tv); }
    ot[lvl][u]=ct;
}

void rec(int rt, int nds, int fa=-1, int lvl=0) {
    if(nds<=1) return; dfs(rt, 0);
    rt=crt(rt, nds/2, 0); pa[rt]=fa;
    //  cout<<rt<<el;
    bk[rt]=true; ct=0;

    // get ett
    cp[lvl][rt]=tp[lvl][rt]=rt;
    for(int &v:adj[rt]) if(!bk[v]) etr(v, rt, lvl, rt, v);
    if(ct==0) return;

    // construct tree
    st[rt].init(ct);
    int tally=0, lv=-1;
    for(int &v:adj[rt]) if(!bk[v]) {
        if(sz[v]<sz[rt]) {
            tally+=sz[v];
            rec(v, sz[v], rt, lvl+1); }
        else lv=v; }
    if(~lv) rec(lv, nds-tally-1, rt, lvl+1);
}

void qry(int u, int v, ll val) {

    // find smallest component
    int cur=0;
    while(cur<LOG-1&&cp[cur+1][u]==cp[cur+1][v]&&cp[cur+1][u]!=0) ++cur;
    //  cout<<"iterating on "<<u<<" starting with "<<cur<<" delta "<<val<<el;

    // jump
    int crt=cp[cur][u];
    while(cur>=0) {
        // update edge
        //   cout<<"crt "<<crt<<el;
        int w=(in[cur][u]>in[cur][v]?u:v);

        // cout<<"level "<<cur<<" w "<<w<<" cent "<<crt<<" updating "<<in[cur][w]<<" "<<ot[cur][w]<<el;
        st[crt].upd(1, 1, st[crt].wt, in[cur][w], ot[cur][w], val);

        // query max
        auto x=st[crt].rmq(1, 1, st[crt].wt, 1, st[crt].wt);
        // cout<<"x value "<<x.f<<" "<<x.s<<" "<<tp[cur][x.s]<<" "<<in[cur][tp[cur][x.s]]<<" "<<ot[cur][tp[cur][x.s]]<<el;
        auto y=max(st[crt].rmq(1, 1, st[crt].wt, 1, in[cur][tp[cur][x.s]]-1), st[crt].rmq(1, 1, st[crt].wt, ot[cur][tp[cur][x.s]]+1, st[crt].wt));
        //cout<<"y value "<<y.f<<" "<<x.s<<el;

        ll cnd=x.f+y.f;
        if(cnd!=av[crt]) {
            ast.erase(ast.find(av[crt]));
            ast.insert(av[crt]=cnd);
        }

        crt=pa[crt]; cur--;
    }

}

int32_t main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    cin>>N>>Q>>W;
    vector<pair<ll,pair<int,int>>> edg;
    for(int i=1; i<N; ++i) {
        ll u, v, w; cin>>u>>v>>w;
        adj[u].pb(v); adj[v].pb(u);
        edg.pb({w,{u,v}});
    }

    // preprocess
    rec(1, N);
    for(int i=1; i<=N; ++i) ast.insert(0);
    for(auto &e:edg) qry(e.s.f, e.s.s, e.f);

    ll last=0, e, w;
    for(int q=1; q<=Q; ++q) {
        cin>>e>>w;
        e=(e+last)%(N-1);
        w=(w+last)%W;

        qry(edg[e].s.f, edg[e].s.s, w-edg[e].f);
        last=*ast.rbegin(); edg[e].f=w;
        cout<<last<<el;
    }
}

Compilation message

diameter.cpp: In member function 'void tree::build(int, int, int)':
diameter.cpp:42:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   42 |         int m=sl+sr>>1;
      |               ~~^~~
diameter.cpp: In member function 'void tree::upd(int, int, int, int, int, ll)':
diameter.cpp:58:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   58 |         int m=sl+sr>>1;
      |               ~~^~~
diameter.cpp: In member function 'std::pair<long long int, int> tree::rmq(int, int, int, int, int)':
diameter.cpp:68:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   68 |         int m=sl+sr>>1;
      |               ~~^~~
diameter.cpp: In function 'void rec(int, int, int, int)':
diameter.cpp:101:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
  101 |     if(nds<=1) return; dfs(rt, 0);
      |     ^~
diameter.cpp:101:24: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  101 |     if(nds<=1) return; dfs(rt, 0);
      |                        ^~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5836 KB Output is correct
2 Correct 3 ms 5836 KB Output is correct
3 Correct 3 ms 5836 KB Output is correct
4 Correct 3 ms 5836 KB Output is correct
5 Correct 3 ms 5836 KB Output is correct
6 Correct 3 ms 5836 KB Output is correct
7 Correct 4 ms 5836 KB Output is correct
8 Correct 3 ms 5836 KB Output is correct
9 Correct 3 ms 5836 KB Output is correct
10 Correct 4 ms 5836 KB Output is correct
11 Correct 3 ms 5836 KB Output is correct
12 Correct 3 ms 5964 KB Output is correct
13 Correct 4 ms 5964 KB Output is correct
14 Correct 5 ms 5956 KB Output is correct
15 Correct 3 ms 5964 KB Output is correct
16 Correct 4 ms 5964 KB Output is correct
17 Correct 4 ms 5964 KB Output is correct
18 Correct 5 ms 5964 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5836 KB Output is correct
2 Correct 3 ms 5836 KB Output is correct
3 Correct 3 ms 5836 KB Output is correct
4 Correct 3 ms 5836 KB Output is correct
5 Correct 3 ms 5836 KB Output is correct
6 Correct 3 ms 5836 KB Output is correct
7 Correct 4 ms 5836 KB Output is correct
8 Correct 3 ms 5836 KB Output is correct
9 Correct 3 ms 5836 KB Output is correct
10 Correct 4 ms 5836 KB Output is correct
11 Correct 3 ms 5836 KB Output is correct
12 Correct 3 ms 5964 KB Output is correct
13 Correct 4 ms 5964 KB Output is correct
14 Correct 5 ms 5956 KB Output is correct
15 Correct 3 ms 5964 KB Output is correct
16 Correct 4 ms 5964 KB Output is correct
17 Correct 4 ms 5964 KB Output is correct
18 Correct 5 ms 5964 KB Output is correct
19 Correct 20 ms 6732 KB Output is correct
20 Correct 22 ms 6848 KB Output is correct
21 Correct 25 ms 6988 KB Output is correct
22 Correct 22 ms 7156 KB Output is correct
23 Correct 43 ms 10264 KB Output is correct
24 Correct 60 ms 11452 KB Output is correct
25 Correct 66 ms 12020 KB Output is correct
26 Correct 73 ms 13000 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5836 KB Output is correct
2 Correct 3 ms 5856 KB Output is correct
3 Correct 4 ms 5836 KB Output is correct
4 Correct 12 ms 5836 KB Output is correct
5 Correct 49 ms 6188 KB Output is correct
6 Correct 3 ms 5836 KB Output is correct
7 Correct 3 ms 5964 KB Output is correct
8 Correct 4 ms 5964 KB Output is correct
9 Correct 5 ms 5856 KB Output is correct
10 Correct 21 ms 5996 KB Output is correct
11 Correct 80 ms 6392 KB Output is correct
12 Correct 8 ms 6860 KB Output is correct
13 Correct 8 ms 6928 KB Output is correct
14 Correct 11 ms 6988 KB Output is correct
15 Correct 30 ms 6976 KB Output is correct
16 Correct 116 ms 7396 KB Output is correct
17 Correct 158 ms 27300 KB Output is correct
18 Correct 129 ms 27320 KB Output is correct
19 Correct 141 ms 27380 KB Output is correct
20 Correct 167 ms 27456 KB Output is correct
21 Correct 268 ms 28036 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 6860 KB Output is correct
2 Correct 29 ms 6988 KB Output is correct
3 Correct 112 ms 7108 KB Output is correct
4 Correct 221 ms 7468 KB Output is correct
5 Correct 63 ms 19144 KB Output is correct
6 Correct 93 ms 19212 KB Output is correct
7 Correct 268 ms 19400 KB Output is correct
8 Correct 536 ms 19848 KB Output is correct
9 Correct 361 ms 84492 KB Output is correct
10 Correct 401 ms 84704 KB Output is correct
11 Correct 670 ms 84828 KB Output is correct
12 Correct 1130 ms 85128 KB Output is correct
13 Correct 768 ms 173800 KB Output is correct
14 Correct 839 ms 173780 KB Output is correct
15 Correct 1162 ms 173964 KB Output is correct
16 Correct 1642 ms 174384 KB Output is correct
17 Correct 2180 ms 174232 KB Output is correct

Subtask #5
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 3027 ms 139044 KB Output is correct
2 Correct 3079 ms 143408 KB Output is correct
3 Correct 3032 ms 141108 KB Output is correct
4 Correct 3205 ms 143828 KB Output is correct
5 Correct 3021 ms 135208 KB Output is correct
6 Correct 2231 ms 99608 KB Output is correct
7 Correct 4459 ms 178332 KB Output is correct
8 Correct 4458 ms 182324 KB Output is correct
9 Correct 4374 ms 182448 KB Output is correct
10 Correct 4245 ms 181764 KB Output is correct
11 Correct 3857 ms 172764 KB Output is correct
12 Correct 3051 ms 123728 KB Output is correct
13 Correct 4062 ms 197220 KB Output is correct
14 Correct 4334 ms 197240 KB Output is correct
15 Correct 4109 ms 197224 KB Output is correct
16 Correct 4075 ms 196488 KB Output is correct
17 Correct 3993 ms 186352 KB Output is correct
18 Correct 3292 ms 129656 KB Output is correct
19 Correct 4413 ms 197172 KB Output is correct
20 Correct 4290 ms 197188 KB Output is correct
21 Correct 4210 ms 197400 KB Output is correct
22 Correct 4270 ms 196440 KB Output is correct
23 Correct 4070 ms 186228 KB Output is correct
24 Correct 3073 ms 129668 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5836 KB Output is correct
2 Correct 3 ms 5836 KB Output is correct
3 Correct 3 ms 5836 KB Output is correct
4 Correct 3 ms 5836 KB Output is correct
5 Correct 3 ms 5836 KB Output is correct
6 Correct 3 ms 5836 KB Output is correct
7 Correct 4 ms 5836 KB Output is correct
8 Correct 3 ms 5836 KB Output is correct
9 Correct 3 ms 5836 KB Output is correct
10 Correct 4 ms 5836 KB Output is correct
11 Correct 3 ms 5836 KB Output is correct
12 Correct 3 ms 5964 KB Output is correct
13 Correct 4 ms 5964 KB Output is correct
14 Correct 5 ms 5956 KB Output is correct
15 Correct 3 ms 5964 KB Output is correct
16 Correct 4 ms 5964 KB Output is correct
17 Correct 4 ms 5964 KB Output is correct
18 Correct 5 ms 5964 KB Output is correct
19 Correct 20 ms 6732 KB Output is correct
20 Correct 22 ms 6848 KB Output is correct
21 Correct 25 ms 6988 KB Output is correct
22 Correct 22 ms 7156 KB Output is correct
23 Correct 43 ms 10264 KB Output is correct
24 Correct 60 ms 11452 KB Output is correct
25 Correct 66 ms 12020 KB Output is correct
26 Correct 73 ms 13000 KB Output is correct
27 Correct 3 ms 5836 KB Output is correct
28 Correct 3 ms 5856 KB Output is correct
29 Correct 4 ms 5836 KB Output is correct
30 Correct 12 ms 5836 KB Output is correct
31 Correct 49 ms 6188 KB Output is correct
32 Correct 3 ms 5836 KB Output is correct
33 Correct 3 ms 5964 KB Output is correct
34 Correct 4 ms 5964 KB Output is correct
35 Correct 5 ms 5856 KB Output is correct
36 Correct 21 ms 5996 KB Output is correct
37 Correct 80 ms 6392 KB Output is correct
38 Correct 8 ms 6860 KB Output is correct
39 Correct 8 ms 6928 KB Output is correct
40 Correct 11 ms 6988 KB Output is correct
41 Correct 30 ms 6976 KB Output is correct
42 Correct 116 ms 7396 KB Output is correct
43 Correct 158 ms 27300 KB Output is correct
44 Correct 129 ms 27320 KB Output is correct
45 Correct 141 ms 27380 KB Output is correct
46 Correct 167 ms 27456 KB Output is correct
47 Correct 268 ms 28036 KB Output is correct
48 Correct 10 ms 6860 KB Output is correct
49 Correct 29 ms 6988 KB Output is correct
50 Correct 112 ms 7108 KB Output is correct
51 Correct 221 ms 7468 KB Output is correct
52 Correct 63 ms 19144 KB Output is correct
53 Correct 93 ms 19212 KB Output is correct
54 Correct 268 ms 19400 KB Output is correct
55 Correct 536 ms 19848 KB Output is correct
56 Correct 361 ms 84492 KB Output is correct
57 Correct 401 ms 84704 KB Output is correct
58 Correct 670 ms 84828 KB Output is correct
59 Correct 1130 ms 85128 KB Output is correct
60 Correct 768 ms 173800 KB Output is correct
61 Correct 839 ms 173780 KB Output is correct
62 Correct 1162 ms 173964 KB Output is correct
63 Correct 1642 ms 174384 KB Output is correct
64 Correct 2180 ms 174232 KB Output is correct
65 Correct 3027 ms 139044 KB Output is correct
66 Correct 3079 ms 143408 KB Output is correct
67 Correct 3032 ms 141108 KB Output is correct
68 Correct 3205 ms 143828 KB Output is correct
69 Correct 3021 ms 135208 KB Output is correct
70 Correct 2231 ms 99608 KB Output is correct
71 Correct 4459 ms 178332 KB Output is correct
72 Correct 4458 ms 182324 KB Output is correct
73 Correct 4374 ms 182448 KB Output is correct
74 Correct 4245 ms 181764 KB Output is correct
75 Correct 3857 ms 172764 KB Output is correct
76 Correct 3051 ms 123728 KB Output is correct
77 Correct 4062 ms 197220 KB Output is correct
78 Correct 4334 ms 197240 KB Output is correct
79 Correct 4109 ms 197224 KB Output is correct
80 Correct 4075 ms 196488 KB Output is correct
81 Correct 3993 ms 186352 KB Output is correct
82 Correct 3292 ms 129656 KB Output is correct
83 Correct 4413 ms 197172 KB Output is correct
84 Correct 4290 ms 197188 KB Output is correct
85 Correct 4210 ms 197400 KB Output is correct
86 Correct 4270 ms 196440 KB Output is correct
87 Correct 4070 ms 186228 KB Output is correct
88 Correct 3073 ms 129668 KB Output is correct
89 Correct 2964 ms 144888 KB Output is correct
90 Correct 3438 ms 160236 KB Output is correct
91 Correct 3928 ms 177008 KB Output is correct
92 Correct 4061 ms 181544 KB Output is correct
93 Correct 4368 ms 187392 KB Output is correct
94 Correct 4331 ms 191184 KB Output is correct
95 Correct 4108 ms 196568 KB Output is correct
96 Correct 4254 ms 196476 KB Output is correct
97 Correct 4447 ms 196656 KB Output is correct
98 Correct 4314 ms 196496 KB Output is correct
99 Correct 4203 ms 196544 KB Output is correct
100 Correct 4253 ms 196604 KB Output is correct