Submission #691835

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
691835	2023-01-31T17:10:02 Z	overwatch9	Dynamic Diameter (CEOI19_diameter)	C++17	7 / 100	518 ms	26152 KB

diameter

// subtask4
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <set>
using namespace std;
using ll = long long;
const int MAX_N = 1e5 + 1;
vector <vector <pair <int, ll>>> adj;
struct edge {
    int a, b;
    ll w;
};
vector<edge> edges;
vector <int> st_sz, id;
 
vector <ll> path_len(MAX_N);
vector <int> euler;
vector <int> root_child;
 
int dfs(int s, int p, int rootc) {
    euler.push_back(s);
    int visited = 1;
    root_child[s] = rootc;
    for (auto i : adj[s]) {
        if (i.first == p)
            continue;
        path_len[i.first] = path_len[s] + i.second;
        if (s == 1)
            visited += dfs(i.first, s, i.first);
        else
            visited += dfs(i.first, s, rootc);
    }
    st_sz[s] = visited;
    return visited;
}
 
struct sgtree_node {
    ll val, lazy_val;
    bool updates_pending;
};
 
struct seg_tree {
 
    #define lc v*2
    #define rc v*2+1
 
    vector <sgtree_node> tree;
    int sz;
    seg_tree (int size) {
        sz = size;
        tree = vector <sgtree_node> (4 * size);
 
    };
 
    ll combine(ll lval, ll rval) {
        return max(lval, rval);
    }
 
    void pushup(int v) {
        tree[v].val = combine(tree[lc].val, tree[rc].val);
    }
 
    void pushdown(int v) {
        if (!tree[v].updates_pending)
            return;
        tree[lc].val += tree[v].lazy_val;
        tree[rc].val += tree[v].lazy_val;
        tree[lc].lazy_val += tree[v].lazy_val;
        tree[rc].lazy_val += tree[v].lazy_val;
        tree[v].lazy_val = 0;
        tree[v].updates_pending = false;
        tree[lc].updates_pending = tree[rc].updates_pending = true;
    }
    void build(int v, int tl, int tr, int l, int r, vector <ll> &arr) {
        if (tl == tr) {
            tree[v].val += arr[tl];
            return;
        }
        pushdown(v);
        int tm = (tl + tr) / 2;
        build(lc, tl, tm, l, r, arr);
        build(rc, tm+1, tr, l, r, arr);
        pushup(v);
    }
    void update(int v, int tl, int tr, int l, int r, ll lazy_val) {
        if (l > tr || r < tl)
            return;
        if (tl >= l && tr <= r) {
            tree[v].val += lazy_val;
            tree[v].updates_pending = true;
            tree[v].lazy_val += lazy_val;
            return;
        }
        pushdown(v);
        int tm = (tl + tr) / 2;
        update(lc, tl, tm, l, r, lazy_val);
        update(rc, tm+1, tr, l, r, lazy_val);
        pushup(v);
    }
    ll query(int v, int tl, int tr, int l, int r) {
        if (l > tr || r < tl)
            return 0;
        if (tl >= l && tr <= r)
            return tree[v].val;
        pushdown(v);
        int tm = (tl + tr) / 2;
        return combine(query(lc, tl, tm, l, r), query(rc, tm+1, tr, l, r));
    }
 
};  
 
int main() {
    int N, Q;
    ll W;
    cin >> N >> Q >> W;
 
    // initialise stuff
    adj = vector <vector <pair <int, ll>>> (N+1);
    edges = vector <edge> (N);
    st_sz = vector <int> (N+1);
    id = vector <int> (N+1);
    root_child = vector <int> (N+1);
 
    for (int i = 0; i < N-1; i++) {
        int a, b;
        ll w;
        cin >> a >> b >> w;
        edge tp;
        tp.a = a;
        tp.b = b;
        tp.w = w;
        edges[i] = tp;
        adj[a].push_back({b, w});
        adj[b].push_back({a, w});
    }
    euler.push_back(0);
    dfs(1, 1, 1);
    for (int i = 1; i <= N; i++)
        id[euler[i]] = i;
 
    seg_tree tree(N+1);
    tree.build(1, 1, N, 1, st_sz[1], path_len);
    multiset <ll> lens;
    for (auto i : adj[1]) {
      	int b = i.first;
        ll x = tree.query(1, 1, N, id[b], id[b] + st_sz[i.first] - 1);
        //cout << x << '\n';
        lens.insert(x);
    }
 
    ll last = 0;
    while (Q--) {
        ll d, e;
        cin >> d >> e;
        d = (d + last) % (N-1);
        e = (e + last) % (W);
        int a = edges[d].a, b = edges[d].b;
        if (path_len[a] > path_len[b])
            swap(a, b);
        ll w = edges[d].w;
        ll delta = e - w;
        edges[d].w = e;

        // ll og_len = tree.query(1, 1, N, id[b], id[b] + st_sz[b] - 1);
        // if (lens.find(og_len) != lens.end())
        //     lens.erase(lens.find(og_len));
 
        int rootc = root_child[b];
        int l = id[rootc];
        int r = l + st_sz[rootc] - 1;
        ll og_len = tree.query(1, 1, N, l, r);
        if (lens.find(og_len) != lens.end())
            lens.erase(lens.find(og_len));
        tree.update(1, 1, N, id[b], id[b] + st_sz[b] - 1, delta);
        
        l = id[rootc];
        r = l + st_sz[rootc] - 1;
        lens.insert(tree.query(1, 1, N, l, r));

        
        // ll new_len = tree.query(1, 1, N, id[b], id[b] + st_sz[b] - 1);

        // lens.insert(new_len);

        if (!lens.empty())
            last = *lens.rbegin();
        if (lens.size() >= 2)
            last += *(--(--lens.end()));
        cout << last << '\n';
    }
 
}

Subtask #1
0 / 11.0

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

Subtask #2
0 / 13.0

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

Subtask #3
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	980 KB	Output is correct
2	Correct	1 ms	980 KB	Output is correct
3	Correct	5 ms	1108 KB	Output is correct
4	Correct	41 ms	1124 KB	Output is correct
5	Correct	198 ms	1424 KB	Output is correct
6	Correct	1 ms	980 KB	Output is correct
7	Correct	1 ms	1108 KB	Output is correct
8	Correct	2 ms	1108 KB	Output is correct
9	Correct	6 ms	1236 KB	Output is correct
10	Correct	49 ms	1272 KB	Output is correct
11	Correct	229 ms	1656 KB	Output is correct
12	Correct	6 ms	2260 KB	Output is correct
13	Correct	7 ms	2260 KB	Output is correct
14	Correct	11 ms	2260 KB	Output is correct
15	Correct	56 ms	2356 KB	Output is correct
16	Correct	247 ms	2776 KB	Output is correct
17	Correct	129 ms	25384 KB	Output is correct
18	Correct	129 ms	25304 KB	Output is correct
19	Correct	131 ms	25372 KB	Output is correct
20	Correct	195 ms	25380 KB	Output is correct
21	Correct	518 ms	26152 KB	Output is correct