oj.uz

Submission #578810

# Submission time Handle Problem Language Result Execution time Memory
578810 2022-06-18T04:42:20 Z talant117408 Dynamic Diameter (CEOI19_diameter) C++17
49 / 100
 2577 ms 30924 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;
ll df, vf;
int n, q;
ll w;

void find_furthest(int v, int p, ll dist = 0) {
    if (dist > df) {
        df = dist;
        vf = v;
    }
    for (auto to : graph[v]) {
        if (to.first == p) continue;
        find_furthest(to.first, v, dist+to.second);
    }
}

void subtask3() {
    for (auto to : edges) {
        if (to.first.first != 1) {
            return;
        }
    }
    set <pair <ll, int>, greater <pair <ll, int>>> st;
    for (auto to : edges) {
        st.insert(mp(to.second, to.first.second));
    }
    ll last = 0;
    while (q--) {
        ll d, e;
        cin >> d >> e;
        d = (d + last) % (n - 1);
        e = (e + last) % w;
        auto &c = edges[d].second;
        auto b = edges[d].first.second;
        st.erase(st.find(mp(c, b)));
        c = e;
        st.insert(mp(c, b));
        ll ans = 0;
        ll cnt = 0;
        for (auto to : st) {
            ans += to.first;
            if (++cnt > 1) break;
        }
        cout << ans << endl;
        last = ans;
    }
    exit(0);
}

