Submission #1245514

#	Time	Username	Problem	Language	Result	Execution time	Memory
1245514		BlockOG	Dynamic Diameter (CEOI19_diameter)	C++20	0 / 100	29 ms	10308 KiB

diameter

#include <bits/stdc++.h>

// mrrrow meeow :3
// go play vivid/stasis now! it's free on steam

#define fo(i, a, b) for (auto i = (a); i < (b); i++)
#define of(i, a, b) for (auto i = (b); i-- > (a);)
#define f first
#define s second
#define pb push_back
#define pob pop_back
#define lb lower_bound
#define ub upper_bound
#define be(a) a.begin(), a.end()
using namespace std;

int ____init = [] {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    return 0;
}();

struct Node {
    long long sum00, sum10, sum01, sum11;

    Node() : sum00(0), sum10(0), sum01(0), sum11(0) {}
    Node(long long v) : sum00(max(v, 0ll)), sum10(max(v, 0ll)), sum01(max(v, 0ll)), sum11(v) {}

    Node combine(const Node &r) const {
        const Node &l = *this;
        Node res;

        res.sum00 = max(max(l.sum00, r.sum00), l.sum01 + r.sum10);
        res.sum10 = max(l.sum10, l.sum11 + r.sum10);
        res.sum01 = max(l.sum01 + r.sum11, r.sum01);
        res.sum11 = l.sum11 + r.sum11;

        return res;
    }
};

const int N = 1 << 5;
Node st[N * 2];
int l = 0;

void st_set(int i, long long v) {
    i += N;
    st[i] = Node(v);
    for (i /= 2; i > 0; i /= 2) st[i] = st[i * 2].combine(st[i * 2 + 1]);
}

vector<pair<int, pair<int, long long>>> adj[100000];
pair<int, int> eedges[99999];

void dfs(int i, int p = -1) {
    for (auto [j, c] : adj[i]) {
        if (j == p) continue;

        eedges[c.f].f = l;
        st[N + l++] = Node(c.s);

        dfs(j, i);

        eedges[c.f].s = l;
        st[N + l++] = Node(-c.s);
    }
}

int main() {
    int n, q;
    long long w;
    cin >> n >> q >> w;
    fo(i, 0, n - 1) {
        int a, b;
        long long c;
        cin >> a >> b >> c;
        a--, b--;
        adj[a].pb({b, {i, c}});
        adj[b].pb({a, {i, c}});
    }
    dfs(0);
    of(i, 1, N) st[i] = st[i * 2].combine(st[i * 2 + 1]);

    fo(i, 1, N * 2) cerr << st[i].sum00 << ',' << st[i].sum01 << ',' << st[i].sum10 << ',' << st[i].sum11 << ' ';
    cerr << endl;

    long long last = 0;
    while (q--) {
        long long d, e;
        cin >> d >> e;

        d = (d + last) % (n - 1);
        e = (e + last) % w;

        st_set(eedges[d].f, e);
        st_set(eedges[d].s, -e);

        cout << st[1].sum00 << endl;
        last = st[1].sum00;
    }
}

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