Submission #637930

#	Time	Username	Problem	Language	Result	Execution time	Memory
637930		MohamedFaresNebili	Dynamic Diameter (CEOI19_diameter)	C++14	100 / 100	3058 ms	165212 KiB

diameter

#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

            using namespace std;
            using ll = long long;

            struct seg
            {
                int N; vector<ll> st, lazy;
                seg() {}
                void init(int _N) {
                    N = _N;
                    st.resize(4 * N);
                    lazy.resize(4 * N);
                }
                void prop(int v, int l, int r) {
                    if(l == r || lazy[v] == 0) return;
                    st[v * 2] += lazy[v];
                    st[v * 2 + 1] += lazy[v];
                    lazy[v * 2] += lazy[v];
                    lazy[v * 2 + 1] += lazy[v];
                    lazy[v] = 0;
                }
                void update(int v, int l, int r, int lo, int hi, ll val) {
                    if(l > hi || r < lo) return;
                    if(l >= lo && r <= hi) {
                        st[v] += val; lazy[v] += val;
                        return;
                    }
                    prop(v, l, r);
                    update(v * 2, l, (l + r) / 2, lo, hi, val);
                    update(v * 2 + 1, (l + r) / 2 + 1, r, lo, hi, val);
                    st[v] = max(st[v * 2], st[v * 2 + 1]);
                }
                ll query(int v, int l, int r, int lo, int hi) {
                    if(l > hi || r < lo) return 0;
                    if(l >= lo && r <= hi) return st[v];
                    prop(v, l, r);
                    return max(query(v * 2, l, (l + r) / 2, lo, hi),
                               query(v * 2 + 1, (l + r) / 2 + 1, r, lo, hi));
                }
            };

            int N, Q; ll W; int S[100005]; seg ST[100005];
            int A[100005], B[100005]; ll C[100005];
            int par[100005], tin[100005], out[100005];
            vector<int> adj[100005]; vector<ll> cur[100005];
            vector<pair<int, int>> G[100005];
            vector<array<int, 3>> E[100005];
            set<pair<ll, int>> ans[100005];
            set<pair<ll, int>> best;
            int timer; vector<int> K;
            bool rem[100005];

            int dfs_size(int v, int p) {
                S[v] = 1;
                for(auto e : adj[v]) {
                    int u = A[e] ^ B[e] ^ v;
                    if(u == p || rem[u]) continue;
                    S[v] += dfs_size(u, v);
                }
                return S[v];
            }
            int dfs_centroid(int v, int p, int _N) {
                for(auto e : adj[v]) {
                    int u = A[e] ^ B[e] ^ v;
                    if(u == p || rem[u]) continue;
                    if(S[u] * 2 > _N)
                        return dfs_centroid(u, v, _N);
                }
                return v;
            }
            void dfs(int v, int p) {
                K.push_back(v); tin[v] = timer++;
                for(auto e : adj[v]) {
                    int u = A[e] ^ B[e] ^ v;
                    if(u == p || rem[u]) continue;
                    par[u] = e; dfs(u, v);
                }
                out[v] = timer - 1;
            }
            void get(int v, int state) {
                auto it = ans[v].rbegin();
                ll res = (*it).first;
                if(ans[v].size() > 1) {
                    it++; res += (*it).first;
                }
                if(state) best.insert({res, v});
                else best.erase({res, v});
            }
            void build(int v) {
                int _N = dfs_size(v, v);
                if(_N == 1) return;
                int centroid = dfs_centroid(v, v, _N);
                K.clear(); ST[centroid].init(_N); timer = 0;
                par[centroid] = -1; dfs(centroid, centroid);
                for(auto u : K) {
                    if(par[u] == -1) continue;
                    E[par[u]].push_back({tin[u], out[u], centroid});
                    ST[centroid].update(1, 0, ST[centroid].N - 1, tin[u], out[u], C[par[u]]);
                }
                int group = 0;
                for(auto e : adj[centroid]) {
                    int u = A[e] ^ B[e] ^ centroid;
                    if(rem[u]) continue;
                    G[centroid].push_back({tin[u], out[u]});
                    ll calc = ST[centroid].query(1, 0, ST[centroid].N - 1, tin[u], out[u]);
                    cur[centroid].push_back(calc);
                    ans[centroid].insert({calc, group++});
                }
                get(centroid, 1); rem[centroid] = 1;
                for(auto e : adj[centroid]) {
                    int u = A[e] ^ B[e] ^ centroid;
                    if(rem[u]) continue;
                    build(u);
                }
            }
            void upd(int I, int O, int D, ll M) {
                int lo = 0, hi = G[D].size() - 1, res = 0;
                while(lo <= hi) {
                    int md = (lo + hi) / 2;
                    if(G[D][md].second < I)
                        lo = md + 1;
                    else hi = md - 1, res = md;
                }
                get(D, 0); ans[D].erase({cur[D][res], res});
                ST[D].update(1, 0, ST[D].N - 1, I, O, M);
                cur[D][res] = ST[D].query(1, 0, ST[D].N - 1, G[D][res].first, G[D][res].second);
                ans[D].insert({cur[D][res], res}); get(D, 1);
            }

            int32_t main() {
                ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
                cin >> N >> Q >> W;
                for(int l = 1; l < N; l++) {
                    cin >> A[l] >> B[l] >> C[l];
                    adj[A[l]].push_back(l);
                    adj[B[l]].push_back(l);
                }
                build(1); ll last = 0;
                for(int l = 0; l < Q; l++) {
                    int d; ll e; cin >> d >> e;
                    d = (d + last) % (N - 1) + 1;
                    e = (e + last) % W;
                    for(auto u : E[d])
                        upd(u[0], u[1], u[2], e - C[d]);
                    C[d] = e; last = (*best.rbegin()).first;
                    cout << last << "\n";
                }
                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