oj.uz

Submission #579133

# Submission time Handle Problem Language Result Execution time Memory
579133 2022-06-18T12:08:40 Z talant117408 Dynamic Diameter (CEOI19_diameter) C++17
100 / 100
 3840 ms 175220 KB 
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;

#define long                unsigned long 
#define pb                  push_back
#define mp                  make_pair
#define all(v)              (v).begin(),(v).end()
#define rall(v)             (v).rbegin(),(v).rend()
#define lb                  lower_bound
#define ub                  upper_bound
#define sz(v)               int((v).size())
#define do_not_disturb      ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl                '\n'

const int N = 1e5+7;
set <pair <int, ll>> graph[N];
vector <pair <pii, ll>> edges;
vector <vector <ll>> tree(N), lz(N);
multiset <ll, greater <ll>> to_leaves[N];
int subtree[N], level[N], parent[N][20], timer, par[N], S[N];
pii ranges[N][20];
int n, q;
ll w;

void push(int i, int v, int l, int r) {
    if (lz[i][v] != 0) {
        tree[i][v] += lz[i][v];
        if (l != r) {
            lz[i][v*2] += lz[i][v];
            lz[i][v*2+1] += lz[i][v];
        }
        lz[i][v] = 0;
    }
}

void update(int i, int v, int l, int r, int ql, int qr, ll val) {
    push(i, v, l, r);
    if (ql > r || l > qr) return;
    if (ql <= l && r <= qr) {
        lz[i][v] += val;
        push(i, v, l, r);
        return;
    }
    int mid = (l+r) >> 1;
    update(i, v*2, l, mid, ql, qr, val);
    update(i, v*2+1, mid+1, r, ql, qr, val);
    tree[i][v] = max(tree[i][v*2], tree[i][v*2+1]);
}

ll get(int i, int v, int l, int r, int ql, int qr) {
    push(i, v, l, r);
    if (ql > r || l > qr) return -1e18;
    if (ql <= l && r <= qr) return tree[i][v];
    int mid = (l+r) >> 1;
    return max(get(i, v*2, l, mid, ql, qr), get(i, v*2+1, mid+1, r, ql, qr));
}

void find_subtrees(int v, int p) {
    subtree[v] = 1;
    for (auto to : graph[v]) {
        if (to.first == p || level[to.first]) continue;
        find_subtrees(to.first, v);
        subtree[v] += subtree[to.first];
    }
}

int find_centroid(int v, int p, int saizu) {
    for (auto to : graph[v]) {
        if (to.first == p || level[to.first]) continue;
        if (subtree[to.first]*2 > saizu) return find_centroid(to.first, v, saizu);
    }
    return v;
}

ll tmpddd;
ll ans_tree[N*4];
void ans_update(int v, int l, int r, int pos, ll val) {
    if (l == r) {
        ans_tree[v] = val;
        return;
    }
    int mid = (l+r) >> 1;
    if (pos <= mid) ans_update(v*2, l, mid, pos, val);
    else ans_update(v*2+1, mid+1, r, pos, val);
    ans_tree[v] = max(ans_tree[v*2], ans_tree[v*2+1]);
}

void cnd_dfs(int v, int p, ll dist, int &origin, int &saizu, int &lev, int &origin2) {
    pii range;
    range.first = ++timer;
    tmpddd = max(tmpddd, dist);
    update(origin, 1, 0, saizu-1, timer, timer, dist);
    parent[v][lev] = origin2;
    
    for (auto to : graph[v]) {
        if (to.first == p || level[to.first]) continue;
        cnd_dfs(to.first, v, dist+to.second, origin, saizu, lev, origin2);
    }
    range.second = timer;
    ranges[v][lev] = range;
}

void centroid_decomposition(int v, int p = 0, int lev = 1) {
    find_subtrees(v, v);
    auto centroid = find_centroid(v, v, subtree[v]);
    level[centroid] = lev;
    par[centroid] = p;
    
    tree[centroid].resize(subtree[v]*4);
    lz[centroid].resize(subtree[v]*4);
    S[centroid] = subtree[v];
    timer = 0;
    for (auto to : graph[centroid]) {
        if (level[to.first]) continue;
        tmpddd = 0;
        cnd_dfs(to.first, centroid, to.second, centroid, subtree[v], lev, to.first);
        to_leaves[centroid].insert(tmpddd);
    }
    ll res = 0, cnt = 0;
    for (auto to : to_leaves[centroid]) {
        res += to;
        if (++cnt > 1) break;
    }
    ans_update(1, 1, n, centroid, res);
    
    for (auto to : graph[centroid]) {
        if (level[to.first]) continue;
        centroid_decomposition(to.first, centroid, lev+1);
    }
}

