Submission #1054755

#	Time	Username	Problem	Language	Result	Execution time	Memory
1054755		VMaksimoski008	Dynamic Diameter (CEOI19_diameter)	C++17	73 / 100	218 ms	42236 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 SegTree {
    int n;
    vector<ll> tree, lazy;

    SegTree(int _n) : n(_n), tree(4*_n+50), lazy(4*_n+50) {}

    void push(int u, int tl, int tr) {
        if(!lazy[u]) return ;
        tree[u] += 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] = max(tree[2*u], tree[2*u+1]);
    }

    ll query(int u, int tl, int tr, int l, int r) {
        if(l > tr || tl > r) return 0;
        if(l <= tl && tr <= r) return tree[u];
        int tm = (tl + tr) / 2;
        return max(query(2*u, tl, tm, l, r), query(2*u+1, tm+1, tr, l, r));
    }

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

ll n, W;
int d[maxn], par[maxn], in[maxn], out[maxn], T[maxn], mx_dep=0, timer=0; ll val[maxn], dp[maxn][3], dist[maxn];
vector<pll> gshit[maxn];
vector<int> graph[maxn];

void dfs1(int u, int p, int c) {
    in[u] = timer++; T[u] = c;
    mx_dep = max(mx_dep, d[u]);
    for(auto &[v, w] : gshit[u]) {
        if(v == p) continue;
        d[v] = d[u] + 1;
        dist[v] = dist[u] + w;
        val[v] = w;
        par[v] = u;
        dfs1(v, u, (u==1?v:c));
    }
    out[u] = timer-1;
}

void dfs(int u) {
    if(u == 0) return ;
    dp[u][0] = dp[u][1] = dp[u][2] = 0; 

    ll mx1=0, mx2=0;
    for(int &v : graph[u]) {
        if(v == par[u]) continue;
        dp[u][0] = max(dp[u][0], dp[v][0] + val[v]);
        dp[u][2] = max(dp[u][2], dp[v][2]);
        if(dp[v][0] + val[v] >= mx1) {
            mx2 = mx1;
            mx1 = dp[v][0] + val[v];
        } else if(dp[v][0] + val[v] >= mx2) {
            mx2 = dp[v][0] + val[v];
        }
    }

    dp[u][1] = mx1 + mx2;
    dp[u][2] = max(dp[u][2], max(dp[u][0], dp[u][1]));
    dfs(par[u]);
}

void dfs2(int u, int p) {
    ll mx1=0, mx2=0;
    for(int &v : graph[u]) {
        if(v == p) continue;
        dfs2(v, u);
        dp[u][0] = max(dp[u][0], dp[v][0] + val[v]);
        dp[u][2] = max(dp[u][2], dp[v][2]);
        if(dp[v][0] + val[v] >= mx1) {
            mx2 = mx1;
            mx1 = dp[v][0] + val[v];
        } else if(dp[v][0] + val[v] >= mx2) {
            mx2 = dp[v][0] + val[v];
        }
    }
 
    dp[u][1] = mx1 + mx2;
    dp[u][2] = max(dp[u][2], max(dp[u][0], dp[u][1]));
}


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

    int q;
    cin >> n >> q >> W;

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

    dfs1(1, 1, 0);
    for(auto &[a, b, w] : edges) if(d[a] > d[b]) swap(a, b);

    if(mx_dep <= 1) {
        multiset<ll> ms;
        for(auto &[a, b, w] : edges) ms.insert(w);

        ll last = 0;
        while(q--) {
            ll d, e;
            cin >> d >> e;
            d = (d + last) % (n - 1);
            e = (e + last) % W;
            ms.erase(ms.find(edges[d][2]));
            edges[d][2] = e;
            ms.insert(e);

            auto it = --ms.end();
            ll ans = *it;
            if(it != ms.begin()) ans += *(--it);

            cout << ans << '\n';
            last = ans;
        }

        return 0;
    }

    if(mx_dep <= 20 || (n <= 5000 && q <= 5000)) {
        ll last = 0;
        dfs2(1, 1);
        while(q--) {
            ll d, e;
            cin >> d >> e;
            d = (d + last) % (n - 1);
            e = (e + last) % W;
            val[edges[d][1]] = e;

            dfs(edges[d][0]);
            cout << dp[1][2] << '\n';
            last = dp[1][2];
        }

        return 0;
    }

    //mora niz kecot
    SegTree tree(n);
    multiset<ll> ms;
    for(int i=1; i<=n; i++) tree.update(in[i], in[i], dist[i]);
    for(int &v : graph[1]) ms.insert(tree.query(in[v], out[v]));

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

        int x = edges[d][1];
        ms.erase(ms.find(tree.query(in[T[x]], out[T[x]])));
        tree.update(in[x], out[x], -edges[d][2]);
        edges[d][2] = e;
        tree.update(in[x], out[x], edges[d][2]);
        ms.insert(tree.query(in[T[x]], out[T[x]]));

        auto it = --ms.end();
        ll ans = *it;
        if(it != ms.begin()) ans += *(--it);

        cout << ans << '\n';
        last = 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: 0 / 27