oj.uz

답안 #637920

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
637920 2022-09-03T15:17:34 Z MohamedFaresNebili Dynamic Diameter (CEOI19_diameter) C++14
100 / 100
 3407 ms 188028 KB 
#include <bits/stdc++.h>
#pragma GCC optimize ("Ofast")
#pragma GCC target ("avx2")

            using namespace std;
            using ll = long long;

            #define int ll

            struct seg
            {
                int N; vector<int> st, lazy;
                seg() {}
                void init(int _N) {
                    N = _N;
                    st.resize(4 * N, 0);
                    lazy.resize(4 * N, 0);
                }
                void prop(int v, int l, int r) {
                    if(l == r || lazy[v] == 0) return;
                    st[v * 2] += lazy[v];
                    st[v * 2 + 1] += lazy[v];
                    lazy[v * 2] += lazy[v];
                    lazy[v * 2 + 1] += lazy[v];
                    lazy[v] = 0;
                }
                void update(int v, int l, int r, int lo, int hi, int val) {
                    if(l > hi || r < lo) return;
                    if(l >= lo && r <= hi) {
                        st[v] += val; lazy[v] += val;
                        return;
                    }
                    prop(v, l, r);
                    update(v * 2, l, (l + r) / 2, lo, hi, val);
                    update(v * 2 + 1, (l + r) / 2 + 1, r, lo, hi, val);
                    st[v] = max(st[v * 2], st[v * 2 + 1]);
                }
                int query(int v, int l, int r, int lo, int hi) {
                    if(l > hi || r < lo) return 0;
                    if(l >= lo && r <= hi) return st[v];
                    prop(v, l, r);
                    return max(query(v * 2, l, (l + r) / 2, lo, hi),
                               query(v * 2 + 1, (l + r) / 2 + 1, r, lo, hi));
                }
            };

            int N, Q, W, S[100005]; seg ST[100005];
            int A[100005], B[100005], C[100005];
            int par[100005], tin[100005], out[100005];
            vector<int> adj[100005], cur[100005];
            vector<pair<int, int>> G[100005];
            vector<array<int, 3>> E[100005];
            set<pair<int, int>> ans[100005];
            set<pair<int, int>> best;
            int timer; vector<int> K;
            bool rem[100005];

            int dfs_size(int v, int p) {
                S[v] = 1;
                for(auto e : adj[v]) {
                    int u = A[e] ^ B[e] ^ v;
                    if(u == p || rem[u]) continue;
                    S[v] += dfs_size(u, v);
                }
                return S[v];
            }
            int dfs_centroid(int v, int p, int _N) {
                for(auto e : adj[v]) {
                    int u = A[e] ^ B[e] ^ v;
                    if(u == p || rem[u]) continue;
                    if(S[u] * 2 > _N)
                        return dfs_centroid(u, v, _N);
                }
                return v;
            }
            void dfs(int v, int p) {
                K.push_back(v); tin[v] = timer++;
                for(auto e : adj[v]) {
                    int u = A[e] ^ B[e] ^ v;
                    if(u == p || rem[u]) continue;
                    par[u] = e; dfs(u, v);
                }
                out[v] = timer - 1;
            }
            void get(int v, int state) {
                auto it = ans[v].rbegin();
                int res = (*it).first;
                if(ans[v].size() > 1) {
                    it++; res += (*it).first;
                }
                if(state) best.insert({res, v});
                else best.erase({res, v});
            }
            void build(int v) {
                int _N = dfs_size(v, v);
                if(_N == 1) return;
                int centroid = dfs_centroid(v, v, _N);
                K.clear(); ST[centroid].init(_N); timer = 0;
                par[centroid] = -1; dfs(centroid, centroid);
                for(auto u : K) {
                    if(par[u] == -1) continue;
                    E[par[u]].push_back({tin[u], out[u], centroid});
                    ST[centroid].update(1, 0, _N - 1, tin[u], out[u], C[par[u]]);
                }
                int group = 0;
                for(auto e : adj[centroid]) {
                    int u = A[e] ^ B[e] ^ centroid;
                    if(rem[u]) continue;
                    G[centroid].push_back({tin[u], out[u]});
                    int calc = ST[centroid].query(1, 0, _N - 1, tin[u], out[u]);
                    cur[centroid].push_back(calc);
                    ans[centroid].insert({calc, group++});
                }
                get(centroid, 1); rem[centroid] = 1;
                for(auto e : adj[centroid]) {
                    int u = A[e] ^ B[e] ^ centroid;
                    if(rem[u]) continue;
                    build(u);
                }
            }
            void upd(int I, int O, int D, int M) {
                int lo = 0, hi = G[D].size() - 1, res = 0;
                while(lo <= hi) {
                    int md = (lo + hi) / 2;
                    if(G[D][md].second < I)
                        lo = md + 1;
                    else hi = md - 1, res = md;
                }
                get(D, 0); ans[D].erase({cur[D][res], res});
                ST[D].update(1, 0, ST[D].N - 1, I, O, M);
                cur[D][res] = ST[D].query(1, 0, ST[D].N - 1, G[D][res].first, G[D][res].second);
                ans[D].insert({cur[D][res], res}); get(D, 1);
            }

            int32_t main() {
                ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
                cin >> N >> Q >> W;
                for(int l = 1; l < N; l++) {
                    cin >> A[l] >> B[l] >> C[l];
                    adj[A[l]].push_back(l);
                    adj[B[l]].push_back(l);
                }
                build(1); int last = 0;
                for(int l = 0; l < Q; l++) {
                    int d, e; cin >> d >> e;
                    d = (d + last) % (N - 1) + 1;
                    e = (e + last) % W;
                    for(auto u : E[d])
                        upd(u[0], u[1], u[2], e - C[d]);
                    C[d] = e; last = (*best.rbegin()).first;
                    cout << last << '\n';
                }
                return 0;
            }

