답안 #691829

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
691829	2023-01-31T16:43:43 Z	overwatch9	Dynamic Diameter (CEOI19_diameter)	C++17	7 / 100	509 ms	28976 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;
 
int dfs(int s, int p) {
    euler.push_back(s);
    int visited = 1;
    for (auto i : adj[s]) {
        if (i.first == p)
            continue;
        path_len[i.first] = path_len[s] + i.second;
        visited += dfs(i.first, s);
    }
    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 = false;
    }
    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);
 
 
    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);
    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));
 
        tree.update(1, 1, N, id[b], id[b] + st_sz[b] - 1, delta);
        
        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

#	결과	실행 시간	메모리	Grader output
1	Incorrect	1 ms	980 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #2
0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	1 ms	980 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #3
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	1108 KB	Output is correct
2	Correct	1 ms	980 KB	Output is correct
3	Correct	5 ms	1108 KB	Output is correct
4	Correct	42 ms	1304 KB	Output is correct
5	Correct	193 ms	2212 KB	Output is correct
6	Correct	1 ms	980 KB	Output is correct
7	Correct	2 ms	1104 KB	Output is correct
8	Correct	2 ms	1108 KB	Output is correct
9	Correct	6 ms	1232 KB	Output is correct
10	Correct	46 ms	1364 KB	Output is correct
11	Correct	220 ms	2484 KB	Output is correct
12	Correct	6 ms	2260 KB	Output is correct
13	Correct	7 ms	2260 KB	Output is correct
14	Correct	10 ms	2388 KB	Output is correct
15	Correct	57 ms	2676 KB	Output is correct
16	Correct	262 ms	3752 KB	Output is correct
17	Correct	125 ms	26124 KB	Output is correct
18	Correct	120 ms	26172 KB	Output is correct
19	Correct	132 ms	26120 KB	Output is correct
20	Correct	187 ms	26496 KB	Output is correct
21	Correct	505 ms	27932 KB	Output is correct