oj.uz

Submission #604881

# Submission time Handle Problem Language Result Execution time Memory
604881 2022-07-25T10:35:47 Z pakhomovee Dynamic Diameter (CEOI19_diameter) C++17
100 / 100
 3885 ms 353872 KB 
#include <iostream>
#include <vector>
#include <unordered_map>
#include <set>
#include <algorithm>

using namespace std;

const int maxn = 100000;

vector<pair<long long, int>> tree[maxn];
vector<long long> add[maxn];

void init(int c, int n) {
    tree[c].resize(n * 4);
    add[c].resize(n * 4);
}

void build(int i, int l, int r, vector<long long> &a, int c) {
    if (l + 1 == r) {
        tree[c][i] = { a[l], l };
        return;
    }
    int m = (l + r) / 2;
    build(i * 2 + 1, l, m, a, c);
    build(i * 2 + 2, m, r, a, c);
    tree[c][i] = max(tree[c][i * 2 + 1], tree[c][i * 2 + 2]);
}

inline void push(int i, int c) {
    add[c][i * 2 + 1] += add[c][i];
    add[c][i * 2 + 2] += add[c][i];
    add[c][i] = 0;
}

void upd(int i, int l, int r, int ql, int qr, long long x, int c) {
    if (qr <= l || r <= ql) {
        return;
    }
    if (ql <= l && r <= qr) {
        add[c][i] += x;
        return;
    }
    int m = (l + r) / 2;
    push(i, c);
    upd(i * 2 + 1, l, m, ql, qr, x, c);
    upd(i * 2 + 2, m, r, ql, qr, x, c);
    tree[c][i] = max(make_pair(tree[c][i * 2 + 1].first + add[c][i * 2 + 1], tree[c][i * 2 + 1].second), make_pair(tree[c][i * 2 + 2].first + add[c][i * 2 + 2], tree[c][i * 2 + 2].second));
}

pair<long long, int> getMax(int i, int l, int r, int ql, int qr, int c) {
    if (qr <= l || r <= ql) {
        return { 0ll, - 1};
    }
    if (ql <= l && r <= qr) {
        return make_pair(tree[c][i].first + add[c][i], tree[c][i].second);
    }
    int m = (l + r) / 2;
    push(i, c);
    auto ans = max(getMax(i * 2 + 1, l, m, ql, qr, c), getMax(i * 2 + 2, m, r, ql, qr, c));
    tree[c][i] = max(make_pair(tree[c][i * 2 + 1].first + add[c][i * 2 + 1], tree[c][i * 2 + 1].second), make_pair(tree[c][i * 2 + 2].first + add[c][i * 2 + 2], tree[c][i * 2 + 2].second));
    return ans;
}

int sz[maxn];
int p[maxn];
bool used[maxn];
vector<long long> ord;
int f[20][maxn];
int s[20][maxn];
int ords[maxn];
int stree[20][maxn];
vector<pair<int, int>> bord[maxn];
long long ans[1 << 18];
int tsz;
int sid;

void upd(int v, long long x) {
    v += 1 << 17;
    ans[v] = x;
    while (v > 1) {
        v >>= 1;
        ans[v] = max(ans[v * 2], ans[v * 2 + 1]);
    }
}

void dsz(int v, vector<vector<pair<int, long long>>> &g, int p) {
    sz[v] = 1;
    for (auto [u, w] : g[v]) {
        if (!used[u] && u != p) {
            dsz(u, g, v);
            sz[v] += sz[u];
        }
    }
}

int findc(int v, vector<vector<pair<int, long long>>> &g, int p) {
    for (auto [u, w] : g[v]) {
        if (!used[u] && sz[u] > tsz / 2 && u != p) {
            return findc(u, g, v);
        }
    }
    return v;
}

