oj.uz

Submission #592538

# Submission time Handle Problem Language Result Execution time Memory
592538 2022-07-09T09:46:55 Z alextodoran Dynamic Diameter (CEOI19_diameter) C++17
100 / 100
 2763 ms 103812 KB 
/**
 ____ ____ ____ ____ ____
||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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12156 KB Output is correct
2 Correct 7 ms 12116 KB Output is correct
3 Correct 8 ms 12108 KB Output is correct
4 Correct 6 ms 12116 KB Output is correct
5 Correct 8 ms 12100 KB Output is correct
6 Correct 6 ms 12112 KB Output is correct
7 Correct 8 ms 12116 KB Output is correct
8 Correct 6 ms 12116 KB Output is correct
9 Correct 9 ms 12116 KB Output is correct
10 Correct 8 ms 12164 KB Output is correct
11 Correct 7 ms 12116 KB Output is correct
12 Correct 7 ms 12116 KB Output is correct
13 Correct 6 ms 12176 KB Output is correct
14 Correct 6 ms 12204 KB Output is correct
15 Correct 7 ms 12224 KB Output is correct
16 Correct 8 ms 12116 KB Output is correct
17 Correct 7 ms 12244 KB Output is correct
18 Correct 7 ms 12160 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12156 KB Output is correct
2 Correct 7 ms 12116 KB Output is correct
3 Correct 8 ms 12108 KB Output is correct
4 Correct 6 ms 12116 KB Output is correct
5 Correct 8 ms 12100 KB Output is correct
6 Correct 6 ms 12112 KB Output is correct
7 Correct 8 ms 12116 KB Output is correct
8 Correct 6 ms 12116 KB Output is correct
9 Correct 9 ms 12116 KB Output is correct
10 Correct 8 ms 12164 KB Output is correct
11 Correct 7 ms 12116 KB Output is correct
12 Correct 7 ms 12116 KB Output is correct
13 Correct 6 ms 12176 KB Output is correct
14 Correct 6 ms 12204 KB Output is correct
15 Correct 7 ms 12224 KB Output is correct
16 Correct 8 ms 12116 KB Output is correct
17 Correct 7 ms 12244 KB Output is correct
18 Correct 7 ms 12160 KB Output is correct
19 Correct 23 ms 12752 KB Output is correct
20 Correct 24 ms 12816 KB Output is correct
21 Correct 27 ms 12852 KB Output is correct
22 Correct 22 ms 12756 KB Output is correct
23 Correct 44 ms 15244 KB Output is correct
24 Correct 48 ms 15388 KB Output is correct
25 Correct 49 ms 15620 KB Output is correct
26 Correct 38 ms 15040 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 12068 KB Output is correct
2 Correct 6 ms 12116 KB Output is correct
3 Correct 8 ms 12176 KB Output is correct
4 Correct 20 ms 12372 KB Output is correct
5 Correct 66 ms 13280 KB Output is correct
6 Correct 7 ms 12116 KB Output is correct
7 Correct 8 ms 12228 KB Output is correct
8 Correct 7 ms 12244 KB Output is correct
9 Correct 8 ms 12372 KB Output is correct
10 Correct 24 ms 12596 KB Output is correct
11 Correct 100 ms 13584 KB Output is correct
12 Correct 13 ms 14096 KB Output is correct
13 Correct 13 ms 14264 KB Output is correct
14 Correct 16 ms 14164 KB Output is correct
15 Correct 37 ms 14468 KB Output is correct
16 Correct 133 ms 15584 KB Output is correct
17 Correct 125 ms 52852 KB Output is correct
18 Correct 131 ms 52896 KB Output is correct
19 Correct 135 ms 52832 KB Output is correct
20 Correct 170 ms 53252 KB Output is correct
21 Correct 397 ms 54772 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 12756 KB Output is correct
2 Correct 35 ms 12944 KB Output is correct
3 Correct 119 ms 13528 KB Output is correct
4 Correct 228 ms 14204 KB Output is correct
5 Correct 32 ms 19964 KB Output is correct
6 Correct 59 ms 20012 KB Output is correct
7 Correct 204 ms 20664 KB Output is correct
8 Correct 378 ms 21568 KB Output is correct
9 Correct 137 ms 55248 KB Output is correct
10 Correct 179 ms 55384 KB Output is correct
11 Correct 456 ms 56172 KB Output is correct
12 Correct 747 ms 57020 KB Output is correct
13 Correct 278 ms 102216 KB Output is correct
14 Correct 326 ms 102296 KB Output is correct
15 Correct 692 ms 102944 KB Output is correct
16 Correct 998 ms 103812 KB Output is correct
17 Correct 2419 ms 103448 KB Output is correct

Subtask #5
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2074 ms 88108 KB Output is correct
2 Correct 2168 ms 89380 KB Output is correct
3 Correct 2280 ms 88504 KB Output is correct
4 Correct 2212 ms 90028 KB Output is correct
5 Correct 2237 ms 88136 KB Output is correct
6 Correct 2013 ms 79392 KB Output is correct
7 Correct 2725 ms 94720 KB Output is correct
8 Correct 2763 ms 94748 KB Output is correct
9 Correct 2697 ms 94700 KB Output is correct
10 Correct 2732 ms 94720 KB Output is correct
11 Correct 2673 ms 93808 KB Output is correct
12 Correct 2428 ms 80680 KB Output is correct
13 Correct 2057 ms 74180 KB Output is correct
14 Correct 2113 ms 74220 KB Output is correct
15 Correct 2053 ms 74208 KB Output is correct
16 Correct 2141 ms 74636 KB Output is correct
17 Correct 2127 ms 75620 KB Output is correct
18 Correct 1762 ms 71696 KB Output is correct
19 Correct 2109 ms 74240 KB Output is correct
20 Correct 2005 ms 74216 KB Output is correct
21 Correct 1988 ms 74388 KB Output is correct
22 Correct 2048 ms 74644 KB Output is correct
23 Correct 1973 ms 75736 KB Output is correct
24 Correct 1733 ms 71740 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12156 KB Output is correct
2 Correct 7 ms 12116 KB Output is correct
3 Correct 8 ms 12108 KB Output is correct
4 Correct 6 ms 12116 KB Output is correct
5 Correct 8 ms 12100 KB Output is correct
6 Correct 6 ms 12112 KB Output is correct
7 Correct 8 ms 12116 KB Output is correct
8 Correct 6 ms 12116 KB Output is correct
9 Correct 9 ms 12116 KB Output is correct
10 Correct 8 ms 12164 KB Output is correct
11 Correct 7 ms 12116 KB Output is correct
12 Correct 7 ms 12116 KB Output is correct
13 Correct 6 ms 12176 KB Output is correct
14 Correct 6 ms 12204 KB Output is correct
15 Correct 7 ms 12224 KB Output is correct
16 Correct 8 ms 12116 KB Output is correct
17 Correct 7 ms 12244 KB Output is correct
18 Correct 7 ms 12160 KB Output is correct
19 Correct 23 ms 12752 KB Output is correct
20 Correct 24 ms 12816 KB Output is correct
21 Correct 27 ms 12852 KB Output is correct
22 Correct 22 ms 12756 KB Output is correct
23 Correct 44 ms 15244 KB Output is correct
24 Correct 48 ms 15388 KB Output is correct
25 Correct 49 ms 15620 KB Output is correct
26 Correct 38 ms 15040 KB Output is correct
27 Correct 6 ms 12068 KB Output is correct
28 Correct 6 ms 12116 KB Output is correct
29 Correct 8 ms 12176 KB Output is correct
30 Correct 20 ms 12372 KB Output is correct
31 Correct 66 ms 13280 KB Output is correct
32 Correct 7 ms 12116 KB Output is correct
33 Correct 8 ms 12228 KB Output is correct
34 Correct 7 ms 12244 KB Output is correct
35 Correct 8 ms 12372 KB Output is correct
36 Correct 24 ms 12596 KB Output is correct
37 Correct 100 ms 13584 KB Output is correct
38 Correct 13 ms 14096 KB Output is correct
39 Correct 13 ms 14264 KB Output is correct
40 Correct 16 ms 14164 KB Output is correct
41 Correct 37 ms 14468 KB Output is correct
42 Correct 133 ms 15584 KB Output is correct
43 Correct 125 ms 52852 KB Output is correct
44 Correct 131 ms 52896 KB Output is correct
45 Correct 135 ms 52832 KB Output is correct
46 Correct 170 ms 53252 KB Output is correct
47 Correct 397 ms 54772 KB Output is correct
48 Correct 11 ms 12756 KB Output is correct
49 Correct 35 ms 12944 KB Output is correct
50 Correct 119 ms 13528 KB Output is correct
51 Correct 228 ms 14204 KB Output is correct
52 Correct 32 ms 19964 KB Output is correct
53 Correct 59 ms 20012 KB Output is correct
54 Correct 204 ms 20664 KB Output is correct
55 Correct 378 ms 21568 KB Output is correct
56 Correct 137 ms 55248 KB Output is correct
57 Correct 179 ms 55384 KB Output is correct
58 Correct 456 ms 56172 KB Output is correct
59 Correct 747 ms 57020 KB Output is correct
60 Correct 278 ms 102216 KB Output is correct
61 Correct 326 ms 102296 KB Output is correct
62 Correct 692 ms 102944 KB Output is correct
63 Correct 998 ms 103812 KB Output is correct
64 Correct 2419 ms 103448 KB Output is correct
65 Correct 2074 ms 88108 KB Output is correct
66 Correct 2168 ms 89380 KB Output is correct
67 Correct 2280 ms 88504 KB Output is correct
68 Correct 2212 ms 90028 KB Output is correct
69 Correct 2237 ms 88136 KB Output is correct
70 Correct 2013 ms 79392 KB Output is correct
71 Correct 2725 ms 94720 KB Output is correct
72 Correct 2763 ms 94748 KB Output is correct
73 Correct 2697 ms 94700 KB Output is correct
74 Correct 2732 ms 94720 KB Output is correct
75 Correct 2673 ms 93808 KB Output is correct
76 Correct 2428 ms 80680 KB Output is correct
77 Correct 2057 ms 74180 KB Output is correct
78 Correct 2113 ms 74220 KB Output is correct
79 Correct 2053 ms 74208 KB Output is correct
80 Correct 2141 ms 74636 KB Output is correct
81 Correct 2127 ms 75620 KB Output is correct
82 Correct 1762 ms 71696 KB Output is correct
83 Correct 2109 ms 74240 KB Output is correct
84 Correct 2005 ms 74216 KB Output is correct
85 Correct 1988 ms 74388 KB Output is correct
86 Correct 2048 ms 74644 KB Output is correct
87 Correct 1973 ms 75736 KB Output is correct
88 Correct 1733 ms 71740 KB Output is correct
89 Correct 1965 ms 88068 KB Output is correct
90 Correct 2356 ms 92292 KB Output is correct
91 Correct 2561 ms 94748 KB Output is correct
92 Correct 2719 ms 93124 KB Output is correct
93 Correct 2729 ms 90612 KB Output is correct
94 Correct 2320 ms 83120 KB Output is correct
95 Correct 1955 ms 71156 KB Output is correct
96 Correct 1886 ms 70164 KB Output is correct
97 Correct 1895 ms 70992 KB Output is correct
98 Correct 1897 ms 73480 KB Output is correct
99 Correct 1904 ms 71024 KB Output is correct
100 Correct 1932 ms 70932 KB Output is correct