Submission #1055337

#	Time	Username	Problem	Language	Result	Execution time	Memory
1055337		VMaksimoski008	Dynamic Diameter (CEOI19_diameter)	C++17	100 / 100	172 ms	66044 KiB

diameter

#include <bits/stdc++.h>
#define int long long

using namespace std;

using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

const int mod = 1e9 + 7;
const int LOG = 20;
const int maxn = 1e5 + 5;

struct Node {
    ll ans, mn, mx, lhs, rhs;
};

Node merge(Node a, Node b) {
	Node x;
    x.ans = max({ a.ans, b.ans, a.lhs + b.mx, a.mx + b.rhs });
    x.mn = min(a.mn, b.mn);
    x.mx = max(a.mx, b.mx);
    x.lhs = max({ a.lhs, b.lhs, a.mx-2*b.mn });
    x.rhs = max({ a.rhs, b.rhs, -2*a.mn+b.mx });
    return x;
}

struct SegTree {
    int n;
    vector<Node> tree;
    vector<ll> lazy, v;

    SegTree(vector<ll> _v) {
        v = _v;
        n = v.size();
        tree.resize(4*n+50);
        lazy.resize(4*n+50);
        build(1, 0, n-1);
    }

    void build(int u, int tl, int tr) {
        if(tl == tr) {
            tree[u].mn = tree[u].mx = v[tl];
            tree[u].lhs = tree[u].rhs = -v[tl];
        } else {
            int tm = (tl + tr) / 2;
            build(2*u, tl, tm);
            build(2*u+1, tm+1, tr);
            tree[u] = merge(tree[2*u], tree[2*u+1]);
        }
    }

    void push(int u, int tl, int tr) {
        if(!lazy[u]) return ;
        tree[u].mx += lazy[u];
        tree[u].mn += lazy[u];
        tree[u].lhs -= lazy[u];
        tree[u].rhs -= lazy[u];

        if(tl != tr) {
            lazy[2*u] += lazy[u];
            lazy[2*u+1] += lazy[u];
        }

        lazy[u] = 0;
    }

    void update(int u, int tl, int tr, int l, int r, ll v) {
        push(u, tl, tr);
        if(l > tr || tl > r) return ;

        if(l <= tl && tr <= r) {
            lazy[u] += v;
            push(u, tl, tr);
            return ;
        }

        int tm = (tl + tr) / 2;
        update(2*u, tl, tm, l, r, v);
        update(2*u+1, tm+1, tr, l, r, v);
        tree[u] = merge(tree[2*u], tree[2*u+1]);
    }

    void update(int l, int r, ll v) { update(1, 0, n-1, l, r, v); }
};

int in[maxn], out[maxn];
ll d[maxn], dist[maxn];
vector<pll> graph[maxn];
vector<ll> to_build;

void dfs(int u, int p) {
    in[u] = to_build.size();
    to_build.push_back(dist[u]);
    for(auto &[v, w] : graph[u]) {
        if(v == p) continue;
        d[v] = d[u] + 1;
        dist[v] = dist[u] + w;
        dfs(v, u);
        to_build.push_back(dist[u]);
    }
    out[u] = to_build.size() - 1;
}

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

    ll n, q, W;
    cin >> n >> q >> W;

    vector<array<ll, 3> > edges;
    for(int i=0; i<n-1; i++) {
        int a, b, w;
        cin >> a >> b >> w;
        edges.push_back({ a, b, w });
        graph[a].push_back({ b, w });
        graph[b].push_back({ a, w });
    }

    dfs(1, 1);
    for(auto &[a, b, w] : edges) if(d[a] > d[b]) swap(a, b);
    
    SegTree tree(to_build);
    ll last = 0;

    while(q--) {
        ll d, e;
        cin >> d >> e;
        d = (d + last) % (n - 1);
        e = (e + last) % W;

        tree.update(in[edges[d][1]], out[edges[d][1]], e - edges[d][2]);
        edges[d][2] = e;
        cout << tree.tree[1].ans << '\n';
        last = tree.tree[1].ans;
    }

    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