Submission #835299

#	Time	Username	Problem	Language	Result	Execution time	Memory
835299		Josia	Dynamic Diameter (CEOI19_diameter)	C++17	100 / 100	4385 ms	285256 KiB

diameter

#include <bits/stdc++.h>

using namespace std;

#define int int64_t


struct seg {
    int n;
    vector<int> tree;
    vector<int> lazy;

    void push(int v) {
        tree[v*2] += lazy[v];
        tree[v*2+1] += lazy[v];

        lazy[v*2] += lazy[v];
        lazy[v*2+1] += lazy[v];

        lazy[v] = 0;
    }

    int query(int v, int rl, int rr, int ql, int qr) {
        if (ql > qr) {
            return 0;
        }
        if (ql == rl && qr == rr) return tree[v];

        push(v);

        int rm = (rl + rr) / 2;

        return max(query(v*2, rl, rm, ql, min(rm, qr)), query(v*2+1, rm+1, rr, max(rm+1, ql), qr));
    }

    void update(int v, int rl, int rr, int ql, int qr, int x) {
        if (ql > qr) {
            return;
        }
        if (ql == rl && qr == rr) {
            tree[v] += x;
            lazy[v] += x;
            return;
        }

        push(v);

        int rm = (rl + rr) / 2;

        update(v*2, rl, rm, ql, min(rm, qr), x);
        update(v*2+1, rm+1, rr, max(rm+1, ql), qr, x);

        tree[v] = max(tree[v*2], tree[v*2+1]);
    }

    void init(int _n, vector<int> a) {
        n = _n;
        tree.assign(n*4, 0);
        lazy.assign(n*4, 0);

        for (int i = 0; i<n; i++) {
            update(1, 0, n-1, i, i, a[i]);
        }
    }
};


vector<vector<int>> graph;
unordered_map<int, int> weight;

array<array<int, 100005>, 20> parent;
array<array<int, 100005>, 20> Size;
array<array<int, 100005>, 20> whichSubtree;
array<array<pair<int, int>, 100005>, 20> prepost;


vector<int> centroidLevel;

struct tree {
    int level;
    int currCol = 0;

    seg segtree;

    vector<int> order;
    vector<int> verticies;
    vector<int> children;
    int dfs(int v, int p, int forbidden, int d) {
        verticies.push_back(v);
        prepost[level][v].first = order.size();
        order.push_back(d);
        parent[level][v] = p;

        if (p!=-1) whichSubtree[level][v] = currCol;

        int s = 1;

        for (int i: graph[v]) {
            if (i == p || centroidLevel[i]!=-1) continue;
            s += dfs(i, v, forbidden, d+weight[i+v*100005]);
            if (p==-1) {
                children.push_back(i);
                currCol++;
            }
        }
        Size[level][v] = s;
        prepost[level][v].second = order.size()-1;
        return s;
    }


    bool isCentroid(int v, int p, int forbidden) {
        int s = 1;
        for (int i: graph[v]) {
            if (i == p || centroidLevel[i]!=-1) continue;
            if (Size[level][i] > (int)verticies.size()/2) return 0;
            s += Size[level][i];
        }
        return (int)verticies.size()-s <= (int)verticies.size()/2;
    }

    int findCentroid(int v, int p, int forbidden) {
        if (isCentroid(v, p, forbidden)) return v;

        int biggest=0;
        int indBiggest=-1;
        for (int i: graph[v]) {
            if (i == p || centroidLevel[i]!=-1) continue;
            if (Size[level][i] > biggest) {
                biggest = Size[level][i];
                indBiggest = i;
            }
        }

        assert(indBiggest!=-1);
        return findCentroid(indBiggest, v, forbidden);
    }



    bool isParent(int p, int v) {
        return (parent[level][v] == p);
    }


    set<pair<int, int>> bestInChild;


