Submission #604881

#	Time	Username	Problem	Language	Result	Execution time	Memory
604881		pakhomovee	Dynamic Diameter (CEOI19_diameter)	C++17	100 / 100	3885 ms	353872 KiB

diameter

#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 (stderr)

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 / 11
• Subtask 2: 13 / 13
• Subtask 3: 7 / 7
• Subtask 4: 18 / 18
• Subtask 5: 24 / 24
• Subtask 6: 27 / 27