oj.uz

답안 #478141

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
478141 2021-10-05T20:46:03 Z bonopo Dynamic Diameter (CEOI19_diameter) C++17
100 / 100
 3104 ms 121632 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], ct;
vector<pair<int,ll>> adj[MM]; ll av[MM], W; pair<ll,int> mp[MM];
multiset<ll> ast;

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

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

    inline void apply(int i, ll v) {
        seg[i].mx.f+=v;
        if(i<wt) seg[i].lz+=v;
    }

    inline void build(int p) {
        while(p>1) p>>=1, seg[p].mx=max(seg[p<<1].mx, seg[p<<1|1].mx), seg[p].mx.f+=seg[p].lz;
    }

    inline void push(int p) {
        for(int s=h; s>0; --s) {
            int i=p>>s;
            if (seg[i].lz!=0) {
                apply(lc, seg[i].lz);
                apply(rc, seg[i].lz);
                seg[i].lz=0;
            }
        }
    }

    inline void inc(int l, int r, ll value) {
        if(l>r) return;
        r++; l+=wt, r+=wt; int l0=l, r0=r;
        for (; l<r; l>>=1, r>>=1) {
            if(l&1) apply(l++, value);
            if(r&1) apply(--r, value); }
        build(l0); build(r0 - 1);
    }

    inline pair<ll,int> qry(int l, int r) {
        if(l>r) return {0,0};
        r++; l+=wt, r+=wt; push(l); push(r - 1);
        pair<ll,int> res=make_pair(0,0);
        for (; l<r; l>>=1, r>>=1) {
            if(l&1) res=max(res, seg[l++].mx);
            if(r&1) res=max(seg[--r].mx, res); }
        return res;
    }

    inline void construct() {
        for (int i=wt-1; i>0; --i) seg[i].mx=max(seg[lc].mx, seg[rc].mx);
    }

    inline void init(int n) {
        wt=n; h=64-__builtin_clzll((ll)n);
        seg.resize(2*n+1);
        for(int i=n; i<n+n; ++i) seg[i].mx=mp[i-n+1];
        construct();
    }
} st[MM];

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

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

void etr(int u, int fa, int lvl, int rt, int tv, ll ew) {
    in[lvl][u]=++ct; cp[lvl][u]=rt; tp[lvl][u]=tv; mp[ct]=make_pair(ew,u);
    for(auto &e:adj[u]) if(e.f!=fa&&!bk[e.f]) {
        etr(e.f, u, lvl, rt, tv, e.s+ew); }
    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;
    bk[rt]=true; ct=0;

    // get ett
    cp[lvl][rt]=tp[lvl][rt]=rt;
    for(auto &e:adj[rt]) if(!bk[e.f]) etr(e.f, rt, lvl, rt, e.f, e.s);
    if(ct==0) return;

    // construct tree
    st[rt].init(ct);
    auto x=st[rt].qry(0, ct-1); x.s=tp[lvl][x.s];
    auto y=max(st[rt].qry(0, in[lvl][x.s]-2), st[rt].qry(ot[lvl][x.s], ct-1));
    ast.insert(av[rt]=x.f+y.f);

    int tally=0, lv=-1;
    for(auto &e:adj[rt]) if(!bk[e.f]) {
        if(sz[e.f]<sz[rt]) {
            tally+=sz[e.f];
            rec(e.f, sz[e.f], rt, lvl+1); }
        else lv=e.f; }
    if(~lv) rec(lv, nds-tally-1, rt, lvl+1);
}

void qry(int u, int v, ll val) {
    int cur=0;
    while(cur<LOG-1&&cp[cur+1][u]==cp[cur+1][v]&&cp[cur+1][u]!=0) ++cur;

    int crt=cp[cur][u];
    while(cur>=0) {
        int w=(in[cur][u]>in[cur][v]?u:v), wt=st[crt].wt;
        st[crt].inc(in[cur][w]-1, ot[cur][w]-1, val);

        auto x=st[crt].qry(0, wt-1); x.s=tp[cur][x.s];
        auto y=max(st[crt].qry(0, in[cur][x.s]-2), st[crt].qry(ot[cur][x.s], wt-1));

        ll cnd=x.f+y.f;
        if(cnd!=av[crt]&&st[crt].wt>0) {
            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,w}); adj[v].pb({u,w});
        edg.pb({w,{u,v}}); }
    // preprocess
    rec(1, N);

    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 function 'void rec(int, int, int, int)':
diameter.cpp:102:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
  102 |     if(nds<=1) return; dfs(rt, 0);
      |     ^~
diameter.cpp:102:24: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  102 |     if(nds<=1) return; dfs(rt, 0);
      |                        ^~~

Subtask #1
11.0 / 11.0

# 결과 실행 시간 메모리 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 3 ms 5836 KB Output is correct
8 Correct 4 ms 5836 KB Output is correct
9 Correct 3 ms 5836 KB Output is correct
10 Correct 3 ms 5836 KB Output is correct
11 Correct 4 ms 5836 KB Output is correct
12 Correct 5 ms 5836 KB Output is correct
13 Correct 3 ms 5972 KB Output is correct
14 Correct 3 ms 5836 KB Output is correct
15 Correct 3 ms 5964 KB Output is correct
16 Correct 3 ms 5964 KB Output is correct
17 Correct 3 ms 5964 KB Output is correct
18 Correct 3 ms 5964 KB Output is correct

