Submission #691849

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
691849	2023-01-31T18:07:17 Z	overwatch9	Dynamic Diameter (CEOI19_diameter)	C++17	7 / 100	527 ms	26076 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);
    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, 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));
        l = id[b];
        r = l + st_sz[b] - 1;
        tree.update(1, 1, N+1, l, r, 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	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	39 ms	1264 KB	Output is correct
5	Correct	205 ms	1612 KB	Output is correct
6	Correct	1 ms	1148 KB	Output is correct
7	Correct	1 ms	1236 KB	Output is correct
8	Correct	2 ms	1224 KB	Output is correct
9	Correct	6 ms	1236 KB	Output is correct
10	Correct	46 ms	1348 KB	Output is correct
11	Correct	218 ms	1696 KB	Output is correct
12	Correct	5 ms	2260 KB	Output is correct
13	Correct	7 ms	2260 KB	Output is correct
14	Correct	11 ms	2388 KB	Output is correct
15	Correct	54 ms	2472 KB	Output is correct
16	Correct	255 ms	2904 KB	Output is correct
17	Correct	115 ms	25396 KB	Output is correct
18	Correct	126 ms	25404 KB	Output is correct
19	Correct	123 ms	25544 KB	Output is correct
20	Correct	188 ms	25596 KB	Output is correct
21	Correct	527 ms	26076 KB	Output is correct