oj.uz

Submission #924798

# Submission time Handle Problem Language Result Execution time Memory
924798 2024-02-09T17:03:31 Z Camillus Dynamic Diameter (CEOI19_diameter) C++17
100 / 100
 1841 ms 134316 KB 
/// @author Camillus
#include "bits/stdc++.h"

using ll = long long;
using namespace std;

mt19937 rnd(228);

vector<pair<int, int>> g[100500];
int from[100500];
int to[100500];
ll w[100500];

int sz[100500];
bool mark[100500];

void dfs_sz(int u, int p = -1) {
    sz[u] = 1;
    for (auto [v, i] : g[u]) {
        if (v != p && !mark[v]) {
            dfs_sz(v, u);
            sz[u] += sz[v];
        }
    }
}

namespace detail {
    int component_size;
    int level;
    int centoid;
};

int get_centroid(int u, int p = -1) {
    for (auto [v, i] : g[u]) {
        if (v != p && !mark[v] && sz[v] * 2 > detail::component_size) {
            return get_centroid(v, u);
        }
    }
    return u;
}

int vertex_centroid[20][100500];
int tin[20][100500];
int tout[20][100500];
int timer[20];

namespace st {
    static constexpr int size = 1 << 17;

    struct node {
        ll max = 0;
        ll add = 0;
    } tree[20][size * 2 - 1];
} // namespace st

struct segment_tree {
    static constexpr int size = st::size;

    st::node *tree;

    segment_tree(int level) {
        tree = st::tree[level];
    }

    inline void apply(int x, ll v) const {
        tree[x].max += v;
        tree[x].add += v;
    }

    inline void push(int x) const {
        if (tree[x].add) {
            apply(x * 2 + 1, tree[x].add);
            apply(x * 2 + 2, tree[x].add);
            tree[x].add = 0;
        }
    }

    inline void pull(int x) const {
        tree[x].max = max(tree[x * 2 + 1].max, tree[x * 2 + 2].max);
    }

    inline void set(int i, ll v) const {
        int x = size + i - 1;
        tree[x].max = v;
        while (x) {
            x = (x - 1) / 2;
            pull(x);
        }
    }

    void add(int l, int r, ll v, int x = 0, int lx = 0, int rx = size) const {
        if (l >= rx || lx >= r) {
            return;
        }

        if (l <= lx && rx <= r) {
            apply(x, v);
            return;
        }

        push(x);

        add(l, r, v, x * 2 + 1, lx, (lx + rx) / 2);
        add(l, r, v, x * 2 + 2, (lx + rx) / 2, rx);

        pull(x);
    }

    ll get(int l, int r, int x = 0, int lx = 0, int rx = size) const {
        if (l <= lx && rx <= r) {
            return tree[x].max;
        }

        if (l >= rx || lx >= r) {
            return 0;
        }

        push(x);

        return max(
                get(l, r, x * 2 + 1, lx, (lx + rx) / 2),
                get(l, r, x * 2 + 2, (lx + rx) / 2, rx)
        );
    }
};


namespace st2 {
    static constexpr int size = 1 << 17;
    ll tree[size * 2 - 1];

    void set(int i, ll v) {
        int x = size + i - 1;
        tree[x] = v;

        while (x) {
            x = (x - 1) / 2;
            tree[x] = max(tree[x * 2 + 1], tree[x * 2 + 2]);
        }
    }

    ll get() {
        return tree[0];
    }
};

vector<int> centoid_children[100500];

vector<ll> C1[100500];
multiset<ll, greater<ll>> C2[100500];

ll get_centroid_diameter(int u) {
    if (C2[u].empty()) {
        return 0;
    } else if (C2[u].size() == 1) {
        return C1[u].back();
    } else {
        return *C2[u].begin() + *next(C2[u].begin());
    }
}

void update_cetroid_diameter(int u) {
    st2::set(u, get_centroid_diameter(u));
}

void dfs_centroid(int u, int p = -1, ll d = 0) {
    vertex_centroid[detail::level][u] = detail::centoid;

    bool is_leaf = true;

    for (auto [v, i] : g[u]) {
        if (v != p && !mark[v]) {
            dfs_centroid(v, u, d + w[i]);
            if (is_leaf) {
                tin[detail::level][u] = tin[detail::level][v];
            }
            tout[detail::level][u] = tout[detail::level][v];
            is_leaf = false;
        }
    }

    if (is_leaf) {
        tin[detail::level][u] = timer[detail::level]++;
        tout[detail::level][u] = timer[detail::level];
        segment_tree(detail::level).set(tin[detail::level][u], d);
    }
}

