Submission #420075

#	Time	Username	Problem	Language	Result	Execution time	Memory
420075		alirezasamimi100	Dynamic Diameter (CEOI19_diameter)	C++17	100 / 100	399 ms	49696 KiB

diameter

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
/*#pragma comment(linker, "/stack:200000000")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")*/
/*#pragma GCC optimize("O2")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,sse,sse2,fma")*/
using namespace std;
using ll = long long int;
using ld = long double;
#define F first
#define S second
#define pb push_back
//#define mp make_pair
#define lc v<<1
#define rc v<<1|1
#define fast_io ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
const int N=2e5+10,LN=18,M=3.5e7+10,SQ=350,BS=737,inf=1e9+10;
const ll INF=1e15;
const ld ep=1e-7;
const int MH=1000696969,MOD=1000000007,MD=998244353;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using pll=pair<ll,ll>;
using pii=pair<int,int>;
#define ordered_set tree<pll, null_type,less<pll>, rb_tree_tag,tree_order_statistics_node_update>
ll pow(ll x, ll y, ll mod){
    ll ans=1;
    while (y != 0) {
        if (y & 1) ans = ans * x % mod;
        y >>= 1;
        x = x * x % mod;
    }
    return ans;
}
ll n,q,W,A[N],B[N],C[N],H[N],st[N],fn[N],lz[N*4],lst;
vector<ll> dd={-1};
vector<pll> adj[N];
void dfs(ll v, ll p=0){
    st[v]=dd.size();
    dd.pb(v);
    for(auto [u,w] : adj[v]){
        if(u!=p){
            H[u]=H[v]+w;
            dfs(u,v);
            dd.pb(v);
        }
    }
    fn[v]=dd.size();
}
struct node{
    ll mx,mn,ans,mr,ml;
    node operator+(node t){
        node an;
        an.ans=max({ans,t.ans,ml+t.mx,t.mr+mx});
        an.mx=max(mx,t.mx);
        an.mn=min(mn,t.mn);
        an.ml=max({ml,t.ml,mx-2*t.mn});
        an.mr=max({mr,t.mr,t.mx-mn*2});
        return an;
    }
} f[N*4];
void build(ll v, ll l, ll r){
    if(r-l==1){
        f[v].ans=0;
        f[v].mx=f[v].mn=H[dd[l]];
        f[v].ml=f[v].mr=-f[v].mx;
        return;
    }
    ll m=(l+r)>>1;
    build(lc,l,m);
    build(rc,m,r);
    f[v]=f[lc]+f[rc];
}
void shift(ll v, ll l, ll r){
    if(!lz[v]) return;
    f[v].mx+=lz[v];
    f[v].mn+=lz[v];
    f[v].mr-=lz[v];
    f[v].ml-=lz[v];
    if(r-l>1){
        lz[lc]+=lz[v];
        lz[rc]+=lz[v];
    }
    lz[v]=0;
}
void upd(ll v, ll l, ll r, ll tl, ll tr, ll x){
    shift(v,l,r);
    if(tl>=tr) return;
    if(tl==l && tr==r){
        lz[v]+=x;
        return shift(v,l,r);
    }
    ll m=(l+r)>>1;
    upd(lc,l,m,tl,min(m,tr),x);
    upd(rc,m,r,max(m,tl),tr,x);
    f[v]=f[lc]+f[rc];
}
int main(){
    fast_io;
    cin >> n >> q >> W;
    for(ll i=0; i<n-1; i++){
        cin >> A[i] >> B[i] >> C[i];
        adj[A[i]].pb({B[i],C[i]});
        adj[B[i]].pb({A[i],C[i]});
    }
    dfs(1);
    ll k=dd.size();
    build(1,1,k);
    while(q--){
        ll d,e;
        cin >> d >> e;
        d=(d+lst)%(n-1);
        e=(e+lst)%W;
        ll v=A[d];
        if(st[B[d]]>st[v]) v=B[d];
        upd(1,1,k,st[v],fn[v],e-C[d]);
        C[d]=e;
        lst=f[1].ans;
        cout << lst << '\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