oj.uz

Submission #478130

# Submission time Handle Problem Language Result Execution time Memory
478130 2021-10-05T18:49:24 Z bonopo Dynamic Diameter (CEOI19_diameter) C++17
49 / 100
 5000 ms 197096 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
#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, W, sz[MM], bk[MM], pa[MM], in[LOG][MM], ot[LOG][MM], cp[LOG][MM], tp[LOG][MM], ct;
vector<int> adj[MM]; ll av[MM];
gp_hash_table<int,int> mp[MM];
multiset<ll> ast;

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

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

    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={0,sl};
            return; }
        int m=sl+sr>>1;
        build(rc, m+1, sr);
        build(lc, sl, m);
        calc(i);
    }

    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) {
        prop(i, sl, sr);
        if(l>sr || r<sl) return {0,0};
        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[rt][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) {
    assert(lvl<LOG);
    dfs(rt, 0);

    // find centroid
    //  cout<<"centroid for "<<rt<<" nds "<<nds<<" lvl "<<lvl<<" is ";
    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(nds);
    dfs(rt, 0);

    for(int &v:adj[rt]) if(!bk[v]) {
            rec(v, sz[v], 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]!=0) ++cur;
    //  cout<<"iterating on "<<u<<" starting with "<<cur<<" delta "<<val<<el;

    // jump
    int crt=u;
    while(cur>=0) {
        // update edge
        //   cout<<"crt "<<crt<<el;

        if(cp[cur][u]==crt&&cp[cur][v]==crt) {
            assert(st[crt].wt>0);
            int w=(in[cur][u]>in[cur][v]?u:v);
            ast.erase(ast.find(av[crt]));

            // 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);
            x.s=mp[crt][x.s];
            // 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; av[crt]=cnd;
            ast.insert(av[crt]);
        }

        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;
    memset(pa, -1, sizeof(pa));
    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:40:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   40 |         int m=sl+sr>>1;
      |               ~~^~~
diameter.cpp: In member function 'void tree::upd(int, int, int, int, int, ll)':
diameter.cpp:56:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   56 |         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:66:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   66 |         int m=sl+sr>>1;
      |               ~~^~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 27292 KB Output is correct
2 Correct 22 ms 27356 KB Output is correct
3 Correct 21 ms 27424 KB Output is correct
4 Correct 22 ms 27440 KB Output is correct
5 Correct 25 ms 27348 KB Output is correct
6 Correct 22 ms 27336 KB Output is correct
7 Correct 22 ms 27372 KB Output is correct
8 Correct 24 ms 27384 KB Output is correct
9 Correct 22 ms 27384 KB Output is correct
10 Correct 22 ms 27456 KB Output is correct
11 Correct 22 ms 27484 KB Output is correct
12 Correct 24 ms 27484 KB Output is correct
13 Correct 23 ms 27468 KB Output is correct
14 Correct 26 ms 27496 KB Output is correct
15 Correct 23 ms 27488 KB Output is correct
16 Correct 24 ms 27528 KB Output is correct
17 Correct 23 ms 27476 KB Output is correct
18 Correct 23 ms 27532 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 27292 KB Output is correct
2 Correct 22 ms 27356 KB Output is correct
3 Correct 21 ms 27424 KB Output is correct
4 Correct 22 ms 27440 KB Output is correct
5 Correct 25 ms 27348 KB Output is correct
6 Correct 22 ms 27336 KB Output is correct
7 Correct 22 ms 27372 KB Output is correct
8 Correct 24 ms 27384 KB Output is correct
9 Correct 22 ms 27384 KB Output is correct
10 Correct 22 ms 27456 KB Output is correct
11 Correct 22 ms 27484 KB Output is correct
12 Correct 24 ms 27484 KB Output is correct
13 Correct 23 ms 27468 KB Output is correct
14 Correct 26 ms 27496 KB Output is correct
15 Correct 23 ms 27488 KB Output is correct
16 Correct 24 ms 27528 KB Output is correct
17 Correct 23 ms 27476 KB Output is correct
18 Correct 23 ms 27532 KB Output is correct
19 Correct 43 ms 28452 KB Output is correct
20 Correct 45 ms 28612 KB Output is correct
21 Correct 50 ms 28888 KB Output is correct
22 Correct 49 ms 28956 KB Output is correct
23 Correct 84 ms 33072 KB Output is correct
24 Correct 111 ms 34708 KB Output is correct
25 Correct 114 ms 35580 KB Output is correct
26 Correct 121 ms 36924 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 27396 KB Output is correct
2 Correct 21 ms 27340 KB Output is correct
3 Correct 22 ms 27468 KB Output is correct
4 Correct 34 ms 27396 KB Output is correct
5 Correct 82 ms 27804 KB Output is correct
6 Correct 22 ms 27312 KB Output is correct
7 Correct 23 ms 27516 KB Output is correct
8 Correct 24 ms 27412 KB Output is correct
9 Correct 25 ms 27468 KB Output is correct
10 Correct 40 ms 27544 KB Output is correct
11 Correct 108 ms 27888 KB Output is correct
12 Correct 29 ms 28604 KB Output is correct
13 Correct 35 ms 28612 KB Output is correct
14 Correct 31 ms 28716 KB Output is correct
15 Correct 63 ms 28712 KB Output is correct
16 Correct 137 ms 29152 KB Output is correct
17 Correct 197 ms 52804 KB Output is correct
18 Correct 197 ms 52736 KB Output is correct
19 Correct 183 ms 52720 KB Output is correct
20 Correct 256 ms 52900 KB Output is correct
21 Correct 342 ms 53328 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 28572 KB Output is correct
2 Correct 52 ms 28612 KB Output is correct
3 Correct 160 ms 28852 KB Output is correct
4 Correct 285 ms 29124 KB Output is correct
5 Correct 97 ms 41492 KB Output is correct
6 Correct 136 ms 41512 KB Output is correct
7 Correct 338 ms 41964 KB Output is correct
8 Correct 573 ms 42204 KB Output is correct
9 Correct 526 ms 111660 KB Output is correct
10 Correct 585 ms 111808 KB Output is correct
11 Correct 904 ms 112064 KB Output is correct
12 Correct 1333 ms 112316 KB Output is correct
13 Correct 1210 ms 196516 KB Output is correct
14 Correct 1173 ms 196536 KB Output is correct
15 Correct 1727 ms 196904 KB Output is correct
16 Correct 2250 ms 197080 KB Output is correct
17 Correct 3076 ms 197096 KB Output is correct

Subtask #5
0 / 24.0

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

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 27292 KB Output is correct
2 Correct 22 ms 27356 KB Output is correct
3 Correct 21 ms 27424 KB Output is correct
4 Correct 22 ms 27440 KB Output is correct
5 Correct 25 ms 27348 KB Output is correct
6 Correct 22 ms 27336 KB Output is correct
7 Correct 22 ms 27372 KB Output is correct
8 Correct 24 ms 27384 KB Output is correct
9 Correct 22 ms 27384 KB Output is correct
10 Correct 22 ms 27456 KB Output is correct
11 Correct 22 ms 27484 KB Output is correct
12 Correct 24 ms 27484 KB Output is correct
13 Correct 23 ms 27468 KB Output is correct
14 Correct 26 ms 27496 KB Output is correct
15 Correct 23 ms 27488 KB Output is correct
16 Correct 24 ms 27528 KB Output is correct
17 Correct 23 ms 27476 KB Output is correct
18 Correct 23 ms 27532 KB Output is correct
19 Correct 43 ms 28452 KB Output is correct
20 Correct 45 ms 28612 KB Output is correct
21 Correct 50 ms 28888 KB Output is correct
22 Correct 49 ms 28956 KB Output is correct
23 Correct 84 ms 33072 KB Output is correct
24 Correct 111 ms 34708 KB Output is correct
25 Correct 114 ms 35580 KB Output is correct
26 Correct 121 ms 36924 KB Output is correct
27 Correct 25 ms 27396 KB Output is correct
28 Correct 21 ms 27340 KB Output is correct
29 Correct 22 ms 27468 KB Output is correct
30 Correct 34 ms 27396 KB Output is correct
31 Correct 82 ms 27804 KB Output is correct
32 Correct 22 ms 27312 KB Output is correct
33 Correct 23 ms 27516 KB Output is correct
34 Correct 24 ms 27412 KB Output is correct
35 Correct 25 ms 27468 KB Output is correct
36 Correct 40 ms 27544 KB Output is correct
37 Correct 108 ms 27888 KB Output is correct
38 Correct 29 ms 28604 KB Output is correct
39 Correct 35 ms 28612 KB Output is correct
40 Correct 31 ms 28716 KB Output is correct
41 Correct 63 ms 28712 KB Output is correct
42 Correct 137 ms 29152 KB Output is correct
43 Correct 197 ms 52804 KB Output is correct
44 Correct 197 ms 52736 KB Output is correct
45 Correct 183 ms 52720 KB Output is correct
46 Correct 256 ms 52900 KB Output is correct
47 Correct 342 ms 53328 KB Output is correct
48 Correct 31 ms 28572 KB Output is correct
49 Correct 52 ms 28612 KB Output is correct
50 Correct 160 ms 28852 KB Output is correct
51 Correct 285 ms 29124 KB Output is correct
52 Correct 97 ms 41492 KB Output is correct
53 Correct 136 ms 41512 KB Output is correct
54 Correct 338 ms 41964 KB Output is correct
55 Correct 573 ms 42204 KB Output is correct
56 Correct 526 ms 111660 KB Output is correct
57 Correct 585 ms 111808 KB Output is correct
58 Correct 904 ms 112064 KB Output is correct
59 Correct 1333 ms 112316 KB Output is correct
60 Correct 1210 ms 196516 KB Output is correct
61 Correct 1173 ms 196536 KB Output is correct
62 Correct 1727 ms 196904 KB Output is correct
63 Correct 2250 ms 197080 KB Output is correct
64 Correct 3076 ms 197096 KB Output is correct
65 Execution timed out 5039 ms 30528 KB Time limit exceeded
66 Halted 0 ms 0 KB -