void dfs_main(int u, int l = 0) {
    detail::level = l;

    dfs_sz(u);
    detail::component_size = sz[u];

    u = get_centroid(u);
    detail::centoid = u;
    mark[u] = true;

    dfs_centroid(u);

    segment_tree ST(l);

    for (auto [v, i] : g[u]) {
        if (!mark[v]) {
            C1[u].push_back(ST.get(tin[l][v], tout[l][v]));
            C2[u].insert(C1[u].back());
            centoid_children[u].push_back(v);
            dfs_main(v, l + 1);
        }
    }

    update_cetroid_diameter(u);
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, q;
    cin >> n >> q;

    ll W;
    cin >> W;

    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v >> w[i];

        from[i] = u;
        to[i] = v;

        g[u].emplace_back(v, i);
        g[v].emplace_back(u, i);
    }

    dfs_main(1);

    ll last = 0;

    while (q--) {
        ll d, e;
        cin >> d >> e;

        d = (d + last) % (n - 1);
        e = (e + last) % W;

        int u = from[d];
        int v = to[d];

        ll change = e - w[d];
        w[d] = e;

        for (int l = 0; l < 20; l++) {
            if (!vertex_centroid[l][u] || vertex_centroid[l][u] != vertex_centroid[l][v]) {
                break;
            }

            int c = vertex_centroid[l][u];

            int L = max(tin[l][u], tin[l][v]);
            int R = min(tout[l][u], tout[l][v]);

            segment_tree ST(l);

            ST.add(L, R, change);

            auto it = upper_bound(centoid_children[c].begin(), centoid_children[c].end(), L, [&l](int L, int u) -> bool {
                return L < tin[l][u];
            });

            it = prev(it);

            int i = it - centoid_children[c].begin();
            int U = centoid_children[c][i];

            C2[c].erase(C2[c].find(C1[c][i]));
            C1[c][i] = ST.get(tin[l][U], tout[l][U]);
            C2[c].insert(C1[c][i]);

            update_cetroid_diameter(c);
        }

        last = st2::get();
        cout << last << '\n';
    }
    return 0;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 37728 KB Output is correct
2 Correct 6 ms 37720 KB Output is correct
3 Correct 6 ms 37724 KB Output is correct
4 Correct 6 ms 37932 KB Output is correct
5 Correct 6 ms 37724 KB Output is correct
6 Correct 7 ms 37724 KB Output is correct
7 Correct 8 ms 44280 KB Output is correct
8 Correct 9 ms 50012 KB Output is correct
9 Correct 8 ms 50012 KB Output is correct
10 Correct 7 ms 50008 KB Output is correct
11 Correct 8 ms 50268 KB Output is correct
12 Correct 7 ms 50268 KB Output is correct
13 Correct 8 ms 50428 KB Output is correct
14 Correct 7 ms 50264 KB Output is correct
15 Correct 7 ms 50268 KB Output is correct
16 Correct 8 ms 50268 KB Output is correct
17 Correct 9 ms 54364 KB Output is correct
18 Correct 8 ms 54360 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 37728 KB Output is correct
2 Correct 6 ms 37720 KB Output is correct
3 Correct 6 ms 37724 KB Output is correct
4 Correct 6 ms 37932 KB Output is correct
5 Correct 6 ms 37724 KB Output is correct
6 Correct 7 ms 37724 KB Output is correct
7 Correct 8 ms 44280 KB Output is correct
8 Correct 9 ms 50012 KB Output is correct
9 Correct 8 ms 50012 KB Output is correct
10 Correct 7 ms 50008 KB Output is correct
11 Correct 8 ms 50268 KB Output is correct
12 Correct 7 ms 50268 KB Output is correct
13 Correct 8 ms 50428 KB Output is correct
14 Correct 7 ms 50264 KB Output is correct
15 Correct 7 ms 50268 KB Output is correct
16 Correct 8 ms 50268 KB Output is correct
17 Correct 9 ms 54364 KB Output is correct
18 Correct 8 ms 54360 KB Output is correct
19 Correct 22 ms 64604 KB Output is correct
20 Correct 26 ms 70748 KB Output is correct
21 Correct 26 ms 71008 KB Output is correct
22 Correct 27 ms 71004 KB Output is correct
23 Correct 31 ms 71532 KB Output is correct
24 Correct 39 ms 81752 KB Output is correct
25 Correct 44 ms 85968 KB Output is correct
26 Correct 39 ms 86304 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 27484 KB Output is correct
2 Correct 5 ms 27692 KB Output is correct
3 Correct 6 ms 27484 KB Output is correct
4 Correct 17 ms 27864 KB Output is correct
5 Correct 63 ms 28692 KB Output is correct
6 Correct 5 ms 27480 KB Output is correct
7 Correct 5 ms 27740 KB Output is correct
8 Correct 5 ms 27740 KB Output is correct
9 Correct 8 ms 27736 KB Output is correct
10 Correct 19 ms 27996 KB Output is correct
11 Correct 75 ms 29016 KB Output is correct
12 Correct 9 ms 28532 KB Output is correct
13 Correct 8 ms 28252 KB Output is correct
14 Correct 11 ms 28148 KB Output is correct
15 Correct 25 ms 28508 KB Output is correct
16 Correct 93 ms 29636 KB Output is correct
17 Correct 80 ms 40648 KB Output is correct
18 Correct 83 ms 40648 KB Output is correct
19 Correct 86 ms 40900 KB Output is correct
20 Correct 113 ms 41160 KB Output is correct
21 Correct 242 ms 42444 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 64600 KB Output is correct
2 Correct 32 ms 64860 KB Output is correct
3 Correct 121 ms 65364 KB Output is correct
4 Correct 228 ms 66128 KB Output is correct
5 Correct 24 ms 86352 KB Output is correct
6 Correct 54 ms 86656 KB Output is correct
7 Correct 173 ms 87124 KB Output is correct
8 Correct 317 ms 88368 KB Output is correct
9 Correct 76 ms 104532 KB Output is correct
10 Correct 116 ms 104788 KB Output is correct
11 Correct 308 ms 105300 KB Output is correct
12 Correct 524 ms 106248 KB Output is correct
13 Correct 141 ms 117768 KB Output is correct
14 Correct 200 ms 118032 KB Output is correct
15 Correct 412 ms 118608 KB Output is correct
16 Correct 680 ms 119520 KB Output is correct
17 Correct 1528 ms 119416 KB Output is correct