void subtask4() {
    vector <ll> ans_for(n+1);
    vector <pll> mx_child(n+1), dist_child(n+1);
    set <pair <ll, int>, greater <pair <ll, int>>> st;
    for (auto to : edges) {
        auto a = to.first.first;
        auto b = to.first.second;
        if (!(a*2 != b || a*2+1 != b)) {
            return;
        }
        if (a*2 == b) dist_child[a].first = to.second;
        else dist_child[a].second = to.second;
    }
    
    for (int i = 1; i <= n; i++) {
        if (sz(graph[i]) == 1) {
            int x = i;
            while (x) {
                if (x*2 <= n) mx_child[x].first = max(mx_child[x*2].first, mx_child[x*2].second)+dist_child[x].first;
                if (x*2+1 <= n) mx_child[x].second = max(mx_child[x*2+1].first, mx_child[x*2+1].second)+dist_child[x].second;
                x >>= 1;
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        st.insert(mp(mx_child[i].first+mx_child[i].second, i));
    }
    
    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;
        int x = (b >> 1);
        if (a*2 == b) dist_child[a].first = e;
        else dist_child[a].second = e;
        while (x) {
            st.erase(st.find(mp(mx_child[x].first+mx_child[x].second, x)));
            if (x*2 <= n) mx_child[x].first = max(mx_child[x*2].first, mx_child[x*2].second)+dist_child[x].first;
            if (x*2+1 <= n) mx_child[x].second = max(mx_child[x*2+1].first, mx_child[x*2+1].second)+dist_child[x].second;
            st.insert(mp(mx_child[x].first+mx_child[x].second, x));
            x >>= 1;
        }
        cout << (*st.begin()).first << endl;
        last = (*st.begin()).first;
    }
    exit(0);
}

ll tree[N*4], lz[N*4];
int depth[N], timer;
pii range[N];
int parent[N];
int origin = 1;

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

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

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

void dfs(int v = 1, int p = 1, ll dist = 0) {
    range[v].first = ++timer;
    update(1, 1, n, timer, timer, dist);
    parent[v] = origin;
    for (auto to : graph[v]) {
        if (to.first == p) continue;
        depth[to.first] = depth[v] + 1;
        if (v == 1) origin = to.first;
        dfs(to.first, v, dist+to.second);
    }
    range[v].second = timer;
}

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));
    }
    
    
    if (n <= 5000) {
        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;
            graph[a].erase(graph[a].find(mp(b, c)));
            graph[b].erase(graph[b].find(mp(a, c)));
            c = e;
            graph[a].insert(mp(b, c));
            graph[b].insert(mp(a, c));
            df = vf = 0;
            find_furthest(1, 1);
            df = 0;
            find_furthest(vf, vf);
            cout << df << endl;
            last = df;
        }
        return;
    }
    subtask3();
    subtask4();
    
    dfs();
    set <pair <ll, int>, greater <pair <ll, int>>> st;
    for (auto to : graph[1]) {
        st.insert(mp(get(1, 1, n, range[to.first].first, range[to.first].second), to.first));
    }
    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 (depth[a] > depth[b]) swap(a, b);
        st.erase(st.find(mp(get(1, 1, n, range[parent[b]].first, range[parent[b]].second), parent[b])));
        update(1, 1, n, range[b].first, range[b].second, e-c);
        c = e;
        st.insert(mp(get(1, 1, n, range[parent[b]].first, range[parent[b]].second), parent[b]));
        ll res = 0;
        ll cnt = 0;
        for (auto to : st) {
            res += to.first;
            if (++cnt > 1) break;
        }
        cout << res << endl;
        last = res;
    }
}

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 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 4992 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct
6 Correct 3 ms 4948 KB Output is correct
7 Correct 3 ms 4948 KB Output is correct
8 Correct 3 ms 4948 KB Output is correct
9 Correct 2 ms 4948 KB Output is correct
10 Correct 3 ms 4948 KB Output is correct
11 Correct 3 ms 4948 KB Output is correct
12 Correct 3 ms 5028 KB Output is correct
13 Correct 3 ms 4948 KB Output is correct
14 Correct 3 ms 4948 KB Output is correct
15 Correct 3 ms 4948 KB Output is correct
16 Correct 3 ms 4948 KB Output is correct
17 Correct 4 ms 4948 KB Output is correct
18 Correct 4 ms 4948 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 4992 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct
6 Correct 3 ms 4948 KB Output is correct
7 Correct 3 ms 4948 KB Output is correct
8 Correct 3 ms 4948 KB Output is correct
9 Correct 2 ms 4948 KB Output is correct
10 Correct 3 ms 4948 KB Output is correct
11 Correct 3 ms 4948 KB Output is correct
12 Correct 3 ms 5028 KB Output is correct
13 Correct 3 ms 4948 KB Output is correct
14 Correct 3 ms 4948 KB Output is correct
15 Correct 3 ms 4948 KB Output is correct
16 Correct 3 ms 4948 KB Output is correct
17 Correct 4 ms 4948 KB Output is correct
18 Correct 4 ms 4948 KB Output is correct
19 Correct 228 ms 5172 KB Output is correct
20 Correct 231 ms 5176 KB Output is correct
21 Correct 271 ms 5180 KB Output is correct
22 Correct 308 ms 5332 KB Output is correct
23 Correct 1716 ms 5752 KB Output is correct
24 Correct 1920 ms 5868 KB Output is correct
25 Correct 1986 ms 5908 KB Output is correct
26 Correct 2452 ms 6088 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 4 ms 4948 KB Output is correct
3 Correct 5 ms 5076 KB Output is correct
4 Correct 22 ms 5092 KB Output is correct
5 Correct 118 ms 5436 KB Output is correct
6 Correct 3 ms 4948 KB Output is correct
7 Correct 3 ms 5076 KB Output is correct
8 Correct 5 ms 5076 KB Output is correct
9 Correct 32 ms 5076 KB Output is correct
10 Correct 343 ms 5220 KB Output is correct
11 Correct 1558 ms 5548 KB Output is correct
12 Correct 6 ms 5972 KB Output is correct
13 Correct 7 ms 5972 KB Output is correct
14 Correct 9 ms 5972 KB Output is correct
15 Correct 17 ms 6192 KB Output is correct
16 Correct 53 ms 6444 KB Output is correct
17 Correct 90 ms 25328 KB Output is correct
18 Correct 92 ms 25340 KB Output is correct
19 Correct 118 ms 25380 KB Output is correct
20 Correct 109 ms 25440 KB Output is correct
21 Correct 215 ms 25924 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 5172 KB Output is correct
2 Correct 257 ms 5224 KB Output is correct
3 Correct 1231 ms 5492 KB Output is correct
4 Correct 2577 ms 5776 KB Output is correct
5 Correct 12 ms 7376 KB Output is correct
6 Correct 25 ms 7544 KB Output is correct
7 Correct 90 ms 7652 KB Output is correct
8 Correct 173 ms 7940 KB Output is correct
9 Correct 39 ms 17096 KB Output is correct
10 Correct 65 ms 17200 KB Output is correct
11 Correct 157 ms 17376 KB Output is correct
12 Correct 328 ms 17696 KB Output is correct
13 Correct 88 ms 29228 KB Output is correct
14 Correct 100 ms 29344 KB Output is correct
15 Correct 260 ms 29520 KB Output is correct
16 Correct 345 ms 29912 KB Output is correct
17 Correct 742 ms 29968 KB Output is correct

