oj.uz

답안 #971982

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
971982 2024-04-29T16:13:23 Z efedmrlr Dynamic Diameter (CEOI19_diameter) C++17
100 / 100
 4458 ms 270808 KB 
#include <bits/stdc++.h>
#define int long long int
#define lli int
#define pb push_back
#define MP make_pair
#define ld long double
#define REP(i, n) for(int i = 0; (i) < (n); (i)++)
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()

using namespace std;

void fastio() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
}

const int N = 1e5 + 5;
const int INF = 1e9 + 500;
const int LGN = 18;

struct SegT {
    vector<lli> st, tag;
    int n;
    void build(int tl, int tr, int v, vector<lli> &x) {
        if(tl == tr) {
            st[v] = x[tl];
            return;
        }
        int tm = (tl + tr) >> 1;
        build(tl, tm, v << 1, x);
        build(tm + 1, tr, v << 1 ^ 1, x);
        st[v] = max(st[v << 1], st[v << 1 ^ 1]);
    }
    void reset(int nn) {
        n = nn;
        st.assign(4*(n + 3), 0);
        tag.assign(4*(n + 3), 0);
    }
    void push(int v) {
        st[v << 1] += tag[v];
        st[v << 1 ^ 1] += tag[v];

        tag[v << 1] += tag[v];
        tag[v << 1 ^ 1] += tag[v];
        tag[v] = 0;
    }
    void update(int tl, int tr, int v, int l, int r, int val) {
        if(tl >= l && tr <= r) {
            st[v] += val;
            tag[v] += val;
            return;
        }
        if(tl > r || tr < l) {
            return;
        }
        push(v);
        int tm = (tl + tr) >> 1;
        update(tl, tm, v << 1, l, r, val);
        update(tm + 1, tr, v << 1 ^ 1, l, r, val);
        st[v] = max(st[v << 1], st[v << 1 ^ 1]);
    }
    void update(int l, int r, int val) {
        update(0, n, 1, l, r, val);
    }
    lli query(int tl, int tr, int v, int l, int r) {
        if(tl >= l && tr <= r) {
            return st[v];
        }
        if(tl > r || tr < l) {
            return 0;
        }
        push(v);
        int tm = (tl + tr) >> 1;
        return max(query(tl, tm, v << 1, l, r), query(tm + 1, tr, v << 1 ^ 1, l, r));
    }
    lli query(int l, int r) {
        return query(0, n, 1, l, r);
    }
};
int n = 0, q = 0, w = 0;
vector<vector<array<int, 2> > > adj(N, vector<array<int, 2> >());
vector<array<int, 3> > edg;
vector<int> sub(N, 0);
vector<int> vis(N, 0);
array<SegT, LGN> st;
vector<array<int, LGN> > cent(N);
vector<array<int, LGN> > tin(N), p(N), ssz(N);
vector<array<int, LGN> > comp(N);
vector<array<int, LGN> > edgnode(N);
array<int, LGN> tim;
array<vector<lli>, LGN> arr;
vector<set<array<lli, 2>, greater<array<lli, 2> > > > cand(N, set<array<lli, 2>, greater<array<lli, 2> > >());
vector<vector<array<lli, 2> > > cent_adj(N, vector<array<lli, 2> >());
set<array<lli, 2>, greater<array<lli, 2> > > anss;
vector<int> lv(N, 0);
vector<lli> cent_res(N, 0);
void dfssz(int node, int par) {
    sub[node] = 1;
    for(auto c : adj[node]) {
        if(c[0] == par || vis[c[0]]) {
            continue;
        }
        dfssz(c[0], node);
        sub[node] += sub[c[0]];
    }
}
int get_cent(int node, int par, int tar) {
    for(auto c : adj[node]) {
        if(c[0] == par || vis[c[0]]) continue;
        if(sub[c[0]] * 2 > tar) {
            return get_cent(c[0], node, tar);
        }
    }
    return node;
}
void prec(int node, int par, int lvl, int centro) {
    ssz[node][lvl] = 1;
    tin[node][lvl] = tim[lvl]++;
    cent[node][lvl] = centro;
    for(auto &c : adj[node]) {
        if(c[0] == par || vis[c[0]]) continue;
        p[c[0]][lvl] = node;
        edgnode[c[1]][lvl] = c[0];
        prec(c[0], node, lvl, centro);
        ssz[node][lvl] += ssz[c[0]][lvl];
    }

}
void prec2(int node, int par, int lvl, int g) {
    comp[node][lvl] = g;
    for(auto c : adj[node]) {
        if(c[0] == par || vis[c[0]]) continue;
        prec2(c[0], node, lvl, g);
    }
}
void prec3(int node, int par, int lvl) {

    for(auto c : adj[node]) {
        if(c[0] == par || vis[c[0]]) continue;
        arr[lvl][tin[c[0]][lvl]] = arr[lvl][tin[node][lvl]] + edg[c[1]][2];
        prec3(c[0], node, lvl);
    }
}
void centroid_decomp(int node, int lvl) {
    dfssz(node, 0);
    int centro = get_cent(node, 0, sub[node]);
    lv[centro] = lvl;
    p[centro][lvl] = 0;
    prec(centro, 0, lvl, centro);
    for(auto c : adj[centro]) {
        if(vis[c[0]]) continue;
        cent_adj[centro].pb({c[0], 0});
        prec2(c[0], centro, lvl, c[0]);
    }
    arr[lvl][tin[centro][lvl]] = 0;
    prec3(centro, 0, lvl);
    vis[centro] = 1;
    for(auto c : adj[centro]) {
        if(vis[c[0]]) continue;
        centroid_decomp(c[0], lvl + 1);
    }
}

