Submission #691316

#	Time	Username	Problem	Language	Result	Execution time	Memory
691316		overwatch9	Dynamic Diameter (CEOI19_diameter)	C++17	0 / 100	416 ms	22936 KiB

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, lc, 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]) {
        ll x = tree.query(1, 1, N, i.first, i.first + 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[id[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[id[b]] - 1);
        // lens.insert(new_len);
        // if (!lens.empty())
        //     last = *lens.rbegin();
        // if (lens.size() >= 2)
        //     last += *(--(--lens.end()));
        cout << last << '\n';
    }

}

Compilation message (stderr)

diameter.cpp: In function 'int main()':
diameter.cpp:157:12: warning: unused variable 'delta' [-Wunused-variable]
  157 |         ll delta = e - w;
      |            ^~~~~

• Subtask 1: 0 / 11
• Subtask 2: 0 / 13
• Subtask 3: 0 / 7
• Subtask 4: 0 / 18
• Subtask 5: 0 / 24
• Subtask 6: 0 / 27