Submission #1073999

#	Time	Username	Problem	Language	Result	Execution time	Memory
1073999		_callmelucian	Dynamic Diameter (CEOI19_diameter)	C++14	42 / 100	5092 ms	156276 KiB

diameter

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pl;
typedef pair<int,int> pii;
typedef tuple<int,int,ll> tt;

#define all(a) a.begin(), a.end()
#define filter(a) a.erase(unique(all(a)), a.end())

const int mn = 1e5 + 5;
const int LOG = 19;

struct IT {
    vector<pl> tr;

    IT() {}
    IT (int sz) : tr(4 * sz) {}

    void update (int pos, ll val, int k, int l, int r) {
        if (pos < l || r < pos) return;
        if (l == r) {
            tr[k] = {val, l};
            return;
        }
        int mid = (l + r) >> 1;
        update(pos, val, 2 * k, l, mid);
        update(pos, val, 2 * k + 1, mid + 1, r);
        tr[k] = max(tr[2 * k], tr[2 * k + 1]);
    }

    pl query (int a, int b, int k, int l, int r) {
        if (b < l || r < a) return {0, 0};
        if (a <= l && r <= b) return tr[k];
        int mid = (l + r) >> 1;
        return max(query(a, b, 2 * k, l, mid), query(a, b, 2 * k + 1, mid + 1, r));
    }
} tree[mn];

struct lazyIT {
    vector<ll> tr, lazy;

    lazyIT() {}
    lazyIT (int sz) : tr(4 * sz), lazy(4 * sz) {}

    ll get (int k) { return tr[k] + lazy[k]; }

    void pushDown (int k) {
        lazy[2 * k] += lazy[k], lazy[2 * k + 1] += lazy[k], lazy[k] = 0;
        tr[k] = max(get(2 * k), get(2 * k + 1));
    }

    void update (int a, int b, ll inc, int k, int l, int r) {
        if (b < l || r < a) return;
        if (a <= l && r <= b) {
            lazy[k] += inc;
            return;
        }
        pushDown(k);
        int mid = (l + r) >> 1;
        update(a, b, inc, 2 * k, l, mid);
        update(a, b, inc, 2 * k + 1, mid + 1, r);
        tr[k] = max(get(2 * k), get(2 * k + 1));
    }

    ll query (int a, int b, int k, int l, int r) {
        if (b < l || r < a) return 0;
        if (a <= l && r <= b) return get(k);
        pushDown(k);
        int mid = (l + r) >> 1;
        return max(query(a, b, 2 * k, l, mid), query(a, b, 2 * k + 1, mid + 1, r));
    }
} depth[mn];

ll in[LOG][mn], out[LOG][mn], ctroid[LOG][mn];
ll diameter[mn], sz[mn], sztr[mn], timeDfs;
vector<pl> adj[mn];
bool del[mn];

void calcDfs (int u, int p, int root, int layer) {
    in[layer][u] = ++timeDfs;
    for (auto [v, w] : adj[u]) {
        if (del[v] || v == p) continue;
        calcDfs(v, u, root, layer);
        depth[root].update(in[layer][v], out[layer][v], w, 1, 1, sztr[root]);
    }
    out[layer][u] = timeDfs;
}

int szDfs (int u, int p) {
    sz[u] = 1;
    for (auto [v, w] : adj[u])
        if (!del[v] && v != p) sz[u] += szDfs(v, u);
    return sz[u];
}

int centroid (int u, int p, int layer, int cursz) {
    for (auto [v, w] : adj[u])
        if (!del[v] && v != p && sz[v] > cursz / 2)
            return centroid(v, u, layer, cursz);
    return u;
}

ll twoBest (IT &tr, int sz) {
    ll best, pos; tie(best, pos) = tr.query(0, sz, 1, 0, sz);
    tr.update(pos, 0, 1, 0, sz);
    ll sec = tr.query(0, sz, 1, 0, sz).first;
    tr.update(pos, best, 1, 0, sz);
    return best + sec;
}

ll getDiam (int layer, int u) { return diameter[ctroid[layer][u]]; }

