oj.uz

Submission #572763

# Submission time Handle Problem Language Result Execution time Memory
572763 2022-06-05T09:01:07 Z piOOE Dynamic Diameter (CEOI19_diameter) C++17
100 / 100
 3934 ms 327476 KB 
#include <bits/stdc++.h>

using namespace std;

#define sz(x) ((int)size(x))
#define all(x) begin(x), end(x)
#define trace(x) cout << #x << ": " << (x) << endl;

typedef long long ll;

mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

int rand(int l, int r) { return (int) ((ll) rnd() % (r - l + 1)) + l; }

struct segtree {
    int sz = 1;
    vector<ll> mx, add;

    segtree() = default;

    segtree(int n) {
        sz = 1;
        while (sz < n) {
            sz <<= 1;
        }
        mx.assign(sz << 1, 0), add.assign(sz << 1, 0);
    }

    void init(int n) {
        sz = 1;
        while (sz < n) {
            sz <<= 1;
        }
        mx.assign(sz << 1, 0), add.assign(sz << 1, 0);
    }

    void modify(int l, int r, ll val, int x, int lx, int rx) {
        if (l >= rx || lx >= r) {
            return;
        }
        if (l <= lx && rx <= r) {
            mx[x] += val;
            add[x] += val;
            return;
        }
        int m = (lx + rx) >> 1;
        modify(l, r, val, x << 1, lx, m), modify(l, r, val, x << 1 | 1, m, rx);
        mx[x] = max(mx[x << 1], mx[x << 1 | 1]) + add[x];
    }

    void modify(int l, int r, ll val) {
        modify(l, r, val, 1, 0, sz);
    }

    ll get(int l, int r, int x, int lx, int rx) {
        if (l >= rx || lx >= r) {
            return 0;
        }
        if (l <= lx && rx <= r) {
            return mx[x];
        }
        int m = (lx + rx) >> 1;
        return max(get(l, r, x << 1, lx, m), get(l, r, x << 1 | 1, m, rx)) + add[x];
    }

    ll get(int l, int r) {
        return get(l, r, 1, 0, sz);
    }

};

const int N = 100000, logn = 18;

int A[N], B[N], Root[logn][N], Parent[logn][N], Child[logn][N], siz[N], lst[N], tin[logn][N], tout[logn][N], PP[logn][N], sz[N], T = 0;
segtree st[logn][N];
multiset<ll, greater<>> mult[logn][N];
ll W[N], diam[logn][N];

bool used[N];

vector<pair<int, int>> g[N];

int centroid(int v, int n, int p) {
    for (auto [to, i]: g[v]) {
        if (!used[to] && to != p && sz[to] * 2 > n) {
            return centroid(to, n, v);
        }
    }
    return v;
}

void calc_sz(int v, int p) {
    sz[v] = 1;
    for (auto [to, i]: g[v]) {
        if (!used[to] && to != p) {
            calc_sz(to, v);
            sz[v] += sz[to];
        }
    }
}

void dfs(int v, int p, int id, int root, int pp) {
    Root[siz[v]][id] = root;
    Parent[siz[v]][id] = p;
    Child[siz[v]][id] = v;
    PP[siz[v]][id] = pp;
    tin[siz[v]][v] = T++;
    for (auto [to, j]: g[v]) {
        if (!used[to] && to != p) {
            dfs(to, v, j, root, pp);
        }
    }
    tout[siz[v]][v] = T;
    st[siz[v]][root].modify(tin[siz[v]][v], tout[siz[v]][v], W[id]);
    ++siz[v];
}

multiset<ll, greater<>> bestDiam;