void solve() {
    REP(i, LGN) {
        tim[i] = 0;
        arr[i].assign(N, 0);
        REP(j, N) edgnode[j][i] = -1;
    }
    cin >> n >> q >> w;
    
    edg.resize(n - 1);
    REP(i, n - 1) {
        cin >> edg[i][0] >> edg[i][1] >> edg[i][2];
        adj[edg[i][0]].pb({edg[i][1], i});
        adj[edg[i][1]].pb({edg[i][0], i});
    }
    centroid_decomp(1, 0);
    REP(i, LGN) {
        st[i].reset(n + 1);
        st[i].build(0, st[i].n, 1, arr[i]);
    }
    for(int i = 1; i <= n; i++) {
        sort(all(cent_adj[i]));
        for(auto &c : cent_adj[i]) {
            lli v = st[lv[i]].query(tin[c[0]][lv[i]], tin[c[0]][lv[i]] + ssz[c[0]][lv[i]] - 1);
            cand[i].insert({v, c[0]});
            c[1] = v;
        }
        cand[i].insert({0, -1});
        cand[i].insert({0, -2});
        cent_res[i] = (*cand[i].begin())[0] + (*next(cand[i].begin()))[0];
        anss.insert({cent_res[i], i});
    }
 
    // for(int i = 1; i <= n; i++) {
    //     cout << "i:" << i << "\n";
    //     for(auto c : cent_adj[i]) {
    //         cout << c[0] << " " << c[1] << "\n";
    //     }
    // }
    lli last = 0;
    REP(z, q) {
        int d, e;
        cin >> d >> e;
        d = (int)((1ll * d + last) % (n - 1));
        e = (int)((1ll * e + last) % w);
        // cout << "d:" << d <<" e:" << e << "\n";
        for(int i = 0; i < LGN; i++) {
            if(edgnode[d][i] == -1) continue;
            // cout << "level:" << i << "\n";
            int node = edgnode[d][i];
            int centr = cent[node][i];
            int rep = comp[node][i];
            auto itr = lower_bound(all(cent_adj[centr]), array<lli, 2>({rep, 0}));
            
            // if(rep != (*itr)[0]) {
            //     itr--;
            //     cerr << (*itr)[0] << "REP" << (*itr)[1] << endl;
            // }
            // cout << "node :" << node << " centr:" << centr << " rep:" << rep << " ";
            cand[centr].erase({(*itr)[1], rep});
            st[i].update(tin[node][i], tin[node][i] + ssz[node][i] - 1, e - edg[d][2]);
            // cout << "old val: " << (*itr)[1] << " ";   
            (*itr)[1] = st[i].query(tin[rep][i], tin[rep][i] + ssz[rep][i] - 1);
            // cout << "new val: " << (*itr)[1] << "\n";
            cand[centr].insert({(*itr)[1], rep});
            
            anss.erase({cent_res[centr], centr});
            cent_res[centr] = (*cand[centr].begin())[0] + (*next(cand[centr].begin()))[0];
            anss.insert({cent_res[centr], centr});
        }
        edg[d][2] = e;
        // cout << "centro:" << (*anss.begin())[1] << " lvl:" << lv[(*anss.begin())[1]] << "\n";
        last = (*anss.begin())[0];
        cout << last << "\n";
    }

}

