Submission #380818

#	Time	Username	Problem	Language	Result	Execution time	Memory
380818		YJU	Dynamic Diameter (CEOI19_diameter)	C++14	100 / 100	634 ms	63980 KiB

diameter

#include<bits/stdc++.h>
#pragma GCC optimize("unroll-loops,no-stack-protector,Ofast")
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef long double ld;
const ll N=2e5+5;
const ll MOD=1e9+7;
const ll INF=(1LL<<60);
#define REP(i,n) for(ll i=0;i<n;i++)
#define REP1(i,n) for(ll i=1;i<=n;i++)
#define pb push_back
#define mp make_pair
#define X first
#define Y second
#define lwb lower_bound
#define SZ(_a) (ll)_a.size()

struct node{
	ll lazy,a,b,ab,ba,dia;
	node(){
		lazy=a=b=ab=ba=dia=0;
	}
	node operator +(node B){
        node tmp;
        tmp.a=max(a,B.a);
        tmp.b=max(b,B.b);
        tmp.ab=max(max(ab,B.ab),a+B.b);
        tmp.ba=max(max(ba,B.ba),b+B.a);
        tmp.dia=max(max(dia,B.dia),max(a+B.ba,ab+B.a));
        return tmp;
	}
}tree[4*N];

void mod(ll id,ll del){
	tree[id].a+=del;
	tree[id].b-=2*del;
	tree[id].ab-=del;
	tree[id].ba-=del;
}

void push(ll id){
	if(tree[id].lazy){
        mod(id*2,tree[id].lazy);
        mod(id*2+1,tree[id].lazy);
        tree[id*2].lazy+=tree[id].lazy;
        tree[id*2+1].lazy+=tree[id].lazy;
        tree[id].lazy=0;
	}
}

void upd(ll id,ll l,ll r,ll ql,ll qr,ll del){
	if(l>=qr||r<=ql)return ;
	if(l>=ql&&r<=qr){
        mod(id,del);
        tree[id].lazy+=del;
        return;
	}
	push(id);
	ll mid=(l+r)>>1;
	upd(id*2,l,mid,ql,qr,del);
	upd(id*2+1,mid,r,ql,qr,del);
	tree[id]=tree[id*2]+tree[id*2+1];
}

ll n,q,m,x[N],y[N],c[N],in[N],out[N],ti,fa[N];
vector<ll> v[N];

void DFS(ll nd,ll e){
	in[nd]=ti++;
	for(auto i:v[nd]){
		if(i==e)continue;
        ll to=x[i]+y[i]-nd;
        fa[i]=to;
        DFS(to,i);
	}
	out[nd]=ti++;
}

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
    cin>>n>>q>>m;
    REP(i,n-1){
		cin>>x[i]>>y[i]>>c[i];
		v[x[i]].pb(i);
		v[y[i]].pb(i);
    }
    DFS(1,-1);
    REP(i,n-1){
		ll nd=fa[i];
		//cout<<i<<" "<<nd<<" ";
		upd(1,0,ti,in[nd],out[nd],c[i]);
		//cout<<tree[1].dia<<"\n";
    }
    //cout<<tree[1].dia<<"\n";
    ll lst=0;
    while(q--){
		ll a,b;
		cin>>a>>b;
        a=(a+lst)%(n-1);
        b=(b+lst)%m;
        ll nd=fa[a];
		upd(1,0,ti,in[nd],out[nd],b-c[a]);
		c[a]=b;
		cout<<(lst=tree[1].dia)<<"\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