Subtask #1
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 19936 KB Output is correct
2 Correct 11 ms 19836 KB Output is correct
3 Correct 12 ms 19880 KB Output is correct
4 Correct 11 ms 19936 KB Output is correct
5 Correct 14 ms 19916 KB Output is correct
6 Correct 14 ms 19840 KB Output is correct
7 Correct 11 ms 19900 KB Output is correct
8 Correct 11 ms 19924 KB Output is correct
9 Correct 12 ms 19924 KB Output is correct
10 Correct 12 ms 19912 KB Output is correct
11 Correct 11 ms 19924 KB Output is correct
12 Correct 10 ms 19924 KB Output is correct
13 Correct 10 ms 19908 KB Output is correct
14 Correct 13 ms 19912 KB Output is correct
15 Correct 12 ms 19972 KB Output is correct
16 Correct 11 ms 19904 KB Output is correct
17 Correct 11 ms 19904 KB Output is correct
18 Correct 11 ms 19912 KB Output is correct

Subtask #2
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 19936 KB Output is correct
2 Correct 11 ms 19836 KB Output is correct
3 Correct 12 ms 19880 KB Output is correct
4 Correct 11 ms 19936 KB Output is correct
5 Correct 14 ms 19916 KB Output is correct
6 Correct 14 ms 19840 KB Output is correct
7 Correct 11 ms 19900 KB Output is correct
8 Correct 11 ms 19924 KB Output is correct
9 Correct 12 ms 19924 KB Output is correct
10 Correct 12 ms 19912 KB Output is correct
11 Correct 11 ms 19924 KB Output is correct
12 Correct 10 ms 19924 KB Output is correct
13 Correct 10 ms 19908 KB Output is correct
14 Correct 13 ms 19912 KB Output is correct
15 Correct 12 ms 19972 KB Output is correct
16 Correct 11 ms 19904 KB Output is correct
17 Correct 11 ms 19904 KB Output is correct
18 Correct 11 ms 19912 KB Output is correct
19 Correct 29 ms 20692 KB Output is correct
20 Correct 32 ms 20808 KB Output is correct
21 Correct 36 ms 20896 KB Output is correct
22 Correct 40 ms 21072 KB Output is correct
23 Correct 55 ms 24192 KB Output is correct
24 Correct 66 ms 25192 KB Output is correct
25 Correct 72 ms 25892 KB Output is correct
26 Correct 80 ms 26912 KB Output is correct

