Submission #592538

#	Time	Username	Problem	Language	Result	Execution time	Memory
592538		alextodoran	Dynamic Diameter (CEOI19_diameter)	C++17	100 / 100	2763 ms	103812 KiB

diameter

/**
 ____ ____ ____ ____ ____
||a |||t |||o |||d |||o ||
||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|

**/

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N_MAX = 100000;
const int D_MAX = 20;

struct Edge {
    int to;
    ll len;
};

int N, Q; ll W;
tuple <int, int, ll> tree[N_MAX + 2];
vector <Edge> edges[N_MAX + 2];
Edge parent[N_MAX + 2];

struct SegInfo {
    ll maxDepth;
    ll lazyAdd;
    void add (const ll &val) {
        maxDepth += val;
        lazyAdd += val;
    }
};

multiset <ll> diameters;

int centroidDepth[N_MAX + 2];
int centroidParent[N_MAX + 2];
int leftLeafID[D_MAX + 2][N_MAX + 2];
int rightLeafID[D_MAX + 2][N_MAX + 2];
vector <int> sons[N_MAX + 2];
vector <SegInfo> segTree[N_MAX + 2];
int leafCount[N_MAX + 2];
multiset <ll> maxDepths[N_MAX + 2];

int centroid, depth;
bool seen[N_MAX + 2];
int subtreeSize[N_MAX + 2];
ll dist[N_MAX + 2];
int nodes[N_MAX + 2], cntNodes;
int leaves[N_MAX + 2], cntLeaves;

void build (int node, int l, int r) {
    if (l == r) {
        segTree[centroid][node] = SegInfo{dist[leaves[l]], 0};
        return;
    }
    int mid = (l + r) / 2;
    int lSon = node * 2, rSon = node * 2 + 1;
    build(lSon, l, mid);
    build(rSon, mid + 1, r);
    segTree[centroid][node].maxDepth =
        max(segTree[centroid][lSon].maxDepth, segTree[centroid][rSon].maxDepth);
}
void build () {
    segTree[centroid].resize(cntLeaves * 4 + 2);
    build(1, 1, leafCount[centroid]);
}

void split (int node) {
    int lSon = node * 2, rSon = node * 2 + 1;
    segTree[centroid][lSon].add(segTree[centroid][node].lazyAdd);
    segTree[centroid][rSon].add(segTree[centroid][node].lazyAdd);
    segTree[centroid][node].lazyAdd = 0;
}

void update (int node, int l, int r, int ul, int ur, ll uval) {
    if (ul <= l && r <= ur) {
        segTree[centroid][node].add(uval);
        return;
    }
    split(node);
    int mid = (l + r) / 2;
    int lSon = node * 2, rSon = node * 2 + 1;
    if (ul <= mid) {
        update(lSon, l, mid, ul, ur, uval);
    }
    if (mid + 1 <= ur) {
        update(rSon, mid + 1, r, ul, ur, uval);
    }
    segTree[centroid][node].maxDepth =
        max(segTree[centroid][lSon].maxDepth, segTree[centroid][rSon].maxDepth);
}
void update (int ul, int ur, ll uval) {
    update(1, 1, leafCount[centroid], ul, ur, uval);
}

ll query (int node, int l, int r, int ql, int qr) {
    if (ql <= l && r <= qr) {
        return segTree[centroid][node].maxDepth;
    }
    split(node);
    int mid = (l + r) / 2;
    int lSon = node * 2, rSon = node * 2 + 1;
    if (ql <= mid && mid + 1 <= qr) {
        return max(query(lSon, l, mid, ql, qr), query(rSon, mid + 1, r, ql, qr));
    } else if (ql <= mid) {
        return query(lSon, l, mid, ql, qr);
    } else {
        return query(rSon, mid + 1, r, ql, qr);
    }
}
ll query (int ql, int qr) {
    return query(1, 1, leafCount[centroid], ql, qr);
}

