Submission #572853

#	Time	Username	Problem	Language	Result	Execution time	Memory
572853		piOOE	Dynamic Diameter (CEOI19_diameter)	C++17	100 / 100	266 ms	41980 KiB

diameter

#include <bits/stdc++.h>

using namespace std;

#define sz(x) ((int)size(x))
#define all(x) begin(x), end(x)
#define trace(x) cout << #x << ": " << (x) << endl;

typedef long long ll;

mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

int rand(int l, int r) { return (int) ((ll) rnd() % (r - l + 1)) + l; }

const int N = 100000, N_ = (1 << 18);

struct node {
    ll sum = 0, mind = 0, maxd = 0, max12 = 0, max23 = 0, ans = 0;
    node shift(ll x) {
        return node{sum + x, mind + x, maxd + x, max12 - x, max23 - x, ans};
    }

    static node create(char c, ll x) {
        if (c == '(') {
            return node{x, 0, x, 0, x, x};
        } else {
            return node{-x, -x, 0, 2 * x, x, x};
        }
    }
} t[N_ * 2];


node mrg(node a, node b) {
    b = b.shift(a.sum);
    node c;
    c.sum = b.sum;
    c.mind = min(a.mind, b.mind);
    c.maxd = max(a.maxd, b.maxd);
    c.max12 = max({a.max12, b.max12, a.maxd - b.mind * 2});
    c.max23 = max({a.max23, b.max23, b.maxd - a.mind * 2});
    c.ans = max({a.ans, b.ans, a.max12 + b.maxd, a.maxd + b.max23});
    return c;
}

int sz = 1;

string s;

ll W[N];

int op[N], cl[N], idx[N * 2], T = 0;

void init(int n) {
    while (sz < n) sz <<= 1;
    for (int i = 0; i < n; ++i) {
        t[i + sz] = node::create(s[i], W[idx[i]]);
    }
    for (int i = sz - 1; i > 0; --i) {
        t[i] = mrg(t[i << 1], t[i << 1 | 1]);
    }
}

void modify(int i) {
    t[i + sz] = node::create(s[i], W[idx[i]]);
    i += sz;
    i >>= 1;
    while (i) {
        t[i] = mrg(t[i << 1], t[i << 1 | 1]);
        i >>= 1;
    }
}

vector<pair<int, int>> g[N];

void dfs(int v, int p) {
    for (auto [to, i] : g[v]) {
        if (to != p) {
            op[i] = T++;
            idx[op[i]] = i;
            s += '(';
            dfs(to, v);
            cl[i] = T++;
            s += ')';
            idx[cl[i]] = i;
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, q;
    cin >> n >> q;
    ll w;
    cin >> w;
    for (int i = 0; i < n - 1; ++i) {
        int a, b;
        cin >> a >> b;
        --a, --b;
        g[a].emplace_back(b, i);
        g[b].emplace_back(a, i);
        cin >> W[i];
    }
    dfs(0, -1);
    init(2 * (n - 1));
    ll last = 0;
    while (q--) {
        int i;
        ll e;
        cin >> i >> e;
        i = (i + last) % (n - 1);
        W[i] = (e + last) % w;
        modify(op[i]), modify(cl[i]);
        cout << (last = t[1].ans) << '\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