Submission #691850

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
691850	2023-01-31T18:08:22 Z	overwatch9	Dynamic Diameter (CEOI19_diameter)	C++17	7 / 100	511 ms	25976 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	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	2 ms	980 KB	Output is correct
3	Correct	5 ms	1108 KB	Output is correct
4	Correct	41 ms	1108 KB	Output is correct
5	Correct	212 ms	1472 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	46 ms	1252 KB	Output is correct
11	Correct	221 ms	1668 KB	Output is correct
12	Correct	6 ms	2260 KB	Output is correct
13	Correct	6 ms	2260 KB	Output is correct
14	Correct	13 ms	2260 KB	Output is correct
15	Correct	67 ms	2388 KB	Output is correct
16	Correct	251 ms	2708 KB	Output is correct
17	Correct	115 ms	25276 KB	Output is correct
18	Correct	119 ms	25316 KB	Output is correct
19	Correct	131 ms	25268 KB	Output is correct
20	Correct	188 ms	25376 KB	Output is correct
21	Correct	511 ms	25976 KB	Output is correct