void solve(int v) {
    used[v] = true;
    calc_sz(v, -1);
    T = 0;
    st[siz[v]][v].init(sz[v]);
    for (auto [to, i]: g[v]) {
        if (!used[to]) {
            dfs(to, v, i, v, to);
            mult[siz[v]][v].insert(st[siz[v]][v].get(tin[siz[v]][to], tout[siz[v]][to]));
        }
    }
    if (!mult[siz[v]][v].empty()) {
        if (sz(mult[siz[v]][v]) == 1) {
            diam[siz[v]][v] = *mult[siz[v]][v].begin();
        } else {
            diam[siz[v]][v] = (*mult[siz[v]][v].begin()) + (*next(mult[siz[v]][v].begin()));
        }
    }
    bestDiam.insert(diam[siz[v]][v]);
    ++siz[v];
    for (auto [to, i] : g[v]) {
        if (!used[to]) {
            lst[i] = siz[v];
            solve(centroid(to, sz[to], -1));
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, q;
    ll WW;
    cin >> n >> q >> WW;
    ll last = 0;
    for (int i = 0; i < n - 1; ++i) {
        cin >> A[i] >> B[i] >> W[i];
        --A[i], --B[i];
        g[A[i]].emplace_back(B[i], i);
        g[B[i]].emplace_back(A[i], i);
    }
    calc_sz(0, -1);
    solve(centroid(0, n, -1));
    assert(!bestDiam.empty());
    while (q--) {
        int i;
        ll w;
        cin >> i >> w;
        i = (last + i) % (n - 1);
        w = (w + last) % WW;
        ll zz = w;
        w = w - W[i];
        W[i] = zz;
        for (int j = 0; j < lst[i]; ++j) {
            int root = Root[j][i];
            int v = Child[j][i];
            int p = Parent[j][i];
            int pp = PP[j][i];
            bestDiam.extract(diam[j][root]);
            mult[j][root].extract(st[j][root].get(tin[j][pp], tout[j][pp]));
            st[j][root].modify(tin[j][v], tout[j][v], w);
            mult[j][root].insert(st[j][root].get(tin[j][pp], tout[j][pp]));
            if (!mult[j][root].empty()) {
                if (mult[j][root].size() == 1) {
                    diam[j][root] = *mult[j][root].begin();
                } else {
                    diam[j][root] = (*mult[j][root].begin()) + (*next(mult[j][root].begin()));
                }
            }
            bestDiam.insert(diam[j][root]);
        }
        assert(!bestDiam.empty());
        last = *bestDiam.begin();
        cout << last << '\n';
    }
    return 0;
}

Compilation message

diameter.cpp: In function 'int main()':
diameter.cpp:176:17: warning: unused variable 'p' [-Wunused-variable]
  176 |             int p = Parent[j][i];
      |                 ^

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 185972 KB Output is correct
2 Correct 93 ms 185892 KB Output is correct
3 Correct 88 ms 185976 KB Output is correct
4 Correct 89 ms 186000 KB Output is correct
5 Correct 84 ms 185996 KB Output is correct
6 Correct 84 ms 185996 KB Output is correct
7 Correct 101 ms 185932 KB Output is correct
8 Correct 87 ms 186060 KB Output is correct
9 Correct 87 ms 186188 KB Output is correct
10 Correct 83 ms 186088 KB Output is correct
11 Correct 86 ms 186056 KB Output is correct
12 Correct 84 ms 186028 KB Output is correct
13 Correct 86 ms 186056 KB Output is correct
14 Correct 90 ms 186100 KB Output is correct
15 Correct 86 ms 185980 KB Output is correct
16 Correct 88 ms 186100 KB Output is correct
17 Correct 85 ms 186032 KB Output is correct
18 Correct 85 ms 186148 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 185972 KB Output is correct
2 Correct 93 ms 185892 KB Output is correct
3 Correct 88 ms 185976 KB Output is correct
4 Correct 89 ms 186000 KB Output is correct
5 Correct 84 ms 185996 KB Output is correct
6 Correct 84 ms 185996 KB Output is correct
7 Correct 101 ms 185932 KB Output is correct
8 Correct 87 ms 186060 KB Output is correct
9 Correct 87 ms 186188 KB Output is correct
10 Correct 83 ms 186088 KB Output is correct
11 Correct 86 ms 186056 KB Output is correct
12 Correct 84 ms 186028 KB Output is correct
13 Correct 86 ms 186056 KB Output is correct
14 Correct 90 ms 186100 KB Output is correct
15 Correct 86 ms 185980 KB Output is correct
16 Correct 88 ms 186100 KB Output is correct
17 Correct 85 ms 186032 KB Output is correct
18 Correct 85 ms 186148 KB Output is correct
19 Correct 107 ms 186908 KB Output is correct
20 Correct 101 ms 186972 KB Output is correct
21 Correct 116 ms 187024 KB Output is correct
22 Correct 107 ms 186984 KB Output is correct
23 Correct 120 ms 190056 KB Output is correct
24 Correct 129 ms 191176 KB Output is correct
25 Correct 141 ms 191552 KB Output is correct
26 Correct 147 ms 192200 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 185872 KB Output is correct
2 Correct 90 ms 185808 KB Output is correct
3 Correct 98 ms 185952 KB Output is correct
4 Correct 115 ms 186044 KB Output is correct
5 Correct 132 ms 186968 KB Output is correct
6 Correct 83 ms 185804 KB Output is correct
7 Correct 88 ms 185996 KB Output is correct
8 Correct 90 ms 186164 KB Output is correct
9 Correct 89 ms 186044 KB Output is correct
10 Correct 99 ms 186216 KB Output is correct
11 Correct 156 ms 187276 KB Output is correct
12 Correct 89 ms 187440 KB Output is correct
13 Correct 91 ms 187364 KB Output is correct
14 Correct 105 ms 187472 KB Output is correct
15 Correct 130 ms 187696 KB Output is correct
16 Correct 179 ms 188900 KB Output is correct
17 Correct 204 ms 215900 KB Output is correct
18 Correct 255 ms 215868 KB Output is correct
19 Correct 207 ms 216008 KB Output is correct
20 Correct 235 ms 216308 KB Output is correct
21 Correct 470 ms 217696 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 186828 KB Output is correct
2 Correct 110 ms 186972 KB Output is correct
3 Correct 206 ms 187416 KB Output is correct
4 Correct 390 ms 188276 KB Output is correct
5 Correct 115 ms 194908 KB Output is correct
6 Correct 159 ms 195076 KB Output is correct
7 Correct 399 ms 195624 KB Output is correct
8 Correct 637 ms 196528 KB Output is correct
9 Correct 299 ms 235844 KB Output is correct
10 Correct 381 ms 236000 KB Output is correct
11 Correct 769 ms 236644 KB Output is correct
12 Correct 1211 ms 237424 KB Output is correct
13 Correct 483 ms 290588 KB Output is correct
14 Correct 620 ms 290732 KB Output is correct
15 Correct 1299 ms 291432 KB Output is correct
16 Correct 1733 ms 292112 KB Output is correct
17 Correct 3098 ms 292088 KB Output is correct

Subtask #5
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2775 ms 298676 KB Output is correct
2 Correct 2844 ms 301388 KB Output is correct
3 Correct 2649 ms 298888 KB Output is correct
4 Correct 2664 ms 303308 KB Output is correct
5 Correct 2657 ms 297656 KB Output is correct
6 Correct 2392 ms 280968 KB Output is correct
7 Correct 3809 ms 319116 KB Output is correct
8 Correct 3549 ms 319096 KB Output is correct
9 Correct 3471 ms 319056 KB Output is correct
10 Correct 3581 ms 318720 KB Output is correct
11 Correct 3580 ms 314932 KB Output is correct
12 Correct 3269 ms 291924 KB Output is correct
13 Correct 3934 ms 327128 KB Output is correct
14 Correct 3805 ms 327352 KB Output is correct
15 Correct 3892 ms 327412 KB Output is correct
16 Correct 3826 ms 326852 KB Output is correct
17 Correct 3767 ms 322036 KB Output is correct
18 Correct 3199 ms 294904 KB Output is correct
19 Correct 3837 ms 327048 KB Output is correct
20 Correct 3783 ms 327188 KB Output is correct
21 Correct 3844 ms 327476 KB Output is correct
22 Correct 3796 ms 327004 KB Output is correct
23 Correct 3719 ms 322432 KB Output is correct
24 Correct 3246 ms 294840 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 185972 KB Output is correct
2 Correct 93 ms 185892 KB Output is correct
3 Correct 88 ms 185976 KB Output is correct
4 Correct 89 ms 186000 KB Output is correct
5 Correct 84 ms 185996 KB Output is correct
6 Correct 84 ms 185996 KB Output is correct
7 Correct 101 ms 185932 KB Output is correct
8 Correct 87 ms 186060 KB Output is correct
9 Correct 87 ms 186188 KB Output is correct
10 Correct 83 ms 186088 KB Output is correct
11 Correct 86 ms 186056 KB Output is correct
12 Correct 84 ms 186028 KB Output is correct
13 Correct 86 ms 186056 KB Output is correct
14 Correct 90 ms 186100 KB Output is correct
15 Correct 86 ms 185980 KB Output is correct
16 Correct 88 ms 186100 KB Output is correct
17 Correct 85 ms 186032 KB Output is correct
18 Correct 85 ms 186148 KB Output is correct
19 Correct 107 ms 186908 KB Output is correct
20 Correct 101 ms 186972 KB Output is correct
21 Correct 116 ms 187024 KB Output is correct
22 Correct 107 ms 186984 KB Output is correct
23 Correct 120 ms 190056 KB Output is correct
24 Correct 129 ms 191176 KB Output is correct
25 Correct 141 ms 191552 KB Output is correct
26 Correct 147 ms 192200 KB Output is correct
27 Correct 85 ms 185872 KB Output is correct
28 Correct 90 ms 185808 KB Output is correct
29 Correct 98 ms 185952 KB Output is correct
30 Correct 115 ms 186044 KB Output is correct
31 Correct 132 ms 186968 KB Output is correct
32 Correct 83 ms 185804 KB Output is correct
33 Correct 88 ms 185996 KB Output is correct
34 Correct 90 ms 186164 KB Output is correct
35 Correct 89 ms 186044 KB Output is correct
36 Correct 99 ms 186216 KB Output is correct
37 Correct 156 ms 187276 KB Output is correct
38 Correct 89 ms 187440 KB Output is correct
39 Correct 91 ms 187364 KB Output is correct
40 Correct 105 ms 187472 KB Output is correct
41 Correct 130 ms 187696 KB Output is correct
42 Correct 179 ms 188900 KB Output is correct
43 Correct 204 ms 215900 KB Output is correct
44 Correct 255 ms 215868 KB Output is correct
45 Correct 207 ms 216008 KB Output is correct
46 Correct 235 ms 216308 KB Output is correct
47 Correct 470 ms 217696 KB Output is correct
48 Correct 105 ms 186828 KB Output is correct
49 Correct 110 ms 186972 KB Output is correct
50 Correct 206 ms 187416 KB Output is correct
51 Correct 390 ms 188276 KB Output is correct
52 Correct 115 ms 194908 KB Output is correct
53 Correct 159 ms 195076 KB Output is correct
54 Correct 399 ms 195624 KB Output is correct
55 Correct 637 ms 196528 KB Output is correct
56 Correct 299 ms 235844 KB Output is correct
57 Correct 381 ms 236000 KB Output is correct
58 Correct 769 ms 236644 KB Output is correct
59 Correct 1211 ms 237424 KB Output is correct
60 Correct 483 ms 290588 KB Output is correct
61 Correct 620 ms 290732 KB Output is correct
62 Correct 1299 ms 291432 KB Output is correct
63 Correct 1733 ms 292112 KB Output is correct
64 Correct 3098 ms 292088 KB Output is correct
65 Correct 2775 ms 298676 KB Output is correct
66 Correct 2844 ms 301388 KB Output is correct
67 Correct 2649 ms 298888 KB Output is correct
68 Correct 2664 ms 303308 KB Output is correct
69 Correct 2657 ms 297656 KB Output is correct
70 Correct 2392 ms 280968 KB Output is correct
71 Correct 3809 ms 319116 KB Output is correct
72 Correct 3549 ms 319096 KB Output is correct
73 Correct 3471 ms 319056 KB Output is correct
74 Correct 3581 ms 318720 KB Output is correct
75 Correct 3580 ms 314932 KB Output is correct
76 Correct 3269 ms 291924 KB Output is correct
77 Correct 3934 ms 327128 KB Output is correct
78 Correct 3805 ms 327352 KB Output is correct
79 Correct 3892 ms 327412 KB Output is correct
80 Correct 3826 ms 326852 KB Output is correct
81 Correct 3767 ms 322036 KB Output is correct
82 Correct 3199 ms 294904 KB Output is correct
83 Correct 3837 ms 327048 KB Output is correct
84 Correct 3783 ms 327188 KB Output is correct
85 Correct 3844 ms 327476 KB Output is correct
86 Correct 3796 ms 327004 KB Output is correct
87 Correct 3719 ms 322432 KB Output is correct
88 Correct 3246 ms 294840 KB Output is correct
89 Correct 2685 ms 299824 KB Output is correct
90 Correct 2992 ms 309348 KB Output is correct
91 Correct 3683 ms 315924 KB Output is correct
92 Correct 3504 ms 317984 KB Output is correct
93 Correct 3670 ms 321344 KB Output is correct
94 Correct 3733 ms 322260 KB Output is correct
95 Correct 3846 ms 324376 KB Output is correct
96 Correct 3816 ms 323364 KB Output is correct
97 Correct 3788 ms 324148 KB Output is correct
98 Correct 3872 ms 326372 KB Output is correct
99 Correct 3881 ms 323900 KB Output is correct
100 Correct 3841 ms 323796 KB Output is correct