Subtask #2
13.0 / 13.0

# 결과 실행 시간 메모리 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 3 ms 5836 KB Output is correct
8 Correct 4 ms 5836 KB Output is correct
9 Correct 3 ms 5836 KB Output is correct
10 Correct 3 ms 5836 KB Output is correct
11 Correct 4 ms 5836 KB Output is correct
12 Correct 5 ms 5836 KB Output is correct
13 Correct 3 ms 5972 KB Output is correct
14 Correct 3 ms 5836 KB Output is correct
15 Correct 3 ms 5964 KB Output is correct
16 Correct 3 ms 5964 KB Output is correct
17 Correct 3 ms 5964 KB Output is correct
18 Correct 3 ms 5964 KB Output is correct
19 Correct 23 ms 6620 KB Output is correct
20 Correct 19 ms 6580 KB Output is correct
21 Correct 22 ms 6628 KB Output is correct
22 Correct 25 ms 6748 KB Output is correct
23 Correct 32 ms 8796 KB Output is correct
24 Correct 39 ms 9472 KB Output is correct
25 Correct 38 ms 9792 KB Output is correct
26 Correct 46 ms 10444 KB Output is correct

Subtask #3
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 5836 KB Output is correct
2 Correct 3 ms 5892 KB Output is correct
3 Correct 5 ms 5836 KB Output is correct
4 Correct 17 ms 5908 KB Output is correct
5 Correct 51 ms 6164 KB Output is correct
6 Correct 3 ms 5836 KB Output is correct
7 Correct 3 ms 5836 KB Output is correct
8 Correct 3 ms 5836 KB Output is correct
9 Correct 4 ms 5836 KB Output is correct
10 Correct 17 ms 5964 KB Output is correct
11 Correct 65 ms 6336 KB Output is correct
12 Correct 6 ms 6604 KB Output is correct
13 Correct 5 ms 6604 KB Output is correct
14 Correct 7 ms 6604 KB Output is correct
15 Correct 23 ms 6760 KB Output is correct
16 Correct 97 ms 7104 KB Output is correct
17 Correct 45 ms 20328 KB Output is correct
18 Correct 40 ms 20224 KB Output is correct
19 Correct 45 ms 20284 KB Output is correct
20 Correct 64 ms 20400 KB Output is correct
21 Correct 150 ms 20808 KB Output is correct

Subtask #4
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 6604 KB Output is correct
2 Correct 31 ms 6616 KB Output is correct
3 Correct 125 ms 6820 KB Output is correct
4 Correct 245 ms 7064 KB Output is correct
5 Correct 21 ms 13980 KB Output is correct
6 Correct 60 ms 14024 KB Output is correct
7 Correct 252 ms 14300 KB Output is correct
8 Correct 508 ms 14644 KB Output is correct
9 Correct 87 ms 53172 KB Output is correct
10 Correct 163 ms 53188 KB Output is correct
11 Correct 491 ms 53388 KB Output is correct
12 Correct 888 ms 53864 KB Output is correct
13 Correct 184 ms 106392 KB Output is correct
14 Correct 257 ms 106256 KB Output is correct
15 Correct 687 ms 106708 KB Output is correct
16 Correct 1274 ms 106888 KB Output is correct
17 Correct 2121 ms 106792 KB Output is correct

Subtask #5
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1698 ms 89828 KB Output is correct
2 Correct 1916 ms 92308 KB Output is correct
3 Correct 1745 ms 90740 KB Output is correct
4 Correct 1801 ms 92744 KB Output is correct
5 Correct 1741 ms 87688 KB Output is correct
6 Correct 1498 ms 69548 KB Output is correct
7 Correct 2478 ms 112692 KB Output is correct
8 Correct 2411 ms 112588 KB Output is correct
9 Correct 2398 ms 112464 KB Output is correct
10 Correct 2360 ms 112036 KB Output is correct
11 Correct 2342 ms 107120 KB Output is correct
12 Correct 2132 ms 82016 KB Output is correct
13 Correct 3025 ms 121416 KB Output is correct
14 Correct 3047 ms 121592 KB Output is correct
15 Correct 2935 ms 121612 KB Output is correct
16 Correct 2957 ms 121280 KB Output is correct
17 Correct 2921 ms 115764 KB Output is correct
18 Correct 2440 ms 86372 KB Output is correct
19 Correct 2972 ms 121612 KB Output is correct
20 Correct 3104 ms 121632 KB Output is correct
21 Correct 2968 ms 121504 KB Output is correct
22 Correct 3001 ms 121264 KB Output is correct
23 Correct 2878 ms 115816 KB Output is correct
24 Correct 2450 ms 86396 KB Output is correct

Subtask #6
27.0 / 27.0