signed main() {
    fastio();
    solve();
}

Subtask #1
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 47 ms 111444 KB Output is correct
2 Correct 31 ms 111708 KB Output is correct
3 Correct 30 ms 111708 KB Output is correct
4 Correct 29 ms 111520 KB Output is correct
5 Correct 28 ms 111704 KB Output is correct
6 Correct 30 ms 111684 KB Output is correct
7 Correct 28 ms 111696 KB Output is correct
8 Correct 29 ms 111708 KB Output is correct
9 Correct 33 ms 111700 KB Output is correct
10 Correct 29 ms 111696 KB Output is correct
11 Correct 29 ms 111708 KB Output is correct
12 Correct 37 ms 111716 KB Output is correct
13 Correct 29 ms 111696 KB Output is correct
14 Correct 29 ms 111820 KB Output is correct
15 Correct 30 ms 111704 KB Output is correct
16 Correct 35 ms 111700 KB Output is correct
17 Correct 28 ms 111696 KB Output is correct
18 Correct 29 ms 111696 KB Output is correct

Subtask #2
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 47 ms 111444 KB Output is correct
2 Correct 31 ms 111708 KB Output is correct
3 Correct 30 ms 111708 KB Output is correct
4 Correct 29 ms 111520 KB Output is correct
5 Correct 28 ms 111704 KB Output is correct
6 Correct 30 ms 111684 KB Output is correct
7 Correct 28 ms 111696 KB Output is correct
8 Correct 29 ms 111708 KB Output is correct
9 Correct 33 ms 111700 KB Output is correct
10 Correct 29 ms 111696 KB Output is correct
11 Correct 29 ms 111708 KB Output is correct
12 Correct 37 ms 111716 KB Output is correct
13 Correct 29 ms 111696 KB Output is correct
14 Correct 29 ms 111820 KB Output is correct
15 Correct 30 ms 111704 KB Output is correct
16 Correct 35 ms 111700 KB Output is correct
17 Correct 28 ms 111696 KB Output is correct
18 Correct 29 ms 111696 KB Output is correct
19 Correct 46 ms 113232 KB Output is correct
20 Correct 48 ms 113236 KB Output is correct
21 Correct 50 ms 113232 KB Output is correct
22 Correct 57 ms 113508 KB Output is correct
23 Correct 69 ms 119108 KB Output is correct
24 Correct 70 ms 119192 KB Output is correct
25 Correct 78 ms 119376 KB Output is correct
26 Correct 84 ms 119644 KB Output is correct

Subtask #3
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 29 ms 111568 KB Output is correct
2 Correct 30 ms 111820 KB Output is correct
3 Correct 30 ms 111696 KB Output is correct
4 Correct 40 ms 111756 KB Output is correct
5 Correct 81 ms 111952 KB Output is correct
6 Correct 29 ms 111632 KB Output is correct
7 Correct 29 ms 112208 KB Output is correct
8 Correct 29 ms 112344 KB Output is correct
9 Correct 32 ms 112208 KB Output is correct
10 Correct 47 ms 112464 KB Output is correct
11 Correct 113 ms 112724 KB Output is correct
12 Correct 35 ms 119060 KB Output is correct
13 Correct 36 ms 119036 KB Output is correct
14 Correct 43 ms 119124 KB Output is correct
15 Correct 60 ms 119132 KB Output is correct
16 Correct 150 ms 119636 KB Output is correct
17 Correct 204 ms 258104 KB Output is correct
18 Correct 211 ms 258024 KB Output is correct
19 Correct 193 ms 258148 KB Output is correct
20 Correct 242 ms 258352 KB Output is correct
21 Correct 463 ms 258748 KB Output is correct