    void updateEdge(int u, int v, int x) {
        // if (verticies.count(u)==0 || verticies.count(v)==0) return;
        if (!isParent(u, v)) swap(u, v);

        int child = whichSubtree[level][v];

        pair<int, int> rangeChild = prepost[level][children[child]];
        bestInChild.erase({segtree.query(1, 0, segtree.n-1, rangeChild.first, rangeChild.second), child});

        pair<int, int> rangeUpdate = prepost[level][v];
        segtree.update(1, 0, segtree.n-1, rangeUpdate.first, rangeUpdate.second, x);

        bestInChild.insert({segtree.query(1, 0, segtree.n-1, rangeChild.first, rangeChild.second), child});
    }

    int getDiam() {
        if (bestInChild.empty()) return 0;
        if (bestInChild.size()==1) return (*bestInChild.rbegin()).first;
        return (*bestInChild.rbegin()).first + (*next(bestInChild.rbegin())).first;
    }

    pair<int, vector<int>> init(int v, int _level, int forbidden) {
        level = _level;
        currCol = 0;
        order.clear();

        dfs(v, -1, forbidden, 0);

        int centroid = findCentroid(v, -1, forbidden);

        currCol = 0;
        order.clear();
        verticies.clear();
        children.clear();
        dfs(centroid, -1, forbidden, 0);

        // for (int i: order) cerr << i << " ";
        // cerr << "\n";

        segtree.init(order.size(), order);

        for (int i = 0; i<(int)children.size(); i++) {
            auto range = prepost[level][children[i]];
            bestInChild.insert({segtree.query(1, 0, segtree.n-1, range.first, range.second), i});
        }

        return {centroid, children};
    }
};




int N, Q, W;




vector<tree> trees;
vector<vector<int>> inTrees;

set<pair<int, int>> allDiams;   // len, treeInd

void makeTrees() {
    queue<array<int, 3>> q;     // centroid, level, parent;

    q.push({0, 0, -1});

    while (q.size()) {
        tree x;
        auto newComps = x.init(q.front()[0], q.front()[1], q.front()[2]);

        centroidLevel[newComps.first] = q.front()[1];

        for (int i: newComps.second) {
            q.push({i, q.front()[1]+1, newComps.first});
        }
        q.pop();

        for (int i: x.verticies) inTrees[i].push_back(trees.size());
        allDiams.insert({x.getDiam(), trees.size()});

        trees.push_back(x);
    }
}

void updateEdge(int u, int v, int x) {

    int p1 = 0;
    int p2 = 0;

    while (p1<(int)inTrees[u].size() && p2<(int)inTrees[v].size()) {
        if (inTrees[u][p1] == inTrees[v][p2]) {
            allDiams.erase({trees[inTrees[u][p1]].getDiam(), inTrees[u][p1]});
            trees[inTrees[u][p1]].updateEdge(u, v, x);
            allDiams.insert({trees[inTrees[u][p1]].getDiam(), inTrees[u][p1]});
            p1++;
            p2++;
            continue;
        }
        if (inTrees[u][p1] < inTrees[v][p2]) {
            p1++;
            continue;
        }
        p2++;
    }

}


int queryBest() {
    return (*allDiams.rbegin()).first;
}


signed main() {
    cin.tie(0);
    ios_base::sync_with_stdio(0);

    cin >> N >> Q >> W;

    graph.resize(N);
    inTrees.resize(N);
    centroidLevel.assign(N, -1);

    vector<array<int,3>> edges(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};
        graph[a].push_back(b);
        graph[b].push_back(a);

        weight[a+b*100005] = c;
        weight[b+a*100005] = c;
    }

    makeTrees();

    // for (auto i: edges) {
    //     updateEdge(i[0], i[1], i[2]);
    // }

    int last = 0;
    for (int i = 0; i<Q; i++) {
        int _d, _e; cin >> _d >> _e;

        int d = (_d+last)%(N-1);
        int e = (_e+last)%(W);

        int diff = e-edges[d][2];

        updateEdge(edges[d][0], edges[d][1], diff);

        edges[d][2] = e;

        last = queryBest();
        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