Submission #692506

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
692506	2023-02-01T16:14:12 Z	overwatch9	Dynamic Diameter (CEOI19_diameter)	C++17	7 / 100	579 ms	28216 KB

diameter

// subtask5
#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);
    root_child[s] = rootc;
    int visited = 1;
    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;
        }
        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, 0);
    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));
        l = id[b];
        r = l + st_sz[b] - 1;
        tree.update(1, 1, N, l, r, 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	2 ms	1100 KB	Output is correct
2	Correct	1 ms	1096 KB	Output is correct
3	Correct	7 ms	1108 KB	Output is correct
4	Correct	45 ms	1312 KB	Output is correct
5	Correct	200 ms	2184 KB	Output is correct
6	Correct	1 ms	1096 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	1168 KB	Output is correct
10	Correct	47 ms	1364 KB	Output is correct
11	Correct	232 ms	2520 KB	Output is correct
12	Correct	6 ms	2388 KB	Output is correct
13	Correct	6 ms	2260 KB	Output is correct
14	Correct	11 ms	2388 KB	Output is correct
15	Correct	58 ms	2608 KB	Output is correct
16	Correct	258 ms	3764 KB	Output is correct
17	Correct	119 ms	26708 KB	Output is correct
18	Correct	118 ms	26548 KB	Output is correct
19	Correct	124 ms	26600 KB	Output is correct
20	Correct	215 ms	26808 KB	Output is correct
21	Correct	579 ms	28216 KB	Output is correct