long long dfs(int v, vector<vector<pair<int, long long>>> &g, long long len, int p, int c, int h) {
    long long res = len;
    stree[h][v] = sid;
    f[h][v] = ord.size();
    ord.push_back(len);
    for (auto [u, w] : g[v]) {
        if (u != p && !used[u]) {
            res = max(res, dfs(u, g, len + w, v, c, h));
        }
    }
    s[h][v] = ord.size();
    ord.push_back(len);
    return res;
}

inline void recalc(int v) {
    if (bord[v].size() > 1) {
        auto [x, idx] = getMax(0, 0, ords[v], 0, ords[v], v);
        long long sum = x;
        int id = upper_bound(bord[v].begin(), bord[v].end(), make_pair(idx, -1)) - bord[v].begin() - 1;
        int bg = bord[v][id].first;
        int en = bord[v][id].second;
        sum += max(getMax(0, 0, ords[v], 0, bg, v).first, getMax(0, 0, ords[v], en + 1, ords[v], v).first);
        upd(v, sum);
    } else if (!bord[v].empty()) {
        auto [x, idx] = getMax(0, 0, ords[v], 0, ords[v], v);
        upd(v, x);
    }
}

int build(int v, vector<vector<pair<int, long long>>> &g, int h) {
    dsz(v, g, -1);
    tsz = sz[v];
    v = findc(v, g, -1);
    used[v] = true;
    f[h][v] = 0;
    ord.push_back(0);
    sid = 0;
    for (auto [u, w] : g[v]) {
        if (!used[u]) {
            int bg = ord.size();
            dfs(u, g, w, -1, v, h);
            int en = ord.size();
            bord[v].push_back({ bg, en });
            ++sid;
        }
    }
    s[h][v] = ord.size();
    ord.push_back(0);
    init(v, ord.size());
    build(0, 0, ord.size(), ord, v);
    ords[v] = ord.size();
    ord.clear();
    recalc(v);
    for (auto [u, w] : g[v]) {
        if (!used[u]) {
            p[build(u, g, h + 1)] = v;
        }
    }
    return v;
}

void upd(int c, int l, int r, long long x) {
    upd(0, 0, ords[c], l, r, x, c);
}

void upd(int v, int u, long long d) {
    int c = v;
    vector<int> pth;
    while (c != -1) {
        pth.push_back(c);
        c = p[c];
    }
    reverse(pth.begin(), pth.end());
    c = u;
    vector<int> pth1;
    while (c != -1) {
        pth1.push_back(c);
        c = p[c];
    }
    reverse(pth1.begin(), pth1.end());
    for (int i = 0; i < pth.size() && i < pth1.size() && pth[i] == pth1[i]; ++i) {
        int c = pth[i];
        if (f[i][u] < f[i][v]) swap(u, v);
        upd(c, f[i][u], s[i][u] + 1, d);
        recalc(c);
    }
}

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    long long n, q, w;
    cin >> n >> q >> w;
    fill(p, p + n, -1);
    vector<vector<pair<int, long long>>> g(n);
    vector<pair<long long, pair<int, int>>> edges;
    for (int i = 0; i < n - 1; ++i) {
        long long u, v, w;
        cin >> u >> v >> w;
        --u; --v;
        edges.push_back({ w, { u, v } });
        g[u].push_back({ v, w });
        g[v].push_back({ u, w });
    }
    build(0, g, 0);
    long long last = 0;
    while (q--) {
        long long d, e;
        cin >> d >> e;
        d = (d + last) % (n - 1);
        e = (e + last) % w;
        long long delta = e - edges[d].first;
        edges[d].first = e;
        upd(edges[d].second.first, edges[d].second.second, delta);
        last = ans[1];
        cout << last << '\n';
    }
}

Compilation message

