Submission #1249069

#	Time	Username	Problem	Language	Result	Execution time	Memory
1249069		cpdreamer	Dynamic Diameter (CEOI19_diameter)	C++20	100 / 100	181 ms	56360 KiB

diameter

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int N = 1e5 + 9;

struct node {
    long long a = 0, b = 0, c = 0, d = 0, e = 0;
    node operator+(const node &oth) const {
        node ret;
        ret.a = max(a, oth.a);
        ret.b = max(b, oth.b);
        ret.c = max(max(c, oth.c), a + oth.b);
        ret.d = max(max(d, oth.d), b + oth.a);
        ret.e = max(max(e, oth.e), max(c + oth.a, a + oth.d));
        return ret;
    }
};

struct ST {
#define lc (n << 1)
#define rc ((n << 1) | 1)
    long long lazy[4 * N * 2];
    node t[4 * N * 2];

    ST() {
        fill(lazy, lazy + 4 * N * 2, 0);
    }

    inline void push(int n, int b, int e) {
        if (lazy[n] == 0) return;
        long long v = lazy[n];
        t[n].a += v;
        t[n].b -= 2 * v;
        t[n].c -= v;
        t[n].d -= v;
        if (b != e) {
            lazy[lc] += v;
            lazy[rc] += v;
        }
        lazy[n] = 0;
    }

    inline void pull(int n) {
        t[n] = t[lc] + t[rc];
    }

    void build(int n, int b, int e, const vector<long long>& dist, const vector<int>& q) {
        if (b == e) {
            t[n].a = dist[q[b]];
            t[n].b = -2 * dist[q[b]];
            t[n].c = -dist[q[b]];
            t[n].d = -dist[q[b]];
            t[n].e = 0;
            return;
        }
        int mid = (b + e) >> 1;
        build(lc, b, mid, dist, q);
        build(rc, mid + 1, e, dist, q);
        pull(n);
    }

    void upd(int n, int b, int e, int i, int j, long long v) {
        push(n, b, e);
        if (j < b || e < i) return;
        if (i <= b && e <= j) {
            lazy[n] += v;
            push(n, b, e);
            return;
        }
        int mid = (b + e) >> 1;
        upd(lc, b, mid, i, j, v);
        upd(rc, mid + 1, e, i, j, v);
        pull(n);
    }
} t;

long long W[N];
vector<pair<int, int>> g[N];
int T, st[N * 2], en[N * 2], pos[N];
vector<long long> dist;
vector<int> q_nodes;

void dfs(int u, int p = 0, long long current_dist = 0) {
    st[u] = ++T;
    q_nodes[T] = u;
    dist[u] = current_dist;
    for (auto e : g[u]) {
        int v = e.first, i = e.second;
        if (v == p) continue;
        pos[i] = v;
        dfs(v, u, current_dist + W[i]);
        q_nodes[++T] = u;
    }
    en[u] = T;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, q;
    long long mod;
    cin >> n >> q >> mod;

    dist.resize(n + 1);
    q_nodes.resize(2 * n);

    for (int i = 1; i < n; i++) {
        int u, v;
        long long w;
        cin >> u >> v >> w;
        g[u].push_back({v, i});
        g[v].push_back({u, i});
        W[i] = w;
    }

    T = 0;
    dfs(1);

    t.build(1, 1, T, dist, q_nodes);

    long long last = 0;
    while (q--) {
        int d;
        long long e;
        cin >> d >> e;
        d = (d + last) % (n - 1) + 1;
        e = (e + last) % mod;
        t.upd(1, 1, T, st[pos[d]], en[pos[d]], e - W[d]);
        W[d] = e;
        last = t.t[1].e;
        cout << last << "\n";
    }

    return 0;
}

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