Subtask #5
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1368 ms 121696 KB Output is correct
2 Correct 1401 ms 122172 KB Output is correct
3 Correct 1363 ms 117632 KB Output is correct
4 Correct 1391 ms 122036 KB Output is correct
5 Correct 1375 ms 121848 KB Output is correct
6 Correct 1222 ms 119520 KB Output is correct
7 Correct 1836 ms 128724 KB Output is correct
8 Correct 1715 ms 128976 KB Output is correct
9 Correct 1841 ms 128668 KB Output is correct
10 Correct 1813 ms 129068 KB Output is correct
11 Correct 1820 ms 128520 KB Output is correct
12 Correct 1616 ms 125720 KB Output is correct
13 Correct 1387 ms 133944 KB Output is correct
14 Correct 1395 ms 133984 KB Output is correct
15 Correct 1420 ms 134316 KB Output is correct
16 Correct 1493 ms 134032 KB Output is correct
17 Correct 1416 ms 133012 KB Output is correct
18 Correct 1361 ms 128912 KB Output is correct
19 Correct 1339 ms 134016 KB Output is correct
20 Correct 1442 ms 134248 KB Output is correct
21 Correct 1385 ms 133968 KB Output is correct
22 Correct 1459 ms 134244 KB Output is correct
23 Correct 1353 ms 133204 KB Output is correct
24 Correct 1329 ms 129372 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 37728 KB Output is correct
2 Correct 6 ms 37720 KB Output is correct
3 Correct 6 ms 37724 KB Output is correct
4 Correct 6 ms 37932 KB Output is correct
5 Correct 6 ms 37724 KB Output is correct
6 Correct 7 ms 37724 KB Output is correct
7 Correct 8 ms 44280 KB Output is correct
8 Correct 9 ms 50012 KB Output is correct
9 Correct 8 ms 50012 KB Output is correct
10 Correct 7 ms 50008 KB Output is correct
11 Correct 8 ms 50268 KB Output is correct
12 Correct 7 ms 50268 KB Output is correct
13 Correct 8 ms 50428 KB Output is correct
14 Correct 7 ms 50264 KB Output is correct
15 Correct 7 ms 50268 KB Output is correct
16 Correct 8 ms 50268 KB Output is correct
17 Correct 9 ms 54364 KB Output is correct
18 Correct 8 ms 54360 KB Output is correct
19 Correct 22 ms 64604 KB Output is correct
20 Correct 26 ms 70748 KB Output is correct
21 Correct 26 ms 71008 KB Output is correct
22 Correct 27 ms 71004 KB Output is correct
23 Correct 31 ms 71532 KB Output is correct
24 Correct 39 ms 81752 KB Output is correct
25 Correct 44 ms 85968 KB Output is correct
26 Correct 39 ms 86304 KB Output is correct
27 Correct 5 ms 27484 KB Output is correct
28 Correct 5 ms 27692 KB Output is correct
29 Correct 6 ms 27484 KB Output is correct
30 Correct 17 ms 27864 KB Output is correct
31 Correct 63 ms 28692 KB Output is correct
32 Correct 5 ms 27480 KB Output is correct
33 Correct 5 ms 27740 KB Output is correct
34 Correct 5 ms 27740 KB Output is correct
35 Correct 8 ms 27736 KB Output is correct
36 Correct 19 ms 27996 KB Output is correct
37 Correct 75 ms 29016 KB Output is correct
38 Correct 9 ms 28532 KB Output is correct
39 Correct 8 ms 28252 KB Output is correct
40 Correct 11 ms 28148 KB Output is correct
41 Correct 25 ms 28508 KB Output is correct
42 Correct 93 ms 29636 KB Output is correct
43 Correct 80 ms 40648 KB Output is correct
44 Correct 83 ms 40648 KB Output is correct
45 Correct 86 ms 40900 KB Output is correct
46 Correct 113 ms 41160 KB Output is correct
47 Correct 242 ms 42444 KB Output is correct
48 Correct 12 ms 64600 KB Output is correct
49 Correct 32 ms 64860 KB Output is correct
50 Correct 121 ms 65364 KB Output is correct
51 Correct 228 ms 66128 KB Output is correct
52 Correct 24 ms 86352 KB Output is correct
53 Correct 54 ms 86656 KB Output is correct
54 Correct 173 ms 87124 KB Output is correct
55 Correct 317 ms 88368 KB Output is correct
56 Correct 76 ms 104532 KB Output is correct
57 Correct 116 ms 104788 KB Output is correct
58 Correct 308 ms 105300 KB Output is correct
59 Correct 524 ms 106248 KB Output is correct
60 Correct 141 ms 117768 KB Output is correct
61 Correct 200 ms 118032 KB Output is correct
62 Correct 412 ms 118608 KB Output is correct
63 Correct 680 ms 119520 KB Output is correct
64 Correct 1528 ms 119416 KB Output is correct
65 Correct 1368 ms 121696 KB Output is correct
66 Correct 1401 ms 122172 KB Output is correct
67 Correct 1363 ms 117632 KB Output is correct
68 Correct 1391 ms 122036 KB Output is correct
69 Correct 1375 ms 121848 KB Output is correct
70 Correct 1222 ms 119520 KB Output is correct
71 Correct 1836 ms 128724 KB Output is correct
72 Correct 1715 ms 128976 KB Output is correct
73 Correct 1841 ms 128668 KB Output is correct
74 Correct 1813 ms 129068 KB Output is correct
75 Correct 1820 ms 128520 KB Output is correct
76 Correct 1616 ms 125720 KB Output is correct
77 Correct 1387 ms 133944 KB Output is correct
78 Correct 1395 ms 133984 KB Output is correct
79 Correct 1420 ms 134316 KB Output is correct
80 Correct 1493 ms 134032 KB Output is correct
81 Correct 1416 ms 133012 KB Output is correct
82 Correct 1361 ms 128912 KB Output is correct
83 Correct 1339 ms 134016 KB Output is correct
84 Correct 1442 ms 134248 KB Output is correct
85 Correct 1385 ms 133968 KB Output is correct
86 Correct 1459 ms 134244 KB Output is correct
87 Correct 1353 ms 133204 KB Output is correct
88 Correct 1329 ms 129372 KB Output is correct
89 Correct 1429 ms 120676 KB Output is correct
90 Correct 1535 ms 125268 KB Output is correct
91 Correct 1700 ms 127188 KB Output is correct
92 Correct 1818 ms 127656 KB Output is correct
93 Correct 1725 ms 129616 KB Output is correct
94 Correct 1688 ms 129208 KB Output is correct
95 Correct 1481 ms 130940 KB Output is correct
96 Correct 1436 ms 129952 KB Output is correct
97 Correct 1358 ms 130808 KB Output is correct
98 Correct 1397 ms 133288 KB Output is correct
99 Correct 1365 ms 130600 KB Output is correct
100 Correct 1400 ms 130432 KB Output is correct