diameter.cpp: In function 'void upd(int, int, long long int)':
diameter.cpp:187:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  187 |     for (int i = 0; i < pth.size() && i < pth1.size() && pth[i] == pth1[i]; ++i) {
      |                     ~~^~~~~~~~~~~~
diameter.cpp:187:41: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  187 |     for (int i = 0; i < pth.size() && i < pth1.size() && pth[i] == pth1[i]; ++i) {
      |                                       ~~^~~~~~~~~~~~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 7400 KB Output is correct
2 Correct 5 ms 7380 KB Output is correct
3 Correct 6 ms 7380 KB Output is correct
4 Correct 5 ms 7424 KB Output is correct
5 Correct 5 ms 7464 KB Output is correct
6 Correct 6 ms 7380 KB Output is correct
7 Correct 4 ms 7508 KB Output is correct
8 Correct 5 ms 7508 KB Output is correct
9 Correct 4 ms 7508 KB Output is correct
10 Correct 6 ms 7568 KB Output is correct
11 Correct 5 ms 7508 KB Output is correct
12 Correct 4 ms 7508 KB Output is correct
13 Correct 5 ms 7508 KB Output is correct
14 Correct 6 ms 7508 KB Output is correct
15 Correct 4 ms 7508 KB Output is correct
16 Correct 6 ms 7628 KB Output is correct
17 Correct 4 ms 7636 KB Output is correct
18 Correct 5 ms 7636 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 7400 KB Output is correct
2 Correct 5 ms 7380 KB Output is correct
3 Correct 6 ms 7380 KB Output is correct
4 Correct 5 ms 7424 KB Output is correct
5 Correct 5 ms 7464 KB Output is correct
6 Correct 6 ms 7380 KB Output is correct
7 Correct 4 ms 7508 KB Output is correct
8 Correct 5 ms 7508 KB Output is correct
9 Correct 4 ms 7508 KB Output is correct
10 Correct 6 ms 7568 KB Output is correct
11 Correct 5 ms 7508 KB Output is correct
12 Correct 4 ms 7508 KB Output is correct
13 Correct 5 ms 7508 KB Output is correct
14 Correct 6 ms 7508 KB Output is correct
15 Correct 4 ms 7508 KB Output is correct
16 Correct 6 ms 7628 KB Output is correct
17 Correct 4 ms 7636 KB Output is correct
18 Correct 5 ms 7636 KB Output is correct
19 Correct 31 ms 8928 KB Output is correct
20 Correct 24 ms 9012 KB Output is correct
21 Correct 42 ms 9328 KB Output is correct
22 Correct 38 ms 9652 KB Output is correct
23 Correct 39 ms 15444 KB Output is correct
24 Correct 57 ms 17664 KB Output is correct
25 Correct 56 ms 18620 KB Output is correct
26 Correct 90 ms 20368 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7380 KB Output is correct
2 Correct 4 ms 7380 KB Output is correct
3 Correct 5 ms 7380 KB Output is correct
4 Correct 20 ms 7540 KB Output is correct
5 Correct 68 ms 7788 KB Output is correct
6 Correct 4 ms 7380 KB Output is correct
7 Correct 6 ms 7636 KB Output is correct
8 Correct 7 ms 7636 KB Output is correct
9 Correct 7 ms 7636 KB Output is correct
10 Correct 30 ms 7784 KB Output is correct
11 Correct 109 ms 8148 KB Output is correct
12 Correct 9 ms 10196 KB Output is correct
13 Correct 8 ms 10260 KB Output is correct
14 Correct 11 ms 10272 KB Output is correct
15 Correct 34 ms 10316 KB Output is correct
16 Correct 129 ms 10720 KB Output is correct
17 Correct 84 ms 62580 KB Output is correct
18 Correct 102 ms 62472 KB Output is correct
19 Correct 115 ms 62544 KB Output is correct
20 Correct 152 ms 62628 KB Output is correct
21 Correct 373 ms 63220 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 9300 KB Output is correct
2 Correct 35 ms 9360 KB Output is correct
3 Correct 171 ms 9484 KB Output is correct
4 Correct 388 ms 9988 KB Output is correct
5 Correct 46 ms 32104 KB Output is correct
6 Correct 101 ms 32200 KB Output is correct
7 Correct 364 ms 32452 KB Output is correct
8 Correct 747 ms 32732 KB Output is correct
9 Correct 179 ms 153620 KB Output is correct
10 Correct 311 ms 153740 KB Output is correct
11 Correct 697 ms 153996 KB Output is correct
12 Correct 1242 ms 154240 KB Output is correct
13 Correct 362 ms 319484 KB Output is correct
14 Correct 461 ms 319496 KB Output is correct
15 Correct 973 ms 319796 KB Output is correct
16 Correct 1769 ms 320028 KB Output is correct
17 Correct 2594 ms 320080 KB Output is correct

Subtask #5
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2183 ms 248412 KB Output is correct
2 Correct 2522 ms 256628 KB Output is correct
3 Correct 2295 ms 253312 KB Output is correct
4 Correct 2930 ms 257120 KB Output is correct
5 Correct 2412 ms 242260 KB Output is correct
6 Correct 2297 ms 172616 KB Output is correct
7 Correct 3427 ms 321748 KB Output is correct
8 Correct 3489 ms 325664 KB Output is correct
9 Correct 3002 ms 325936 KB Output is correct
10 Correct 2880 ms 324512 KB Output is correct
11 Correct 2924 ms 307964 KB Output is correct
12 Correct 2517 ms 212696 KB Output is correct
13 Correct 3184 ms 353736 KB Output is correct
14 Correct 3310 ms 353604 KB Output is correct
15 Correct 3876 ms 353576 KB Output is correct
16 Correct 3845 ms 352008 KB Output is correct
17 Correct 3212 ms 332172 KB Output is correct
18 Correct 2901 ms 222032 KB Output is correct
19 Correct 3220 ms 353872 KB Output is correct
20 Correct 3293 ms 353572 KB Output is correct
21 Correct 3846 ms 353576 KB Output is correct
22 Correct 3885 ms 352060 KB Output is correct
23 Correct 3129 ms 331960 KB Output is correct
24 Correct 2992 ms 222100 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 7400 KB Output is correct
2 Correct 5 ms 7380 KB Output is correct
3 Correct 6 ms 7380 KB Output is correct
4 Correct 5 ms 7424 KB Output is correct
5 Correct 5 ms 7464 KB Output is correct
6 Correct 6 ms 7380 KB Output is correct
7 Correct 4 ms 7508 KB Output is correct
8 Correct 5 ms 7508 KB Output is correct
9 Correct 4 ms 7508 KB Output is correct
10 Correct 6 ms 7568 KB Output is correct
11 Correct 5 ms 7508 KB Output is correct
12 Correct 4 ms 7508 KB Output is correct
13 Correct 5 ms 7508 KB Output is correct
14 Correct 6 ms 7508 KB Output is correct
15 Correct 4 ms 7508 KB Output is correct
16 Correct 6 ms 7628 KB Output is correct
17 Correct 4 ms 7636 KB Output is correct
18 Correct 5 ms 7636 KB Output is correct
19 Correct 31 ms 8928 KB Output is correct
20 Correct 24 ms 9012 KB Output is correct
21 Correct 42 ms 9328 KB Output is correct
22 Correct 38 ms 9652 KB Output is correct
23 Correct 39 ms 15444 KB Output is correct
24 Correct 57 ms 17664 KB Output is correct
25 Correct 56 ms 18620 KB Output is correct
26 Correct 90 ms 20368 KB Output is correct
27 Correct 4 ms 7380 KB Output is correct
28 Correct 4 ms 7380 KB Output is correct
29 Correct 5 ms 7380 KB Output is correct
30 Correct 20 ms 7540 KB Output is correct
31 Correct 68 ms 7788 KB Output is correct
32 Correct 4 ms 7380 KB Output is correct
33 Correct 6 ms 7636 KB Output is correct
34 Correct 7 ms 7636 KB Output is correct
35 Correct 7 ms 7636 KB Output is correct
36 Correct 30 ms 7784 KB Output is correct
37 Correct 109 ms 8148 KB Output is correct
38 Correct 9 ms 10196 KB Output is correct
39 Correct 8 ms 10260 KB Output is correct
40 Correct 11 ms 10272 KB Output is correct
41 Correct 34 ms 10316 KB Output is correct
42 Correct 129 ms 10720 KB Output is correct
43 Correct 84 ms 62580 KB Output is correct
44 Correct 102 ms 62472 KB Output is correct
45 Correct 115 ms 62544 KB Output is correct
46 Correct 152 ms 62628 KB Output is correct
47 Correct 373 ms 63220 KB Output is correct
48 Correct 9 ms 9300 KB Output is correct
49 Correct 35 ms 9360 KB Output is correct
50 Correct 171 ms 9484 KB Output is correct
51 Correct 388 ms 9988 KB Output is correct
52 Correct 46 ms 32104 KB Output is correct
53 Correct 101 ms 32200 KB Output is correct
54 Correct 364 ms 32452 KB Output is correct
55 Correct 747 ms 32732 KB Output is correct
56 Correct 179 ms 153620 KB Output is correct
57 Correct 311 ms 153740 KB Output is correct
58 Correct 697 ms 153996 KB Output is correct
59 Correct 1242 ms 154240 KB Output is correct
60 Correct 362 ms 319484 KB Output is correct
61 Correct 461 ms 319496 KB Output is correct
62 Correct 973 ms 319796 KB Output is correct
63 Correct 1769 ms 320028 KB Output is correct
64 Correct 2594 ms 320080 KB Output is correct
65 Correct 2183 ms 248412 KB Output is correct
66 Correct 2522 ms 256628 KB Output is correct
67 Correct 2295 ms 253312 KB Output is correct
68 Correct 2930 ms 257120 KB Output is correct
69 Correct 2412 ms 242260 KB Output is correct
70 Correct 2297 ms 172616 KB Output is correct
71 Correct 3427 ms 321748 KB Output is correct
72 Correct 3489 ms 325664 KB Output is correct
73 Correct 3002 ms 325936 KB Output is correct
74 Correct 2880 ms 324512 KB Output is correct
75 Correct 2924 ms 307964 KB Output is correct
76 Correct 2517 ms 212696 KB Output is correct
77 Correct 3184 ms 353736 KB Output is correct
78 Correct 3310 ms 353604 KB Output is correct
79 Correct 3876 ms 353576 KB Output is correct
80 Correct 3845 ms 352008 KB Output is correct
81 Correct 3212 ms 332172 KB Output is correct
82 Correct 2901 ms 222032 KB Output is correct
83 Correct 3220 ms 353872 KB Output is correct
84 Correct 3293 ms 353572 KB Output is correct
85 Correct 3846 ms 353576 KB Output is correct
86 Correct 3885 ms 352060 KB Output is correct
87 Correct 3129 ms 331960 KB Output is correct
88 Correct 2992 ms 222100 KB Output is correct
89 Correct 2072 ms 256156 KB Output is correct
90 Correct 2490 ms 284156 KB Output is correct
91 Correct 3169 ms 316564 KB Output is correct
92 Correct 3406 ms 325076 KB Output is correct
93 Correct 3411 ms 336336 KB Output is correct
94 Correct 3397 ms 341828 KB Output is correct
95 Correct 3453 ms 350548 KB Output is correct
96 Correct 3557 ms 350480 KB Output is correct
97 Correct 3592 ms 350564 KB Output is correct
98 Correct 3342 ms 352748 KB Output is correct
99 Correct 3415 ms 350548 KB Output is correct
100 Correct 3456 ms 350544 KB Output is correct