oj.uz

Submission #934458

# Submission time Handle Problem Language Result Execution time Memory
934458 2024-02-27T10:51:32 Z sysia Dynamic Diameter (CEOI19_diameter) C++17
100 / 100
 3657 ms 187940 KB 
//Sylwia Sapkowska
#include <bits/stdc++.h>
#pragma GCC optimize("O3", "unroll-loops")
using namespace std;

void __print(int x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << "'" << x << "'";}
void __print(const char *x) {cerr << '"' << x << '"';}
void __print(const string &x) {cerr << '"' << x << '"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ", "; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? ", " : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifdef LOCAL
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif

#define int long long
typedef pair<int, int> T;
const int oo = 1e18, oo2 = 1e9+7, K = 17;
const int mod = 998244353;

struct Tree{
    vector<int>tab, lazy;
    int size = 1;

    Tree(int n){
        while (size < n) size*=2;
        tab.assign(2*size, -oo);
        lazy.assign(2*size, 0);
    }
    //dodaj na przedziale max na przedziale

    void update(int x, int lx, int rx, int pos, int val){
        if (lx == rx) {
            tab[x] = val;
            return;
        }
        int m = (lx+rx)/2;
        push(x);
        if (pos <= m) update(2*x, lx, m, pos, val);
        else update(2*x+1, m+1, rx, pos, val);
        tab[x] = max(tab[2*x], tab[2*x+1]);
    }

    void update(int x, int lx, int rx, int l, int r, int val){
        if (lx > r || rx < l) return;
        if (lx >= l && rx <= r){
            tab[x] += val;
            lazy[x] += val;
            return;
        }
        int m = (lx+rx)/2;
        push(x);
        update(2*x, lx, m, l, r, val);
        update(2*x+1, m+1, rx, l, r, val);
        tab[x] = max(tab[2*x], tab[2*x+1]);
    }

    void push(int x){
        if (!lazy[x]) return;
        for (auto k: {2*x, 2*x+1}){
            tab[k] += lazy[x];
            lazy[k] += lazy[x];
        }
        lazy[x] = 0;
    }

    int query(int x, int lx, int rx, int l, int r){
        if (lx > r || rx < l) return -oo;
        if (lx >= l && rx <= r) return tab[x];
        int m = (lx+rx)/2;
        push(x);
        return max(query(2*x, lx, m, l, r), query(2*x+1, m+1, rx, l, r));
    }
};

void solve(){
    int n, q, w; cin >> n >> q >> w;
    vector<vector<T>>g(n+1);
    vector<int>cost(n);
    for (int i = 1; i<n; i++){
        int a, b; cin >> a >> b >> cost[i];
        g[a].emplace_back(b, i);
        g[b].emplace_back(a, i);
    }   
    vector<int>sz(n+1);
    vector<bool>vis(n+1); 
    function<int(int, int)>getsz = [&](int v, int pa){
        sz[v] = 1;
        for (auto [x, i]: g[v]){
            if (x == pa || vis[x]) continue;
            sz[v] += getsz(x, v);
        }
        return sz[v];
    };
    function<int(int, int, int)>get_centroid = [&](int v, int pa, int ms){
        for (auto [x, i]: g[v]){
            if (x == pa || vis[x]) continue;
            if (2*sz[x] > ms) return get_centroid(x, v, ms);
        }
        return v;
    };

    int all = 0;
    Tree t(n * K);
    vector<multiset<int>>vals(n+1);
    vector<int>depth(n+1), ord;
    vector<vector<array<int, 6>>>where(n+1);
    multiset<int>ans;
    auto get = [&](int c){
        if ((int)vals[c].empty()) return -oo;
        if ((int)vals[c].size() == 1) return *vals[c].rbegin();
        debug(c, vals[c]);
        auto it = --(vals[c].end());
        int ans = *it;
        it--;
        ans += *it;
        debug(ans);
        return ans;
    };
    function<void(int)>centroid = [&](int c){
        c = get_centroid(c, c, getsz(c, c));
        getsz(c, c);
        function<void(int, int, int, int)>dfs = [&](int v, int pa, int from, int pos){
            for (auto [x, i]: g[v]){
                if (x == pa || vis[x]) continue;
                from = (v == pa ? x : from);
                pos = (v == pa ? all : pos);
                // if (v == pa) SZ[{c, from}] = {sz[from], all};
                // pos[{c, i}] = {all++, from};
                // ord.emplace_back(sz[x]);
                where[i].emplace_back(array<int, 6>{c, all++, from, pos, sz[from], sz[x]});
                depth[x] = depth[v] + cost[i];
                t.update(1, 0, t.size-1, all-1, depth[x]);
                dfs(x, v, from, pos);
                if (v == pa){
                    vals[c].insert(t.query(1, 0, t.size-1, pos, pos+sz[x]-1));
                }
            }
        };
        depth[c] = 0;
        dfs(c, c, -1, -1);
        ans.insert(get(c));
        debug(c, vals[c]);
        vis[c] = 1;
        for (auto [x, i]: g[c]){
            if (!vis[x]){
                centroid(x);
            }
        }
    };
    centroid(1);
    int last = 0;
    debug(ord);
    while (q--){
        int i, waga; cin >> i >> waga;
        i = (i+last)%(n-1) + 1;
        waga = (waga+last)%w;
        debug(i, cost[i], waga);
        int diff = waga - cost[i];
        cost[i] = waga;
        for (auto [c, pos, from, lfrom, szfr, szx]: where[i]){
            debug(c, all, from);
            ans.erase(ans.find(get(c)));
            vals[c].erase(vals[c].find(t.query(1, 0, t.size-1, lfrom, lfrom+szfr-1)));
            t.update(1, 0, t.size-1, pos, pos+szx-1, diff);
            vals[c].insert(t.query(1, 0, t.size-1, lfrom, lfrom+szfr-1));
            ans.insert(get(c));
        } 
        last = *ans.rbegin();
        cout << last << "\n";
        // return;
    }
}

int32_t main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    solve();

    return 0;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 604 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 1 ms 348 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 604 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 23 ms 2108 KB Output is correct
20 Correct 21 ms 2140 KB Output is correct
21 Correct 30 ms 2204 KB Output is correct
22 Correct 29 ms 2396 KB Output is correct
23 Correct 35 ms 7736 KB Output is correct
24 Correct 45 ms 8612 KB Output is correct
25 Correct 63 ms 9300 KB Output is correct
26 Correct 61 ms 10216 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 11 ms 516 KB Output is correct
5 Correct 51 ms 852 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 1116 KB Output is correct
8 Correct 1 ms 1116 KB Output is correct
9 Correct 3 ms 1116 KB Output is correct
10 Correct 15 ms 1116 KB Output is correct
11 Correct 71 ms 1364 KB Output is correct
12 Correct 6 ms 6160 KB Output is correct
13 Correct 6 ms 5980 KB Output is correct
14 Correct 8 ms 5976 KB Output is correct
15 Correct 27 ms 6216 KB Output is correct
16 Correct 102 ms 6524 KB Output is correct
17 Correct 128 ms 98096 KB Output is correct
18 Correct 163 ms 97984 KB Output is correct
19 Correct 170 ms 98240 KB Output is correct
20 Correct 180 ms 98244 KB Output is correct
21 Correct 332 ms 99076 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2140 KB Output is correct
2 Correct 32 ms 2188 KB Output is correct
3 Correct 149 ms 2384 KB Output is correct
4 Correct 300 ms 2908 KB Output is correct
5 Correct 40 ms 18512 KB Output is correct
6 Correct 81 ms 18524 KB Output is correct
7 Correct 283 ms 18960 KB Output is correct
8 Correct 533 ms 19280 KB Output is correct
9 Correct 183 ms 84560 KB Output is correct
10 Correct 251 ms 84820 KB Output is correct
11 Correct 606 ms 85112 KB Output is correct
12 Correct 1047 ms 85528 KB Output is correct
13 Correct 382 ms 169520 KB Output is correct
14 Correct 468 ms 169492 KB Output is correct
15 Correct 917 ms 169740 KB Output is correct
16 Correct 1467 ms 170580 KB Output is correct
17 Correct 2986 ms 170644 KB Output is correct

Subtask #5
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2125 ms 163904 KB Output is correct
2 Correct 2243 ms 165736 KB Output is correct
3 Correct 2274 ms 165640 KB Output is correct
4 Correct 2264 ms 164800 KB Output is correct
5 Correct 2163 ms 160612 KB Output is correct
6 Correct 1846 ms 133296 KB Output is correct
7 Correct 2999 ms 178120 KB Output is correct
8 Correct 2993 ms 182128 KB Output is correct
9 Correct 3056 ms 181888 KB Output is correct
10 Correct 3050 ms 181620 KB Output is correct
11 Correct 2924 ms 175560 KB Output is correct
12 Correct 2494 ms 146580 KB Output is correct
13 Correct 3293 ms 187584 KB Output is correct
14 Correct 3356 ms 187364 KB Output is correct
15 Correct 3329 ms 187940 KB Output is correct
16 Correct 3399 ms 187120 KB Output is correct
17 Correct 3176 ms 181976 KB Output is correct
18 Correct 2621 ms 152260 KB Output is correct
19 Correct 3657 ms 187356 KB Output is correct
20 Correct 3446 ms 187500 KB Output is correct
21 Correct 3418 ms 187732 KB Output is correct
22 Correct 3477 ms 187096 KB Output is correct
23 Correct 3435 ms 182024 KB Output is correct
24 Correct 2739 ms 152004 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 604 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 23 ms 2108 KB Output is correct
20 Correct 21 ms 2140 KB Output is correct
21 Correct 30 ms 2204 KB Output is correct
22 Correct 29 ms 2396 KB Output is correct
23 Correct 35 ms 7736 KB Output is correct
24 Correct 45 ms 8612 KB Output is correct
25 Correct 63 ms 9300 KB Output is correct
26 Correct 61 ms 10216 KB Output is correct
27 Correct 1 ms 348 KB Output is correct
28 Correct 0 ms 348 KB Output is correct
29 Correct 1 ms 348 KB Output is correct
30 Correct 11 ms 516 KB Output is correct
31 Correct 51 ms 852 KB Output is correct
32 Correct 0 ms 348 KB Output is correct
33 Correct 1 ms 1116 KB Output is correct
34 Correct 1 ms 1116 KB Output is correct
35 Correct 3 ms 1116 KB Output is correct
36 Correct 15 ms 1116 KB Output is correct
37 Correct 71 ms 1364 KB Output is correct
38 Correct 6 ms 6160 KB Output is correct
39 Correct 6 ms 5980 KB Output is correct
40 Correct 8 ms 5976 KB Output is correct
41 Correct 27 ms 6216 KB Output is correct
42 Correct 102 ms 6524 KB Output is correct
43 Correct 128 ms 98096 KB Output is correct
44 Correct 163 ms 97984 KB Output is correct
45 Correct 170 ms 98240 KB Output is correct
46 Correct 180 ms 98244 KB Output is correct
47 Correct 332 ms 99076 KB Output is correct
48 Correct 6 ms 2140 KB Output is correct
49 Correct 32 ms 2188 KB Output is correct
50 Correct 149 ms 2384 KB Output is correct
51 Correct 300 ms 2908 KB Output is correct
52 Correct 40 ms 18512 KB Output is correct
53 Correct 81 ms 18524 KB Output is correct
54 Correct 283 ms 18960 KB Output is correct
55 Correct 533 ms 19280 KB Output is correct
56 Correct 183 ms 84560 KB Output is correct
57 Correct 251 ms 84820 KB Output is correct
58 Correct 606 ms 85112 KB Output is correct
59 Correct 1047 ms 85528 KB Output is correct
60 Correct 382 ms 169520 KB Output is correct
61 Correct 468 ms 169492 KB Output is correct
62 Correct 917 ms 169740 KB Output is correct
63 Correct 1467 ms 170580 KB Output is correct
64 Correct 2986 ms 170644 KB Output is correct
65 Correct 2125 ms 163904 KB Output is correct
66 Correct 2243 ms 165736 KB Output is correct
67 Correct 2274 ms 165640 KB Output is correct
68 Correct 2264 ms 164800 KB Output is correct
69 Correct 2163 ms 160612 KB Output is correct
70 Correct 1846 ms 133296 KB Output is correct
71 Correct 2999 ms 178120 KB Output is correct
72 Correct 2993 ms 182128 KB Output is correct
73 Correct 3056 ms 181888 KB Output is correct
74 Correct 3050 ms 181620 KB Output is correct
75 Correct 2924 ms 175560 KB Output is correct
76 Correct 2494 ms 146580 KB Output is correct
77 Correct 3293 ms 187584 KB Output is correct
78 Correct 3356 ms 187364 KB Output is correct
79 Correct 3329 ms 187940 KB Output is correct
80 Correct 3399 ms 187120 KB Output is correct
81 Correct 3176 ms 181976 KB Output is correct
82 Correct 2621 ms 152260 KB Output is correct
83 Correct 3657 ms 187356 KB Output is correct
84 Correct 3446 ms 187500 KB Output is correct
85 Correct 3418 ms 187732 KB Output is correct
86 Correct 3477 ms 187096 KB Output is correct
87 Correct 3435 ms 182024 KB Output is correct
88 Correct 2739 ms 152004 KB Output is correct
89 Correct 2260 ms 167576 KB Output is correct
90 Correct 2537 ms 172960 KB Output is correct
91 Correct 2967 ms 178924 KB Output is correct
92 Correct 3168 ms 181560 KB Output is correct
93 Correct 3252 ms 183940 KB Output is correct
94 Correct 3244 ms 186856 KB Output is correct
95 Correct 3358 ms 186928 KB Output is correct
96 Correct 3252 ms 186840 KB Output is correct
97 Correct 3337 ms 186648 KB Output is correct
98 Correct 3372 ms 186880 KB Output is correct
99 Correct 3320 ms 187256 KB Output is correct
100 Correct 3370 ms 186704 KB Output is correct