oj.uz

Submission #478128

# Submission time Handle Problem Language Result Execution time Memory
478128 2021-10-05T18:13:06 Z bonopo Dynamic Diameter (CEOI19_diameter) C++17
49 / 100
 5000 ms 203500 KB 
#include "bits/stdc++.h"
using namespace std;
#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];
unordered_map<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) {
    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) {
            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;
    }
}

// MM

Compilation message

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

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 11724 KB Output is correct
2 Correct 6 ms 11724 KB Output is correct
3 Correct 6 ms 11724 KB Output is correct
4 Correct 6 ms 11724 KB Output is correct
5 Correct 6 ms 11724 KB Output is correct
6 Correct 8 ms 11724 KB Output is correct
7 Correct 6 ms 11724 KB Output is correct
8 Correct 6 ms 11756 KB Output is correct
9 Correct 6 ms 11852 KB Output is correct
10 Correct 8 ms 11744 KB Output is correct
11 Correct 7 ms 11724 KB Output is correct
12 Correct 6 ms 11852 KB Output is correct
13 Correct 7 ms 11804 KB Output is correct
14 Correct 6 ms 11880 KB Output is correct
15 Correct 9 ms 11852 KB Output is correct
16 Correct 7 ms 11808 KB Output is correct
17 Correct 8 ms 11852 KB Output is correct
18 Correct 7 ms 11824 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 11724 KB Output is correct
2 Correct 6 ms 11724 KB Output is correct
3 Correct 6 ms 11724 KB Output is correct
4 Correct 6 ms 11724 KB Output is correct
5 Correct 6 ms 11724 KB Output is correct
6 Correct 8 ms 11724 KB Output is correct
7 Correct 6 ms 11724 KB Output is correct
8 Correct 6 ms 11756 KB Output is correct
9 Correct 6 ms 11852 KB Output is correct
10 Correct 8 ms 11744 KB Output is correct
11 Correct 7 ms 11724 KB Output is correct
12 Correct 6 ms 11852 KB Output is correct
13 Correct 7 ms 11804 KB Output is correct
14 Correct 6 ms 11880 KB Output is correct
15 Correct 9 ms 11852 KB Output is correct
16 Correct 7 ms 11808 KB Output is correct
17 Correct 8 ms 11852 KB Output is correct
18 Correct 7 ms 11824 KB Output is correct
19 Correct 26 ms 12936 KB Output is correct
20 Correct 32 ms 13004 KB Output is correct
21 Correct 34 ms 13264 KB Output is correct
22 Correct 34 ms 13508 KB Output is correct
23 Correct 61 ms 17924 KB Output is correct
24 Correct 88 ms 19644 KB Output is correct
25 Correct 111 ms 20532 KB Output is correct
26 Correct 105 ms 21944 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11596 KB Output is correct
2 Correct 6 ms 11596 KB Output is correct
3 Correct 8 ms 11724 KB Output is correct
4 Correct 18 ms 11760 KB Output is correct
5 Correct 62 ms 12124 KB Output is correct
6 Correct 6 ms 11596 KB Output is correct
7 Correct 6 ms 11852 KB Output is correct
8 Correct 7 ms 11848 KB Output is correct
9 Correct 9 ms 11852 KB Output is correct
10 Correct 24 ms 11852 KB Output is correct
11 Correct 86 ms 12224 KB Output is correct
12 Correct 14 ms 13004 KB Output is correct
13 Correct 13 ms 13004 KB Output is correct
14 Correct 15 ms 13044 KB Output is correct
15 Correct 37 ms 13072 KB Output is correct
16 Correct 115 ms 13476 KB Output is correct
17 Correct 168 ms 38496 KB Output is correct
18 Correct 197 ms 38564 KB Output is correct
19 Correct 176 ms 38412 KB Output is correct
20 Correct 199 ms 38564 KB Output is correct
21 Correct 338 ms 39048 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 13132 KB Output is correct
2 Correct 39 ms 13140 KB Output is correct
3 Correct 143 ms 13272 KB Output is correct
4 Correct 258 ms 13616 KB Output is correct
5 Correct 94 ms 27712 KB Output is correct
6 Correct 142 ms 27720 KB Output is correct
7 Correct 325 ms 27948 KB Output is correct
8 Correct 574 ms 28560 KB Output is correct
9 Correct 591 ms 108672 KB Output is correct
10 Correct 619 ms 108836 KB Output is correct
11 Correct 965 ms 109008 KB Output is correct
12 Correct 1379 ms 109332 KB Output is correct
13 Correct 1177 ms 202780 KB Output is correct
14 Correct 1301 ms 202720 KB Output is correct
15 Correct 1759 ms 202968 KB Output is correct
16 Correct 2237 ms 203500 KB Output is correct
17 Correct 3008 ms 203164 KB Output is correct