Subtask #4
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 32 ms 112988 KB Output is correct
2 Correct 59 ms 113192 KB Output is correct
3 Correct 172 ms 113404 KB Output is correct
4 Correct 307 ms 114524 KB Output is correct
5 Correct 52 ms 126552 KB Output is correct
6 Correct 97 ms 126804 KB Output is correct
7 Correct 298 ms 127496 KB Output is correct
8 Correct 587 ms 128188 KB Output is correct
9 Correct 158 ms 186336 KB Output is correct
10 Correct 271 ms 186428 KB Output is correct
11 Correct 686 ms 187556 KB Output is correct
12 Correct 1172 ms 188244 KB Output is correct
13 Correct 268 ms 261200 KB Output is correct
14 Correct 396 ms 261396 KB Output is correct
15 Correct 867 ms 262408 KB Output is correct
16 Correct 1545 ms 263448 KB Output is correct
17 Correct 3341 ms 263004 KB Output is correct

Subtask #5
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2595 ms 263572 KB Output is correct
2 Correct 2567 ms 263592 KB Output is correct
3 Correct 2514 ms 263644 KB Output is correct
4 Correct 2663 ms 263668 KB Output is correct
5 Correct 2541 ms 263300 KB Output is correct
6 Correct 2243 ms 262792 KB Output is correct
7 Correct 3507 ms 265572 KB Output is correct
8 Correct 3713 ms 265480 KB Output is correct
9 Correct 3724 ms 265652 KB Output is correct
10 Correct 3570 ms 266188 KB Output is correct
11 Correct 3401 ms 265244 KB Output is correct
12 Correct 3206 ms 265328 KB Output is correct
13 Correct 4270 ms 269392 KB Output is correct
14 Correct 4110 ms 269468 KB Output is correct
15 Correct 4458 ms 269528 KB Output is correct
16 Correct 4347 ms 269336 KB Output is correct
17 Correct 4197 ms 268748 KB Output is correct
18 Correct 3686 ms 266504 KB Output is correct
19 Correct 4112 ms 269268 KB Output is correct
20 Correct 3957 ms 269428 KB Output is correct
21 Correct 3941 ms 269660 KB Output is correct
22 Correct 4094 ms 269412 KB Output is correct
23 Correct 3929 ms 268540 KB Output is correct
24 Correct 3342 ms 266248 KB Output is correct