Subtask #3
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 19924 KB Output is correct
2 Correct 12 ms 19924 KB Output is correct
3 Correct 11 ms 19924 KB Output is correct
4 Correct 23 ms 20052 KB Output is correct
5 Correct 74 ms 20616 KB Output is correct
6 Correct 12 ms 19912 KB Output is correct
7 Correct 11 ms 20052 KB Output is correct
8 Correct 13 ms 20020 KB Output is correct
9 Correct 14 ms 20044 KB Output is correct
10 Correct 34 ms 20216 KB Output is correct
11 Correct 99 ms 20780 KB Output is correct
12 Correct 16 ms 21460 KB Output is correct
13 Correct 16 ms 21460 KB Output is correct
14 Correct 18 ms 21460 KB Output is correct
15 Correct 38 ms 21560 KB Output is correct
16 Correct 136 ms 22084 KB Output is correct
17 Correct 145 ms 48384 KB Output is correct
18 Correct 144 ms 48284 KB Output is correct
19 Correct 136 ms 48264 KB Output is correct
20 Correct 201 ms 48456 KB Output is correct
21 Correct 428 ms 48960 KB Output is correct

Subtask #4
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 17 ms 20820 KB Output is correct
2 Correct 43 ms 20988 KB Output is correct
3 Correct 165 ms 21336 KB Output is correct
4 Correct 337 ms 21568 KB Output is correct
5 Correct 58 ms 33172 KB Output is correct
6 Correct 110 ms 33240 KB Output is correct
7 Correct 365 ms 33600 KB Output is correct
8 Correct 577 ms 34044 KB Output is correct
9 Correct 269 ms 94004 KB Output is correct
10 Correct 366 ms 94068 KB Output is correct
11 Correct 706 ms 94316 KB Output is correct
12 Correct 1085 ms 94612 KB Output is correct
13 Correct 551 ms 174272 KB Output is correct
14 Correct 645 ms 174320 KB Output is correct
15 Correct 1134 ms 174560 KB Output is correct
16 Correct 1587 ms 174868 KB Output is correct
17 Correct 2619 ms 174908 KB Output is correct

Subtask #5
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2505 ms 146952 KB Output is correct
2 Correct 2674 ms 150452 KB Output is correct
3 Correct 2629 ms 149564 KB Output is correct
4 Correct 2591 ms 149936 KB Output is correct
5 Correct 2484 ms 142476 KB Output is correct
6 Correct 2041 ms 101696 KB Output is correct
7 Correct 3249 ms 175884 KB Output is correct
8 Correct 3306 ms 175880 KB Output is correct
9 Correct 3363 ms 175704 KB Output is correct
10 Correct 3167 ms 174984 KB Output is correct
11 Correct 3100 ms 165692 KB Output is correct
12 Correct 2669 ms 115704 KB Output is correct
13 Correct 3308 ms 187912 KB Output is correct
14 Correct 3232 ms 187796 KB Output is correct
15 Correct 3263 ms 187992 KB Output is correct
16 Correct 3357 ms 187072 KB Output is correct
17 Correct 3243 ms 176860 KB Output is correct
18 Correct 2659 ms 120832 KB Output is correct
19 Correct 3393 ms 188028 KB Output is correct
20 Correct 3304 ms 187820 KB Output is correct
21 Correct 3308 ms 187748 KB Output is correct
22 Correct 3390 ms 187036 KB Output is correct
23 Correct 3348 ms 176976 KB Output is correct
24 Correct 2827 ms 120812 KB Output is correct