void solve() {
    cin >> n >> q >> w;
    for (int i = 0; i < n-1; i++) {
        int a, b;
        ll c;
        cin >> a >> b >> c;
        if (a > b) swap(a, b);
        edges.pb(mp(mp(a, b), c));
        graph[a].insert(mp(b, c));
        graph[b].insert(mp(a, c));
    }
    centroid_decomposition(1);
    ll last = 0;
    while (q--) {
        ll d, e;
        cin >> d >> e;
        d = (d + last) % (n - 1);
        e = (e + last) % w; 
        auto a = edges[d].first.first, b = edges[d].first.second;
        auto &c = edges[d].second;
        if (level[a] > level[b]) swap(a, b);
        auto x = a;
        while (x) {
            {
                auto ita = ranges[a][level[x]].first;
                auto itb = ranges[b][level[x]].first;
                if (get(x, 1, 0, S[x]-1, ita, ita) > get(x, 1, 0, S[x]-1, itb, itb)) swap(a, b);
            }
            auto range = ranges[b][level[x]];
            auto prange = ranges[parent[b][level[x]]][level[x]];
            to_leaves[x].erase(to_leaves[x].find(get(x, 1, 0, S[x]-1, prange.first, prange.second)));
            update(x, 1, 0, S[x]-1, range.first, range.second, e-c);
            to_leaves[x].insert(get(x, 1, 0, S[x]-1, prange.first, prange.second));
            ll res = 0, cnt = 0;
            for (auto to : to_leaves[x]) {
                res += to;
                if (++cnt > 1) break;
            }
            ans_update(1, 1, n, x, res);
            x = par[x];
        }
        cout << ans_tree[1] << endl;
        c = e;
        last = ans_tree[1];
    }
}

int main() {
    do_not_disturb
    
    int t = 1;
    //~ cin >> t;
    while (t--) {
        solve();
    }
    
    return 0;
}
/*

*/

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14420 KB Output is correct
2 Correct 8 ms 14352 KB Output is correct
3 Correct 8 ms 14420 KB Output is correct
4 Correct 8 ms 14360 KB Output is correct
5 Correct 7 ms 14420 KB Output is correct
6 Correct 7 ms 14420 KB Output is correct
7 Correct 7 ms 14420 KB Output is correct
8 Correct 8 ms 14408 KB Output is correct
9 Correct 10 ms 14416 KB Output is correct
10 Correct 8 ms 14420 KB Output is correct
11 Correct 8 ms 14420 KB Output is correct
12 Correct 16 ms 14420 KB Output is correct
13 Correct 8 ms 14420 KB Output is correct
14 Correct 8 ms 14496 KB Output is correct
15 Correct 8 ms 14440 KB Output is correct
16 Correct 8 ms 14508 KB Output is correct
17 Correct 8 ms 14420 KB Output is correct
18 Correct 8 ms 14420 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14420 KB Output is correct
2 Correct 8 ms 14352 KB Output is correct
3 Correct 8 ms 14420 KB Output is correct
4 Correct 8 ms 14360 KB Output is correct
5 Correct 7 ms 14420 KB Output is correct
6 Correct 7 ms 14420 KB Output is correct
7 Correct 7 ms 14420 KB Output is correct
8 Correct 8 ms 14408 KB Output is correct
9 Correct 10 ms 14416 KB Output is correct
10 Correct 8 ms 14420 KB Output is correct
11 Correct 8 ms 14420 KB Output is correct
12 Correct 16 ms 14420 KB Output is correct
13 Correct 8 ms 14420 KB Output is correct
14 Correct 8 ms 14496 KB Output is correct
15 Correct 8 ms 14440 KB Output is correct
16 Correct 8 ms 14508 KB Output is correct
17 Correct 8 ms 14420 KB Output is correct
18 Correct 8 ms 14420 KB Output is correct
19 Correct 31 ms 15276 KB Output is correct
20 Correct 32 ms 15368 KB Output is correct
21 Correct 40 ms 15440 KB Output is correct
22 Correct 40 ms 15544 KB Output is correct
23 Correct 56 ms 19068 KB Output is correct
24 Correct 68 ms 19744 KB Output is correct
25 Correct 85 ms 20140 KB Output is correct
26 Correct 108 ms 20916 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14380 KB Output is correct
2 Correct 8 ms 14420 KB Output is correct
3 Correct 10 ms 14420 KB Output is correct
4 Correct 23 ms 14552 KB Output is correct
5 Correct 75 ms 14796 KB Output is correct
6 Correct 8 ms 14420 KB Output is correct
7 Correct 9 ms 14732 KB Output is correct
8 Correct 10 ms 14676 KB Output is correct
9 Correct 10 ms 14704 KB Output is correct
10 Correct 29 ms 14804 KB Output is correct
11 Correct 122 ms 15308 KB Output is correct
12 Correct 13 ms 17524 KB Output is correct
13 Correct 14 ms 17564 KB Output is correct
14 Correct 18 ms 17492 KB Output is correct
15 Correct 47 ms 17608 KB Output is correct
16 Correct 170 ms 18044 KB Output is correct
17 Correct 168 ms 75848 KB Output is correct
18 Correct 179 ms 75948 KB Output is correct
19 Correct 187 ms 75908 KB Output is correct
20 Correct 266 ms 76124 KB Output is correct
21 Correct 573 ms 76464 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 15444 KB Output is correct
2 Correct 55 ms 15492 KB Output is correct
3 Correct 234 ms 15688 KB Output is correct
4 Correct 500 ms 15948 KB Output is correct
5 Correct 47 ms 26544 KB Output is correct
6 Correct 117 ms 26608 KB Output is correct
7 Correct 542 ms 26776 KB Output is correct
8 Correct 776 ms 27088 KB Output is correct
9 Correct 239 ms 82020 KB Output is correct
10 Correct 380 ms 82088 KB Output is correct
11 Correct 938 ms 82472 KB Output is correct
12 Correct 1708 ms 82912 KB Output is correct
13 Correct 566 ms 155884 KB Output is correct
14 Correct 729 ms 155932 KB Output is correct
15 Correct 1269 ms 156124 KB Output is correct
16 Correct 2308 ms 156432 KB Output is correct
17 Correct 3548 ms 156384 KB Output is correct