void preDfs (int u, int layer) {
    szDfs(u, u);
    int tmp = sz[u], ori = u;

    u = ctroid[layer][u] = centroid(u, u, layer, tmp);
    sztr[u] = tmp, depth[u] = lazyIT(tmp), tree[u] = IT(adj[u].size());
    timeDfs = 0, calcDfs(u, u, u, layer);

    int trsz = adj[u].size() - 1;
    for (int i = 0; i < adj[u].size(); i++) {
        ll v, w; tie(v, w) = adj[u][i];
        if (!del[v]) {
            ll cur = depth[u].query(in[layer][v], out[layer][v], 1, 1, sztr[u]);
            tree[u].update(i, cur, 1, 0, trsz);
        }
    }
    diameter[u] = twoBest(tree[u], trsz);

    del[u] = 1;
    for (auto [v, w] : adj[u]) {
        if (del[v]) continue;
        preDfs(v, layer + 1);
        diameter[u] = max(diameter[u], getDiam(layer + 1, v));
    }
    del[u] = 0;
}

void update (int u, int layer, int a, int b, ll incr) {
    u = ctroid[layer][u], del[u] = 1;
    if (depth[u].query(in[layer][a], in[layer][a], 1, 1, sztr[u]) >
        depth[u].query(in[layer][b], in[layer][b], 1, 1, sztr[u])) swap(a, b);

    // for this re-rooted subtree, a is parent of b
    depth[u].update(in[layer][b], out[layer][b], incr, 1, 1, sztr[u]);
    int trsz = adj[u].size() - 1;

    function<bool(int,int,int)> range = [&] (int p, int l, int r) {
        return l <= p && p <= r;
    };

    ll ans = 0;
    for (int i = 0; i < adj[u].size(); i++) {
        int v = adj[u][i].first;
        if (del[v]) continue;
        if (range(in[layer][b], in[layer][v], out[layer][v])) {
            ll cur = depth[u].query(in[layer][v], out[layer][v], 1, 1, sztr[u]);
            tree[u].update(i, cur, 1, 0, trsz);

            if (u != a)
                update(v, layer + 1, a, b, incr);
        }
        ans = max(ans, getDiam(layer + 1, v));
    }
    ans = max(ans, twoBest(tree[u], trsz));
    diameter[u] = ans, del[u] = 0;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n, q; ll w; cin >> n >> q >> w;

    vector<tt> edge;
    for (int i = 1; i < n; i++) {
        int a, b; ll c; cin >> a >> b >> c;
        adj[a].emplace_back(b, c);
        adj[b].emplace_back(a, c);
        edge.emplace_back(a, b, c);
    }
    preDfs(1, 0);

    ll ans = 0;
    while (q--) {
        int x, y; cin >> x >> y;
        ll d = (ans + x) % (n - 1), e = (ans + y) % w;
        int a, b; ll weight; tie(a, b, weight) = edge[d];

        ll incr = e - weight;
        edge[d] = make_tuple(a, b, e);
        update(1, 0, a, b, incr);

        ans = getDiam(0, 1);
        cout << ans << "\n";
    }

    return 0;
}

Compilation message (stderr)

diameter.cpp: In function 'void calcDfs(int, int, int, int)':
diameter.cpp:84:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   84 |     for (auto [v, w] : adj[u]) {
      |               ^
diameter.cpp: In function 'int szDfs(int, int)':
diameter.cpp:94:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   94 |     for (auto [v, w] : adj[u])
      |               ^
diameter.cpp: In function 'int centroid(int, int, int, int)':
diameter.cpp:100:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  100 |     for (auto [v, w] : adj[u])
      |               ^
diameter.cpp: In function 'void preDfs(int, int)':
diameter.cpp:125:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  125 |     for (int i = 0; i < adj[u].size(); i++) {
      |                     ~~^~~~~~~~~~~~~~~
diameter.cpp:135:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  135 |     for (auto [v, w] : adj[u]) {
      |               ^
diameter.cpp:118:22: warning: unused variable 'ori' [-Wunused-variable]
  118 |     int tmp = sz[u], ori = u;
      |                      ^~~
diameter.cpp: In function 'void update(int, int, int, int, ll)':
diameter.cpp:157:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  157 |     for (int i = 0; i < adj[u].size(); i++) {
      |                     ~~^~~~~~~~~~~~~~~

• Subtask 1: 11 / 11
• Subtask 2: 13 / 13
• Subtask 3: 0 / 7
• Subtask 4: 18 / 18
• Subtask 5: 0 / 24
• Subtask 6: 0 / 27