Subtask #5
0 / 24.0

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

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 11724 KB Output is correct
2 Correct 6 ms 11724 KB Output is correct
3 Correct 6 ms 11724 KB Output is correct
4 Correct 6 ms 11724 KB Output is correct
5 Correct 6 ms 11724 KB Output is correct
6 Correct 8 ms 11724 KB Output is correct
7 Correct 6 ms 11724 KB Output is correct
8 Correct 6 ms 11756 KB Output is correct
9 Correct 6 ms 11852 KB Output is correct
10 Correct 8 ms 11744 KB Output is correct
11 Correct 7 ms 11724 KB Output is correct
12 Correct 6 ms 11852 KB Output is correct
13 Correct 7 ms 11804 KB Output is correct
14 Correct 6 ms 11880 KB Output is correct
15 Correct 9 ms 11852 KB Output is correct
16 Correct 7 ms 11808 KB Output is correct
17 Correct 8 ms 11852 KB Output is correct
18 Correct 7 ms 11824 KB Output is correct
19 Correct 26 ms 12936 KB Output is correct
20 Correct 32 ms 13004 KB Output is correct
21 Correct 34 ms 13264 KB Output is correct
22 Correct 34 ms 13508 KB Output is correct
23 Correct 61 ms 17924 KB Output is correct
24 Correct 88 ms 19644 KB Output is correct
25 Correct 111 ms 20532 KB Output is correct
26 Correct 105 ms 21944 KB Output is correct
27 Correct 6 ms 11596 KB Output is correct
28 Correct 6 ms 11596 KB Output is correct
29 Correct 8 ms 11724 KB Output is correct
30 Correct 18 ms 11760 KB Output is correct
31 Correct 62 ms 12124 KB Output is correct
32 Correct 6 ms 11596 KB Output is correct
33 Correct 6 ms 11852 KB Output is correct
34 Correct 7 ms 11848 KB Output is correct
35 Correct 9 ms 11852 KB Output is correct
36 Correct 24 ms 11852 KB Output is correct
37 Correct 86 ms 12224 KB Output is correct
38 Correct 14 ms 13004 KB Output is correct
39 Correct 13 ms 13004 KB Output is correct
40 Correct 15 ms 13044 KB Output is correct
41 Correct 37 ms 13072 KB Output is correct
42 Correct 115 ms 13476 KB Output is correct
43 Correct 168 ms 38496 KB Output is correct
44 Correct 197 ms 38564 KB Output is correct
45 Correct 176 ms 38412 KB Output is correct
46 Correct 199 ms 38564 KB Output is correct
47 Correct 338 ms 39048 KB Output is correct
48 Correct 13 ms 13132 KB Output is correct
49 Correct 39 ms 13140 KB Output is correct
50 Correct 143 ms 13272 KB Output is correct
51 Correct 258 ms 13616 KB Output is correct
52 Correct 94 ms 27712 KB Output is correct
53 Correct 142 ms 27720 KB Output is correct
54 Correct 325 ms 27948 KB Output is correct
55 Correct 574 ms 28560 KB Output is correct
56 Correct 591 ms 108672 KB Output is correct
57 Correct 619 ms 108836 KB Output is correct
58 Correct 965 ms 109008 KB Output is correct
59 Correct 1379 ms 109332 KB Output is correct
60 Correct 1177 ms 202780 KB Output is correct
61 Correct 1301 ms 202720 KB Output is correct
62 Correct 1759 ms 202968 KB Output is correct
63 Correct 2237 ms 203500 KB Output is correct
64 Correct 3008 ms 203164 KB Output is correct
65 Execution timed out 5098 ms 14796 KB Time limit exceeded
66 Halted 0 ms 0 KB -