Submission #689778

#	Time	Username	Problem	Language	Result	Execution time	Memory
689778		overwatch9	Dynamic Diameter (CEOI19_diameter)	C++17	18 / 100	356 ms	19404 KiB

diameter

// subtask4
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;
using ll = long long;
const int MAX_N = 1e5 + 1;
vector <pair <int, ll>> adj[MAX_N];
struct edge {
    int a, b;
    ll w;
};
edge edges[MAX_N];
int parent[MAX_N];
vector <ll> seg_tree, value, diameter;
int seg_sz;
void update(ll x, int a) {
    seg_tree[a] = x;
    value[a] = x;
    for (a; a >= 1; a /= 2) {
        if (a * 2 >= seg_sz * 2)
            continue;
        diameter[a] = max({diameter[a*2], diameter[a*2+1], seg_tree[a*2] + seg_tree[a*2+1]});
        seg_tree[a] = value[a] + max(seg_tree[a*2], seg_tree[a*2+1]);
    }
}
void dfs(int s, int p) {
    parent[s] = p;
    for (auto i : adj[s]) {
        if (i.first == p)
            continue;
        dfs(i.first, s);
    }
}
int main() {
    int N, Q;
    ll W;
    cin >> N >> Q >> W;
    seg_sz = pow(2, ceil(log2(N)));
    seg_tree.resize(seg_sz * 2);
    value.resize(seg_sz * 2);
    diameter.resize(seg_sz * 2);
    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});
    }
    dfs(1, 1);
    for (int i = 0; i < N-1; i++) {
        int a = edges[i].a;
        int b = edges[i].b;
        ll w = edges[i].w;
        if (parent[a] == b) {
            update(w, a);
        } else {
            update(w, b);
        }
    }
    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 (parent[a] == b) {
            update(e, a);
        } else {
            update(e, b);
        }
        edges[d].w = e;
        last = diameter[1];
        cout << last << '\n';
    }
}

Compilation message (stderr)

diameter.cpp: In function 'void update(ll, int)':
diameter.cpp:21:10: warning: statement has no effect [-Wunused-value]
   21 |     for (a; a >= 1; a /= 2) {
      |          ^

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