Submission #691836

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
691836	2023-01-31T17:14:41 Z	overwatch9	Dynamic Diameter (CEOI19_diameter)	C++17	7 / 100	485 ms	25892 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, 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+1, 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+1, l, r);
        if (lens.find(og_len) != lens.end())
            lens.erase(lens.find(og_len));
        tree.update(1, 1, N+1, 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+1, 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	1108 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	1108 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	1104 KB	Output is correct
4	Correct	40 ms	1160 KB	Output is correct
5	Correct	194 ms	1464 KB	Output is correct
6	Correct	1 ms	980 KB	Output is correct
7	Correct	1 ms	1108 KB	Output is correct
8	Correct	3 ms	1108 KB	Output is correct
9	Correct	5 ms	1108 KB	Output is correct
10	Correct	44 ms	1252 KB	Output is correct
11	Correct	216 ms	1580 KB	Output is correct
12	Correct	5 ms	2260 KB	Output is correct
13	Correct	6 ms	2260 KB	Output is correct
14	Correct	11 ms	2260 KB	Output is correct
15	Correct	56 ms	2348 KB	Output is correct
16	Correct	252 ms	2840 KB	Output is correct
17	Correct	116 ms	25352 KB	Output is correct
18	Correct	118 ms	25280 KB	Output is correct
19	Correct	122 ms	25496 KB	Output is correct
20	Correct	187 ms	25404 KB	Output is correct
21	Correct	485 ms	25892 KB	Output is correct