void dfs (int u) {
    nodes[++cntNodes] = u;
    seen[u] = true;
    subtreeSize[u] = 1;
    leftLeafID[depth][u] = INT_MAX;
    rightLeafID[depth][u] = INT_MIN;
    for (Edge e : edges[u]) {
        if (seen[e.to] == false && centroidDepth[e.to] == 0) {
            parent[e.to] = Edge{u, e.len};
            dist[e.to] = dist[u] + e.len;
            dfs(e.to);
            subtreeSize[u] += subtreeSize[e.to];
            leftLeafID[depth][u] = min(leftLeafID[depth][u], leftLeafID[depth][e.to]);
            rightLeafID[depth][u] = max(rightLeafID[depth][u], rightLeafID[depth][e.to]);
        }
    }
    if (leftLeafID[depth][u] > rightLeafID[depth][u]) {
        leaves[++cntLeaves] = u;
        leftLeafID[depth][u] = rightLeafID[depth][u] = cntLeaves;
    }
}
void init (int u) {
    parent[u] = Edge{u, 0};
    dist[u] = 0;
    for (int i = 1; i <= cntNodes; i++) {
        seen[nodes[i]] = false;
    }
    cntNodes = 0;
    cntLeaves = 0;
}

void findCentroid (int root) {
    init(root);
    dfs(root);
    for (int i = 1; i <= cntNodes; i++) {
        int u = nodes[i];
        bool ok = true;
        for (Edge e : edges[u]) {
            if (e.to != parent[u].to && centroidDepth[e.to] == false) {
                if (subtreeSize[e.to] > cntNodes / 2) {
                    ok = false;
                    break;
                }
            }
        }
        if (cntNodes - subtreeSize[u] > cntNodes / 2) {
            ok = false;
        }
        if (ok == true) {
            centroid = u;
            break;
        }
    }
    init(centroid);
    dfs(centroid);
}

ll diameter (int centroid) {
    multiset <ll> :: iterator it = maxDepths[centroid].end();
    ll len = 0;
    if (it != maxDepths[centroid].begin()) {
        it--; len += *it;
        if (it != maxDepths[centroid].begin()) {
            it--; len += *it;
        }
    }
    return len;
}

void centroidDecomposition (int root, int cparent = 0) {
    depth++;
    findCentroid(root);
    centroidDepth[centroid] = depth;
    centroidParent[centroid] = cparent;
    leafCount[centroid] = cntLeaves;
    build();
    for (Edge e : edges[centroid]) {
        int u = e.to;
        if (centroidDepth[u] == 0) {
            sons[centroid].push_back(u);
            maxDepths[centroid].insert(query(leftLeafID[depth][u], rightLeafID[depth][u]));
        }
    }
    diameters.insert(diameter(centroid));
    int thisCentroid = centroid;
    for (int u : sons[centroid]) {
        centroidDecomposition(u, thisCentroid);
    }
    depth--;
}

void changeLen (int u, int v, ll lenDelta) {
    centroid = (centroidDepth[u] < centroidDepth[v] ? u : v);
    while (centroid != 0) {
        int depth = centroidDepth[centroid];
        int lID = max(leftLeafID[depth][u], leftLeafID[depth][v]);
        int rID = min(rightLeafID[depth][u], rightLeafID[depth][v]);
        int son; {
            int l = 0, r = (int) sons[centroid].size() - 1;
            while (l < r) {
                int mid = (l + r + 1) / 2;
                if (leftLeafID[depth][sons[centroid][mid]] <= lID) {
                    l = mid;
                } else {
                    r = mid - 1;
                }
            }
            son = sons[centroid][l];
        }
        diameters.erase(diameters.find(diameter(centroid)));
        maxDepths[centroid].erase(maxDepths[centroid].find(
            query(leftLeafID[depth][son], rightLeafID[depth][son])));
        update(lID, rID, lenDelta);
        maxDepths[centroid].insert(query(leftLeafID[depth][son], rightLeafID[depth][son]));
        diameters.insert(diameter(centroid));
        centroid = centroidParent[centroid];
    }
}

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

    cin >> N >> Q >> W;
    for (int i = 1; i <= N - 1; i++) {
        int u, v; ll len;
        cin >> u >> v >> len;
        edges[u].push_back(Edge{v, len});
        edges[v].push_back(Edge{u, len});
        tree[i] = make_tuple(u, v, len);
    }

    centroidDecomposition(1);

    ll last = 0;
    while (Q--) {
        int i; ll len;
        cin >> i >> len;
        i = (i + last) % (N - 1) + 1;
        len = (len + last) % W;
        int u, v; ll old; tie(u, v, old) = tree[i];
        changeLen(u, v, len - old);
        tree[i] = make_tuple(u, v, len);
        last = *diameters.rbegin();
        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