Subtask #6
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 47 ms 111444 KB Output is correct
2 Correct 31 ms 111708 KB Output is correct
3 Correct 30 ms 111708 KB Output is correct
4 Correct 29 ms 111520 KB Output is correct
5 Correct 28 ms 111704 KB Output is correct
6 Correct 30 ms 111684 KB Output is correct
7 Correct 28 ms 111696 KB Output is correct
8 Correct 29 ms 111708 KB Output is correct
9 Correct 33 ms 111700 KB Output is correct
10 Correct 29 ms 111696 KB Output is correct
11 Correct 29 ms 111708 KB Output is correct
12 Correct 37 ms 111716 KB Output is correct
13 Correct 29 ms 111696 KB Output is correct
14 Correct 29 ms 111820 KB Output is correct
15 Correct 30 ms 111704 KB Output is correct
16 Correct 35 ms 111700 KB Output is correct
17 Correct 28 ms 111696 KB Output is correct
18 Correct 29 ms 111696 KB Output is correct
19 Correct 46 ms 113232 KB Output is correct
20 Correct 48 ms 113236 KB Output is correct
21 Correct 50 ms 113232 KB Output is correct
22 Correct 57 ms 113508 KB Output is correct
23 Correct 69 ms 119108 KB Output is correct
24 Correct 70 ms 119192 KB Output is correct
25 Correct 78 ms 119376 KB Output is correct
26 Correct 84 ms 119644 KB Output is correct
27 Correct 29 ms 111568 KB Output is correct
28 Correct 30 ms 111820 KB Output is correct
29 Correct 30 ms 111696 KB Output is correct
30 Correct 40 ms 111756 KB Output is correct
31 Correct 81 ms 111952 KB Output is correct
32 Correct 29 ms 111632 KB Output is correct
33 Correct 29 ms 112208 KB Output is correct
34 Correct 29 ms 112344 KB Output is correct
35 Correct 32 ms 112208 KB Output is correct
36 Correct 47 ms 112464 KB Output is correct
37 Correct 113 ms 112724 KB Output is correct
38 Correct 35 ms 119060 KB Output is correct
39 Correct 36 ms 119036 KB Output is correct
40 Correct 43 ms 119124 KB Output is correct
41 Correct 60 ms 119132 KB Output is correct
42 Correct 150 ms 119636 KB Output is correct
43 Correct 204 ms 258104 KB Output is correct
44 Correct 211 ms 258024 KB Output is correct
45 Correct 193 ms 258148 KB Output is correct
46 Correct 242 ms 258352 KB Output is correct
47 Correct 463 ms 258748 KB Output is correct
48 Correct 32 ms 112988 KB Output is correct
49 Correct 59 ms 113192 KB Output is correct
50 Correct 172 ms 113404 KB Output is correct
51 Correct 307 ms 114524 KB Output is correct
52 Correct 52 ms 126552 KB Output is correct
53 Correct 97 ms 126804 KB Output is correct
54 Correct 298 ms 127496 KB Output is correct
55 Correct 587 ms 128188 KB Output is correct
56 Correct 158 ms 186336 KB Output is correct
57 Correct 271 ms 186428 KB Output is correct
58 Correct 686 ms 187556 KB Output is correct
59 Correct 1172 ms 188244 KB Output is correct
60 Correct 268 ms 261200 KB Output is correct
61 Correct 396 ms 261396 KB Output is correct
62 Correct 867 ms 262408 KB Output is correct
63 Correct 1545 ms 263448 KB Output is correct
64 Correct 3341 ms 263004 KB Output is correct
65 Correct 2595 ms 263572 KB Output is correct
66 Correct 2567 ms 263592 KB Output is correct
67 Correct 2514 ms 263644 KB Output is correct
68 Correct 2663 ms 263668 KB Output is correct
69 Correct 2541 ms 263300 KB Output is correct
70 Correct 2243 ms 262792 KB Output is correct
71 Correct 3507 ms 265572 KB Output is correct
72 Correct 3713 ms 265480 KB Output is correct
73 Correct 3724 ms 265652 KB Output is correct
74 Correct 3570 ms 266188 KB Output is correct
75 Correct 3401 ms 265244 KB Output is correct
76 Correct 3206 ms 265328 KB Output is correct
77 Correct 4270 ms 269392 KB Output is correct
78 Correct 4110 ms 269468 KB Output is correct
79 Correct 4458 ms 269528 KB Output is correct
80 Correct 4347 ms 269336 KB Output is correct
81 Correct 4197 ms 268748 KB Output is correct
82 Correct 3686 ms 266504 KB Output is correct
83 Correct 4112 ms 269268 KB Output is correct
84 Correct 3957 ms 269428 KB Output is correct
85 Correct 3941 ms 269660 KB Output is correct
86 Correct 4094 ms 269412 KB Output is correct
87 Correct 3929 ms 268540 KB Output is correct
88 Correct 3342 ms 266248 KB Output is correct
89 Correct 2577 ms 264060 KB Output is correct
90 Correct 2923 ms 264728 KB Output is correct
91 Correct 3337 ms 265704 KB Output is correct
92 Correct 3351 ms 266412 KB Output is correct
93 Correct 3526 ms 267704 KB Output is correct
94 Correct 3758 ms 268524 KB Output is correct
95 Correct 4152 ms 268768 KB Output is correct
96 Correct 3971 ms 268240 KB Output is correct
97 Correct 4014 ms 268908 KB Output is correct
98 Correct 4005 ms 270808 KB Output is correct
99 Correct 3910 ms 268556 KB Output is correct
100 Correct 3932 ms 268356 KB Output is correct