# 결과 실행 시간 메모리 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 3 ms 5836 KB Output is correct
8 Correct 4 ms 5836 KB Output is correct
9 Correct 3 ms 5836 KB Output is correct
10 Correct 3 ms 5836 KB Output is correct
11 Correct 4 ms 5836 KB Output is correct
12 Correct 5 ms 5836 KB Output is correct
13 Correct 3 ms 5972 KB Output is correct
14 Correct 3 ms 5836 KB Output is correct
15 Correct 3 ms 5964 KB Output is correct
16 Correct 3 ms 5964 KB Output is correct
17 Correct 3 ms 5964 KB Output is correct
18 Correct 3 ms 5964 KB Output is correct
19 Correct 23 ms 6620 KB Output is correct
20 Correct 19 ms 6580 KB Output is correct
21 Correct 22 ms 6628 KB Output is correct
22 Correct 25 ms 6748 KB Output is correct
23 Correct 32 ms 8796 KB Output is correct
24 Correct 39 ms 9472 KB Output is correct
25 Correct 38 ms 9792 KB Output is correct
26 Correct 46 ms 10444 KB Output is correct
27 Correct 2 ms 5836 KB Output is correct
28 Correct 3 ms 5892 KB Output is correct
29 Correct 5 ms 5836 KB Output is correct
30 Correct 17 ms 5908 KB Output is correct
31 Correct 51 ms 6164 KB Output is correct
32 Correct 3 ms 5836 KB Output is correct
33 Correct 3 ms 5836 KB Output is correct
34 Correct 3 ms 5836 KB Output is correct
35 Correct 4 ms 5836 KB Output is correct
36 Correct 17 ms 5964 KB Output is correct
37 Correct 65 ms 6336 KB Output is correct
38 Correct 6 ms 6604 KB Output is correct
39 Correct 5 ms 6604 KB Output is correct
40 Correct 7 ms 6604 KB Output is correct
41 Correct 23 ms 6760 KB Output is correct
42 Correct 97 ms 7104 KB Output is correct
43 Correct 45 ms 20328 KB Output is correct
44 Correct 40 ms 20224 KB Output is correct
45 Correct 45 ms 20284 KB Output is correct
46 Correct 64 ms 20400 KB Output is correct
47 Correct 150 ms 20808 KB Output is correct
48 Correct 6 ms 6604 KB Output is correct
49 Correct 31 ms 6616 KB Output is correct
50 Correct 125 ms 6820 KB Output is correct
51 Correct 245 ms 7064 KB Output is correct
52 Correct 21 ms 13980 KB Output is correct
53 Correct 60 ms 14024 KB Output is correct
54 Correct 252 ms 14300 KB Output is correct
55 Correct 508 ms 14644 KB Output is correct
56 Correct 87 ms 53172 KB Output is correct
57 Correct 163 ms 53188 KB Output is correct
58 Correct 491 ms 53388 KB Output is correct
59 Correct 888 ms 53864 KB Output is correct
60 Correct 184 ms 106392 KB Output is correct
61 Correct 257 ms 106256 KB Output is correct
62 Correct 687 ms 106708 KB Output is correct
63 Correct 1274 ms 106888 KB Output is correct
64 Correct 2121 ms 106792 KB Output is correct
65 Correct 1698 ms 89828 KB Output is correct
66 Correct 1916 ms 92308 KB Output is correct
67 Correct 1745 ms 90740 KB Output is correct
68 Correct 1801 ms 92744 KB Output is correct
69 Correct 1741 ms 87688 KB Output is correct
70 Correct 1498 ms 69548 KB Output is correct
71 Correct 2478 ms 112692 KB Output is correct
72 Correct 2411 ms 112588 KB Output is correct
73 Correct 2398 ms 112464 KB Output is correct
74 Correct 2360 ms 112036 KB Output is correct
75 Correct 2342 ms 107120 KB Output is correct
76 Correct 2132 ms 82016 KB Output is correct
77 Correct 3025 ms 121416 KB Output is correct
78 Correct 3047 ms 121592 KB Output is correct
79 Correct 2935 ms 121612 KB Output is correct
80 Correct 2957 ms 121280 KB Output is correct
81 Correct 2921 ms 115764 KB Output is correct
82 Correct 2440 ms 86372 KB Output is correct
83 Correct 2972 ms 121612 KB Output is correct
84 Correct 3104 ms 121632 KB Output is correct
85 Correct 2968 ms 121504 KB Output is correct
86 Correct 3001 ms 121264 KB Output is correct
87 Correct 2878 ms 115816 KB Output is correct
88 Correct 2450 ms 86396 KB Output is correct
89 Correct 1731 ms 91028 KB Output is correct
90 Correct 1927 ms 100352 KB Output is correct
91 Correct 2217 ms 109592 KB Output is correct
92 Correct 2432 ms 112380 KB Output is correct
93 Correct 2611 ms 116256 KB Output is correct
94 Correct 2713 ms 118632 KB Output is correct
95 Correct 2949 ms 121340 KB Output is correct
96 Correct 3029 ms 121324 KB Output is correct
97 Correct 2926 ms 121556 KB Output is correct
98 Correct 3038 ms 121560 KB Output is correct
99 Correct 2973 ms 121632 KB Output is correct
100 Correct 2913 ms 121460 KB Output is correct