Submission #1006626

#	Time	Username	Problem	Language	Result	Execution time	Memory
1006626		imarn	Dynamic Diameter (CEOI19_diameter)	C++14	100 / 100	174 ms	49348 KiB

diameter

#include<bits/stdc++.h>
//#include "gap.h"
#pragma GCC optimize("O3")
#pragma GCC target("avx2")
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define plx pair<ll,int>
#define f first
#define s second
#define pb push_back
#define all(x) x.begin(),x.end()
#define vi vector<int>
#define vl vector<ll>
using namespace std;
const int mxn=1e5+5;
vector<pair<int,ll>>g[mxn];
ll d[mxn]{0};
vector<int>ord;
int idx[mxn]{0},sz,lst[mxn];
void tour(int u,int p){
    ord.pb(u);idx[u]=ord.size();lst[u]=ord.size();
    for(auto v:g[u]){
        if(v.f==p)continue;
        d[v.f]=d[u]+v.s;
        tour(v.f,u);ord.pb(u);
        lst[u]=ord.size();
    }
}
struct node{
    ll mnd,pref,suf,mx,mxd;
    node operator+(node b){
        node res;
        res.mnd=min(mnd,b.mnd);
        res.pref=max(pref,b.pref);
        res.pref=max(res.pref,mxd-2*b.mnd);
        res.suf=max(suf,b.suf);
        res.suf=max(res.suf,b.mxd-2*mnd);
        res.mxd=max(mxd,b.mxd);
        res.mx=max(mx,b.mx);
        res.mx=max(res.mx,pref+b.mxd);
        res.mx=max(res.mx,mxd+b.suf);
        return res;
    }
}t[16*mxn];ll lz[16*mxn]{0};
void push(int i,int l,int r){
    t[i].mnd+=lz[i];
    t[i].pref-=lz[i];
    t[i].suf-=lz[i];
    t[i].mxd+=lz[i];
    if(l<r)lz[2*i]+=lz[i],lz[2*i+1]+=lz[i];
    lz[i]=0;
}
void build(int i,int l,int r){
    if(l==r)return void(t[i]={d[ord[l-1]],-d[ord[l-1]],-d[ord[l-1]],0,d[ord[l-1]]});
    int m=(l+r)>>1;build(2*i,l,m);build(2*i+1,m+1,r);
    t[i]=t[2*i]+t[2*i+1];
}
void update(int i,int l,int r,int tl,int tr,ll v){
    push(i,l,r);
    if(r<tl||l>tr)return;
    if(r<=tr&&l>=tl){
        lz[i]+=v;push(i,l,r);return;
    }int m=(l+r)>>1;update(2*i,l,m,tl,tr,v);update(2*i+1,m+1,r,tl,tr,v);
    t[i]=t[2*i]+t[2*i+1];
}
struct edge{
    int a,b;ll c;
}rod[mxn];
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    int n,q;ll w;cin>>n>>q>>w;
    for(int i=1;i<=n-1;i++){
        int a,b;ll c;cin>>a>>b>>c;
        g[a].pb({b,c});g[b].pb({a,c});
        rod[i-1]={a,b,c};
    }tour(1,1);sz=ord.size();build(1,1,sz);
    ll ans=0;
    while(q--){
        ll dx,e;cin>>dx>>e;dx=(dx+ans)%(n-1);e=(e+ans)%w;
        if(dx<0)dx+=n-1;if(e<0)e+=w;
        int a=rod[dx].a,b=rod[dx].b;ll x=rod[dx].c;
        if(d[a]<d[b])swap(a,b);update(1,1,sz,idx[a],lst[a],e-x);
        rod[dx].c=e;ans=t[1].mx;cout<<ans<<'\n';
    }
}

Compilation message (stderr)

diameter.cpp: In function 'int main()':
diameter.cpp:81:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   81 |         if(dx<0)dx+=n-1;if(e<0)e+=w;
      |         ^~
diameter.cpp:81:25: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   81 |         if(dx<0)dx+=n-1;if(e<0)e+=w;
      |                         ^~
diameter.cpp:83:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   83 |         if(d[a]<d[b])swap(a,b);update(1,1,sz,idx[a],lst[a],e-x);
      |         ^~
diameter.cpp:83:32: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   83 |         if(d[a]<d[b])swap(a,b);update(1,1,sz,idx[a],lst[a],e-x);
      |                                ^~~~~~

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