Subtask #5
0 / 24.0

# Verdict Execution time Memory Grader output
1 Incorrect 748 ms 30924 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 4992 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct
6 Correct 3 ms 4948 KB Output is correct
7 Correct 3 ms 4948 KB Output is correct
8 Correct 3 ms 4948 KB Output is correct
9 Correct 2 ms 4948 KB Output is correct
10 Correct 3 ms 4948 KB Output is correct
11 Correct 3 ms 4948 KB Output is correct
12 Correct 3 ms 5028 KB Output is correct
13 Correct 3 ms 4948 KB Output is correct
14 Correct 3 ms 4948 KB Output is correct
15 Correct 3 ms 4948 KB Output is correct
16 Correct 3 ms 4948 KB Output is correct
17 Correct 4 ms 4948 KB Output is correct
18 Correct 4 ms 4948 KB Output is correct
19 Correct 228 ms 5172 KB Output is correct
20 Correct 231 ms 5176 KB Output is correct
21 Correct 271 ms 5180 KB Output is correct
22 Correct 308 ms 5332 KB Output is correct
23 Correct 1716 ms 5752 KB Output is correct
24 Correct 1920 ms 5868 KB Output is correct
25 Correct 1986 ms 5908 KB Output is correct
26 Correct 2452 ms 6088 KB Output is correct
27 Correct 2 ms 4948 KB Output is correct
28 Correct 4 ms 4948 KB Output is correct
29 Correct 5 ms 5076 KB Output is correct
30 Correct 22 ms 5092 KB Output is correct
31 Correct 118 ms 5436 KB Output is correct
32 Correct 3 ms 4948 KB Output is correct
33 Correct 3 ms 5076 KB Output is correct
34 Correct 5 ms 5076 KB Output is correct
35 Correct 32 ms 5076 KB Output is correct
36 Correct 343 ms 5220 KB Output is correct
37 Correct 1558 ms 5548 KB Output is correct
38 Correct 6 ms 5972 KB Output is correct
39 Correct 7 ms 5972 KB Output is correct
40 Correct 9 ms 5972 KB Output is correct
41 Correct 17 ms 6192 KB Output is correct
42 Correct 53 ms 6444 KB Output is correct
43 Correct 90 ms 25328 KB Output is correct
44 Correct 92 ms 25340 KB Output is correct
45 Correct 118 ms 25380 KB Output is correct
46 Correct 109 ms 25440 KB Output is correct
47 Correct 215 ms 25924 KB Output is correct
48 Correct 35 ms 5172 KB Output is correct
49 Correct 257 ms 5224 KB Output is correct
50 Correct 1231 ms 5492 KB Output is correct
51 Correct 2577 ms 5776 KB Output is correct
52 Correct 12 ms 7376 KB Output is correct
53 Correct 25 ms 7544 KB Output is correct
54 Correct 90 ms 7652 KB Output is correct
55 Correct 173 ms 7940 KB Output is correct
56 Correct 39 ms 17096 KB Output is correct
57 Correct 65 ms 17200 KB Output is correct
58 Correct 157 ms 17376 KB Output is correct
59 Correct 328 ms 17696 KB Output is correct
60 Correct 88 ms 29228 KB Output is correct
61 Correct 100 ms 29344 KB Output is correct
62 Correct 260 ms 29520 KB Output is correct
63 Correct 345 ms 29912 KB Output is correct
64 Correct 742 ms 29968 KB Output is correct
65 Incorrect 748 ms 30924 KB Output isn't correct
66 Halted 0 ms 0 KB -