Subtask #5
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 3496 ms 132904 KB Output is correct
2 Correct 3417 ms 135352 KB Output is correct
3 Correct 3076 ms 134640 KB Output is correct
4 Correct 3014 ms 135460 KB Output is correct
5 Correct 2884 ms 130876 KB Output is correct
6 Correct 2676 ms 107552 KB Output is correct
7 Correct 3809 ms 158724 KB Output is correct
8 Correct 3840 ms 162932 KB Output is correct
9 Correct 3622 ms 162660 KB Output is correct
10 Correct 3650 ms 162252 KB Output is correct
11 Correct 3656 ms 156644 KB Output is correct
12 Correct 3236 ms 125376 KB Output is correct
13 Correct 3825 ms 174924 KB Output is correct
14 Correct 3404 ms 175036 KB Output is correct
15 Correct 3365 ms 174984 KB Output is correct
16 Correct 3792 ms 174488 KB Output is correct
17 Correct 3446 ms 167572 KB Output is correct
18 Correct 3010 ms 130140 KB Output is correct
19 Correct 3463 ms 175028 KB Output is correct
20 Correct 3561 ms 175028 KB Output is correct
21 Correct 3534 ms 175220 KB Output is correct
22 Correct 3380 ms 174528 KB Output is correct
23 Correct 3394 ms 167528 KB Output is correct
24 Correct 3204 ms 130096 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14420 KB Output is correct
2 Correct 8 ms 14352 KB Output is correct
3 Correct 8 ms 14420 KB Output is correct
4 Correct 8 ms 14360 KB Output is correct
5 Correct 7 ms 14420 KB Output is correct
6 Correct 7 ms 14420 KB Output is correct
7 Correct 7 ms 14420 KB Output is correct
8 Correct 8 ms 14408 KB Output is correct
9 Correct 10 ms 14416 KB Output is correct
10 Correct 8 ms 14420 KB Output is correct
11 Correct 8 ms 14420 KB Output is correct
12 Correct 16 ms 14420 KB Output is correct
13 Correct 8 ms 14420 KB Output is correct
14 Correct 8 ms 14496 KB Output is correct
15 Correct 8 ms 14440 KB Output is correct
16 Correct 8 ms 14508 KB Output is correct
17 Correct 8 ms 14420 KB Output is correct
18 Correct 8 ms 14420 KB Output is correct
19 Correct 31 ms 15276 KB Output is correct
20 Correct 32 ms 15368 KB Output is correct
21 Correct 40 ms 15440 KB Output is correct
22 Correct 40 ms 15544 KB Output is correct
23 Correct 56 ms 19068 KB Output is correct
24 Correct 68 ms 19744 KB Output is correct
25 Correct 85 ms 20140 KB Output is correct
26 Correct 108 ms 20916 KB Output is correct
27 Correct 9 ms 14380 KB Output is correct
28 Correct 8 ms 14420 KB Output is correct
29 Correct 10 ms 14420 KB Output is correct
30 Correct 23 ms 14552 KB Output is correct
31 Correct 75 ms 14796 KB Output is correct
32 Correct 8 ms 14420 KB Output is correct
33 Correct 9 ms 14732 KB Output is correct
34 Correct 10 ms 14676 KB Output is correct
35 Correct 10 ms 14704 KB Output is correct
36 Correct 29 ms 14804 KB Output is correct
37 Correct 122 ms 15308 KB Output is correct
38 Correct 13 ms 17524 KB Output is correct
39 Correct 14 ms 17564 KB Output is correct
40 Correct 18 ms 17492 KB Output is correct
41 Correct 47 ms 17608 KB Output is correct
42 Correct 170 ms 18044 KB Output is correct
43 Correct 168 ms 75848 KB Output is correct
44 Correct 179 ms 75948 KB Output is correct
45 Correct 187 ms 75908 KB Output is correct
46 Correct 266 ms 76124 KB Output is correct
47 Correct 573 ms 76464 KB Output is correct
48 Correct 14 ms 15444 KB Output is correct
49 Correct 55 ms 15492 KB Output is correct
50 Correct 234 ms 15688 KB Output is correct
51 Correct 500 ms 15948 KB Output is correct
52 Correct 47 ms 26544 KB Output is correct
53 Correct 117 ms 26608 KB Output is correct
54 Correct 542 ms 26776 KB Output is correct
55 Correct 776 ms 27088 KB Output is correct
56 Correct 239 ms 82020 KB Output is correct
57 Correct 380 ms 82088 KB Output is correct
58 Correct 938 ms 82472 KB Output is correct
59 Correct 1708 ms 82912 KB Output is correct
60 Correct 566 ms 155884 KB Output is correct
61 Correct 729 ms 155932 KB Output is correct
62 Correct 1269 ms 156124 KB Output is correct
63 Correct 2308 ms 156432 KB Output is correct
64 Correct 3548 ms 156384 KB Output is correct
65 Correct 3496 ms 132904 KB Output is correct
66 Correct 3417 ms 135352 KB Output is correct
67 Correct 3076 ms 134640 KB Output is correct
68 Correct 3014 ms 135460 KB Output is correct
69 Correct 2884 ms 130876 KB Output is correct
70 Correct 2676 ms 107552 KB Output is correct
71 Correct 3809 ms 158724 KB Output is correct
72 Correct 3840 ms 162932 KB Output is correct
73 Correct 3622 ms 162660 KB Output is correct
74 Correct 3650 ms 162252 KB Output is correct
75 Correct 3656 ms 156644 KB Output is correct
76 Correct 3236 ms 125376 KB Output is correct
77 Correct 3825 ms 174924 KB Output is correct
78 Correct 3404 ms 175036 KB Output is correct
79 Correct 3365 ms 174984 KB Output is correct
80 Correct 3792 ms 174488 KB Output is correct
81 Correct 3446 ms 167572 KB Output is correct
82 Correct 3010 ms 130140 KB Output is correct
83 Correct 3463 ms 175028 KB Output is correct
84 Correct 3561 ms 175028 KB Output is correct
85 Correct 3534 ms 175220 KB Output is correct
86 Correct 3380 ms 174528 KB Output is correct
87 Correct 3394 ms 167528 KB Output is correct
88 Correct 3204 ms 130096 KB Output is correct
89 Correct 2677 ms 137452 KB Output is correct
90 Correct 3027 ms 146720 KB Output is correct
91 Correct 3494 ms 158596 KB Output is correct
92 Correct 3558 ms 161912 KB Output is correct
93 Correct 3616 ms 166932 KB Output is correct
94 Correct 3598 ms 169124 KB Output is correct
95 Correct 3500 ms 172076 KB Output is correct
96 Correct 3428 ms 172276 KB Output is correct
97 Correct 3447 ms 172172 KB Output is correct
98 Correct 3512 ms 174380 KB Output is correct
99 Correct 3512 ms 172112 KB Output is correct
100 Correct 3486 ms 172184 KB Output is correct