Submission #1246379

#	Time	Username	Problem	Language	Result	Execution time	Memory
1246379		KindaGoodGames	Dynamic Diameter (CEOI19_diameter)	C++20	31 / 100	559 ms	35256 KiB

diameter

// #pragma GCC optimize("O3, unroll-loops,Ofast")
#include<bits/stdc++.h>

using namespace std;
#define int long long
#define pii pair<int,int>
#define tiii tuple<int,int,int>

int INF = numeric_limits<int>::max() / 4;

struct Value {
    int ma = -INF;
    int ma2 = -INF;

    Value() {}
    Value(int a) {
        ma = a;
    }
    Value(int a, int b) {
        ma = a;
        ma2 = b;
    }

    void add(int v) {
        ma += v;
        ma2 += v;
    }
};

Value comb(Value a, Value b) {
    vector<int> r = { a.ma,a.ma2,b.ma,b.ma2 };
    sort(r.rbegin(), r.rend());
    return Value(r[0], r[1]);
}
struct SegmentTree {
    vector<Value> S;
    vector<int> lazy;
    int len = 1;

    SegmentTree(int n) {
        while (len < n) {
            len <<= 1;
        }

        S.resize(2 * len);
        lazy.resize(2 * len);
    }

    void upd(int i, int v) {
        i += len;

        S[i] = Value(v);

        for (i /= 2; i > 0; i /= 2) {
            S[i] = comb(S[i * 2], S[i * 2 + 1]);
        }
    }

    void apply1(int i, int v) {
        S[i].add(v);
        lazy[i] += v;
    }

    void push(int i) {
        apply1(i * 2 + 1, lazy[i]);
        apply1(i * 2, lazy[i]);

        lazy[i] = 0;
    }


    Value query(int ql, int qr, int l = 0, int r = -2, int i = 1) {
        if (r == -2) r = len;

        if (ql <= l && r <= qr) {
            return S[i];
        }
        if (r <= ql || qr <= l) {
            return Value();
        }

        int mid = (l + r) / 2;

        push(i);
        Value a = query(ql, qr, l, mid, i * 2);
        Value b = query(ql, qr, mid, r, i * 2 + 1);
        return comb(a, b);
    }


    void apply(int ql, int qr, int v, int l = 0, int r = -2, int i = 1) {
        if (r == -2) r = len;

        if (ql <= l && r <= qr) {
            apply1(i, v);
            return;
        }
        if (r <= ql || qr <= l) return;

        int mid = (l + r) / 2;

        push(i);
        apply(ql, qr, v, l, mid, i * 2); apply(ql, qr, v, mid, r, i * 2 + 1);
        S[i] = comb(S[i * 2], S[i * 2 + 1]);
    }
};

vector<int> val, cost, ftree;
vector<int> par, sz, depth;
vector<int> start, stop;
vector<vector<pii>> adj;
int timer = 0;

void DFS(int v, int p, int d = 0, int len = 0, int f = -1) {
    start[v] = timer++;

    depth[v] = d;
    sz[v] = 1;
    par[v] = p;
    ftree[v] = f;

    int h = -1;
    int s = -1;
    for (auto u : adj[v]) {
        if (u.first == p) continue;
        val[u.first] = len + u.second;
        cost[u.first] = u.second;

        int nf = f;
        if (f == -1) {
            nf = u.first;
        }
        DFS(u.first, v, d + 1, len + u.second, nf);

        sz[v] += sz[u.first];
    }

    stop[v] = timer;
}

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n, q, w;
    cin >> n >> q >> w;

    vector<tiii> edges(n - 1);
    adj.resize(n);
    val.resize(n);
    par = sz = val = depth = cost = start = stop = ftree = vector<int>(n, -1);

    for (int i = 0; i < n - 1; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        a--; b--;
        edges[i] = { a,b,c };
        adj[a].push_back({ b,c });
        adj[b].push_back({ a,c });
    }

    DFS(0, 0);
    val[0] = 0;
    cost[0] = 0;

    SegmentTree seg(n);

    for (int i = 0; i < n; i++) {
        seg.upd(start[i], val[i]);
    }

    int last = 0;
    SegmentTree seg2(adj[0].size());

    map<int, int> indch;
    for (int i = 0; i < adj[0].size(); i++) {
        auto u = adj[0][i];
        Value v = seg.query(start[u.first], stop[u.first]);
        seg2.upd(i, v.ma);
        indch[u.first] = i;
    }
    while (q--) {
        int d, e;
        cin >> d >> e;

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

        int a, b, c;
        tie(a, b, c) = edges[edge];
        if (depth[a] < depth[b]) swap(a, b);
        int diff = weight - c;

        seg.apply(start[a], stop[a], diff);

        edges[edge] = { a,b,weight };
        cost[a] = weight;

        auto u = ftree[a];
        int ans = seg.query(start[u], stop[u]).ma; 
            seg2.upd(indch[u], ans);

        int ma = 0;
        for (int i = 0; i < 1; i++) {
            Value res = Value();

            res = seg2.query(0, adj[0].size());
            int rem = seg.query(start[i], start[i] + 1).ma;

            int pv = max((res.ma + res.ma2) - (2 * rem), res.ma - rem);
            if (pv > ma) {
                ma = max({ ma, pv });
            }
        }

        cout << ma << "\n";
        last = ma;
    }
}

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