Submission #1242418

#	Time	Username	Problem	Language	Result	Execution time	Memory
1242418		yassia	Dynamic Diameter (CEOI19_diameter)	C++20	55 / 100	1126 ms	64736 KiB

diameter

#ifndef local
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("O3")
#endif
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
using ll = long long;
#define int ll
using pii = pair<int, int>;
using pll = pair<ll,ll>;
using str = string;
using ld = long double;
using hash_map =gp_hash_table<int, int>;
using hash_set= gp_hash_table <int, null_type>;
auto sd = std::chrono::high_resolution_clock::now().time_since_epoch().count();
mt19937 rnd(sd);
typedef tree<ll, null_type, less<>, rb_tree_tag,
        tree_order_statistics_node_update> ord_set;
const ll maxn = 3e5+8;
const ll inf = 2e18+7;
const ll logn = 20;
ll n;
ll dp[maxn];
ll dist[maxn];
ll d_bfs[maxn];
ll pr[maxn];
ll wei[maxn];
ll d[5*maxn];
ll ps[5*maxn];
ll bup[logn+3][maxn];
ll timer= 0 ;
ll tin[maxn]; ll tout[maxn];
void push(ll v) {
    if (ps[v]==0)return;
    ps[v*2] += ps[v]; ps[v*2+1]+=ps[v];
    d[v*2]+=ps[v]; d[v*2+1]+=ps[v];
    ps[v] = 0;
}

void upd(ll v, ll l, ll r, ll sl, ll sr, ll x){
    push(v);
    if (sl <= l && r <= sr){
        ps[v]+=x;
        d[v]+=x;
        push(v);
        return;
    }
    else if (sr <= l || r <= sl){
        return;
    }push(v);
    upd(v*2 ,l, (l+r)/2, sl, sr,x); upd(v*2+1, (l+r)/2, r, sl, sr, x);
    d[v]=max(d[v*2],d[v*2+1]);
}
ll get_max(ll v, ll l, ll r, ll sl, ll sr){
    push(v);
    if (sl <= l &&r <= sr){
        return d[v];
    }
    else if (sr <= l || r <= sl)return 0;
    push(v);
    return max(get_max(v*2, l, (l+r)/2, sl, sr),get_max(v*2+1, (l+r)/2, r, sl, sr));
}
void cntp(ll v, vector<vector<ll>>&g,ll p){
    pr[v] = p;
    if (p != -1){
        dp[v] = dp[p]+1;
    }
    tin[v]=timer++;
    for (auto u: g[v]) {
        if (u != p){
            cntp(u, g, v);
            bup[0][u] = v;
        }
    }
    tout[v]=timer++;
}
void dfs(ll v, vector<vector<ll>>&g){
    if (pr[v]!=-1)dist[v] = dist[pr[v]] +wei[v];
    else dist[v] = 0;
    for (auto u : g[v]){
        if (u != pr[v]){
            dfs(u, g);
        }
    }
}
void bfs(ll u, vector<vector<ll>> &g){
    for(int i = 1; i <= n; i++){
        d_bfs[i] = inf;
    }
    d_bfs[u] = 0;
    queue<ll> q;
    q.push(u);
    ll w=  0;
    while (!q.empty()){
        u= q.front();
        q.pop();
        for (auto v  : g[u]){
            if (pr[u]==v) w = wei[u];
            else w = wei[v];
            if (d_bfs[v]>d_bfs[u]+w){
                d_bfs[v]= d_bfs[u]+w;
                q.push(v);
            }
        }
    }
}
void solve1() {
    ll  q, ww;
    cin >> n >> q>>ww;
    vector<vector<ll>> g(n+1);
    // 3 and 5g
    // 1 and 2
    // 4
    vector<vector<ll>>edges;
    set<pll> ee;
    for (int i =0; i < n-1; i++){
        ll u, v;
        cin>>u>>v;
        g[u].push_back(v);
        g[v].push_back(u);
        ee.insert({min(u,v),max(u,v)});
        ll w; cin >> w;
        edges.push_back({u, v, w});
    }

    if (n <= 100000000ll/q){
        ll root = 1;
        for (int i = 1; i <= n; i++){
            if (g[i].size()>=2){
                root = i;
                break;
            }
        }cntp(root, g, -1);
        for (auto t : edges){
            ll u = t[0]; ll v = t[1];
            ll w = t[2];
            if (pr[u]==v){
                wei[u] = w;
            }
            else wei[v] = w;
        }
        ll last= 0;
        for (int j =0 ; j < q; j++){
            ll dj, ej;
            cin>>dj>>ej;
            dj = (dj+last)%(n-1);
            ej = (ej+last)%ww;
            edges[dj][2] = ej;
            if (edges[dj][0] == pr[edges[dj][1]]){
                wei[edges[dj][1]] = ej;
            }
            else {
                wei[edges[dj][0]] = ej;
            }
            dfs(root, g);
            ll u1 =root;
            ll w1 = 0;
            for (int i = 1; i<= n;i++){
                if (dist[i]>w1){
                    w1 = dist[i];
                    u1= i;
                }
            }
            bfs(u1, g);
            ll mx_ans = 0;
            for (int i = 1; i <= n; i++){
                mx_ans =max(mx_ans, d_bfs[i]);
            }
            last = mx_ans;
            cout<<mx_ans<<endl;
        }
    }
    else {
        ll root = 1;
        cntp(root, g, -1);
        for (auto t : edges){
            ll u = t[0]; ll v = t[1];
            ll w = t[2];
            if (pr[u]==v){
                wei[u] = w;
            }
            else wei[v] = w;
        }
        dfs(root, g);
        for (int lg = 1; lg <= logn; lg++){
            for (int i =1; i <= n;i++){
                bup[lg][i] = bup[lg-1][bup[lg-1][i]];
            }
        }
        for (int i =1; i<= n;i++){
            upd(1, 0, timer, tin[i],tin[i]+1,dist[i]);
            upd(1, 0, timer, tout[i], tout[i]+1, dist[i]);
        }
        ll last= 0;
        multiset<pll> all;
        for (auto u : g[root]){
            all.insert({-get_max(1, 0, timer, tin[u], tout[u]+1), u});
        }
        for (int i = 0; i <q; i++){
            ll dj, ej;
            cin>>dj>>ej;
            dj = (dj+last)%(n-1);
            ej = (ej+last)%ww;
            ll uu = edges[dj][0];
            ll vv = edges[dj][1];
            if (pr[uu]==vv) {
                swap(uu,vv);
            }
            edges[dj][2] = ej;
            ll prev_wei = wei[vv];
            wei[vv] = ej;
            ll changed = vv;
            for (int up = logn; up >= 0; up--){
                if (dp[bup[up][changed]]>=1){
                    changed = bup[up][changed];
                }
            }
            all.erase({-get_max(1, 0, timer, tin[changed], tout[changed]+1), changed});
            upd(1, 0, timer, tin[vv], tout[vv]+1, wei[vv]-prev_wei);
            all.insert({-get_max(1, 0, timer, tin[changed], tout[changed]+1), changed});
            ll ans1 = -all.begin()->first;
            ll ans0 = 0;
            if (all.size()>1){
                auto h = *(all.begin().operator++());
                ans0 = -h.first;
            }
            cout<<ans1+ans0<<endl;
            last =ans1+ans0;
        }
    }

}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
#ifdef local
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif

    int t1 = 1;
    while (t1) solve1(), t1--;

#ifdef local
    printf_s("\n%.5f s", (double) clock() / CLOCKS_PER_SEC);
#endif
}

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