Subtask #6
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 19936 KB Output is correct
2 Correct 11 ms 19836 KB Output is correct
3 Correct 12 ms 19880 KB Output is correct
4 Correct 11 ms 19936 KB Output is correct
5 Correct 14 ms 19916 KB Output is correct
6 Correct 14 ms 19840 KB Output is correct
7 Correct 11 ms 19900 KB Output is correct
8 Correct 11 ms 19924 KB Output is correct
9 Correct 12 ms 19924 KB Output is correct
10 Correct 12 ms 19912 KB Output is correct
11 Correct 11 ms 19924 KB Output is correct
12 Correct 10 ms 19924 KB Output is correct
13 Correct 10 ms 19908 KB Output is correct
14 Correct 13 ms 19912 KB Output is correct
15 Correct 12 ms 19972 KB Output is correct
16 Correct 11 ms 19904 KB Output is correct
17 Correct 11 ms 19904 KB Output is correct
18 Correct 11 ms 19912 KB Output is correct
19 Correct 29 ms 20692 KB Output is correct
20 Correct 32 ms 20808 KB Output is correct
21 Correct 36 ms 20896 KB Output is correct
22 Correct 40 ms 21072 KB Output is correct
23 Correct 55 ms 24192 KB Output is correct
24 Correct 66 ms 25192 KB Output is correct
25 Correct 72 ms 25892 KB Output is correct
26 Correct 80 ms 26912 KB Output is correct
27 Correct 10 ms 19924 KB Output is correct
28 Correct 12 ms 19924 KB Output is correct
29 Correct 11 ms 19924 KB Output is correct
30 Correct 23 ms 20052 KB Output is correct
31 Correct 74 ms 20616 KB Output is correct
32 Correct 12 ms 19912 KB Output is correct
33 Correct 11 ms 20052 KB Output is correct
34 Correct 13 ms 20020 KB Output is correct
35 Correct 14 ms 20044 KB Output is correct
36 Correct 34 ms 20216 KB Output is correct
37 Correct 99 ms 20780 KB Output is correct
38 Correct 16 ms 21460 KB Output is correct
39 Correct 16 ms 21460 KB Output is correct
40 Correct 18 ms 21460 KB Output is correct
41 Correct 38 ms 21560 KB Output is correct
42 Correct 136 ms 22084 KB Output is correct
43 Correct 145 ms 48384 KB Output is correct
44 Correct 144 ms 48284 KB Output is correct
45 Correct 136 ms 48264 KB Output is correct
46 Correct 201 ms 48456 KB Output is correct
47 Correct 428 ms 48960 KB Output is correct
48 Correct 17 ms 20820 KB Output is correct
49 Correct 43 ms 20988 KB Output is correct
50 Correct 165 ms 21336 KB Output is correct
51 Correct 337 ms 21568 KB Output is correct
52 Correct 58 ms 33172 KB Output is correct
53 Correct 110 ms 33240 KB Output is correct
54 Correct 365 ms 33600 KB Output is correct
55 Correct 577 ms 34044 KB Output is correct
56 Correct 269 ms 94004 KB Output is correct
57 Correct 366 ms 94068 KB Output is correct
58 Correct 706 ms 94316 KB Output is correct
59 Correct 1085 ms 94612 KB Output is correct
60 Correct 551 ms 174272 KB Output is correct
61 Correct 645 ms 174320 KB Output is correct
62 Correct 1134 ms 174560 KB Output is correct
63 Correct 1587 ms 174868 KB Output is correct
64 Correct 2619 ms 174908 KB Output is correct
65 Correct 2505 ms 146952 KB Output is correct
66 Correct 2674 ms 150452 KB Output is correct
67 Correct 2629 ms 149564 KB Output is correct
68 Correct 2591 ms 149936 KB Output is correct
69 Correct 2484 ms 142476 KB Output is correct
70 Correct 2041 ms 101696 KB Output is correct
71 Correct 3249 ms 175884 KB Output is correct
72 Correct 3306 ms 175880 KB Output is correct
73 Correct 3363 ms 175704 KB Output is correct
74 Correct 3167 ms 174984 KB Output is correct
75 Correct 3100 ms 165692 KB Output is correct
76 Correct 2669 ms 115704 KB Output is correct
77 Correct 3308 ms 187912 KB Output is correct
78 Correct 3232 ms 187796 KB Output is correct
79 Correct 3263 ms 187992 KB Output is correct
80 Correct 3357 ms 187072 KB Output is correct
81 Correct 3243 ms 176860 KB Output is correct
82 Correct 2659 ms 120832 KB Output is correct
83 Correct 3393 ms 188028 KB Output is correct
84 Correct 3304 ms 187820 KB Output is correct
85 Correct 3308 ms 187748 KB Output is correct
86 Correct 3390 ms 187036 KB Output is correct
87 Correct 3348 ms 176976 KB Output is correct
88 Correct 2827 ms 120812 KB Output is correct
89 Correct 2539 ms 147988 KB Output is correct
90 Correct 2740 ms 159632 KB Output is correct
91 Correct 3193 ms 172184 KB Output is correct
92 Correct 3314 ms 175616 KB Output is correct
93 Correct 3330 ms 180316 KB Output is correct
94 Correct 3282 ms 183336 KB Output is correct
95 Correct 3379 ms 187708 KB Output is correct
96 Correct 3321 ms 188012 KB Output is correct
97 Correct 3407 ms 187808 KB Output is correct
98 Correct 3355 ms 187804 KB Output is correct
99 Correct 3372 ms 187916 KB Output is correct
100 Correct 3279 ms 187724 KB Output is correct