Submission #1326151

#	Time	Username	Problem	Language	Result	Execution time	Memory
1326151		boclobanchat	Dynamic Diameter (CEOI19_diameter)	C++20	100 / 100	295 ms	47756 KiB

diameter

#include<bits/stdc++.h>
using namespace std;
const int MAXN=2e5+5;
struct edge
{
	long long nex,pos,val;
};
struct node
{
	long long ans,mnpref,mxsuff,fpref,fsuff,fsum,sum;
};
node merge(node a,node b)
{
	node c;
	c.ans=max(max(a.ans,b.ans),max(-a.mnpref+b.fsuff,a.fpref+b.mxsuff));
	c.mnpref=min(b.mnpref,b.sum+a.mnpref);
	c.mxsuff=max(a.mxsuff,a.sum+b.mxsuff);
	c.fsum=max(-a.sum+b.sum,max(-a.sum+b.fsum,a.fsum+b.sum));
	c.fpref=max(-a.mnpref+b.fsum,max(b.fpref,b.sum+a.fpref));
	c.fsuff=max(b.mxsuff+a.fsum,max(a.fsuff,-a.sum+b.fsuff));
	c.sum=a.sum+b.sum;
	return c;
}
node seg[MAXN*4];
void update(int l,int r,int i,long long val,int pos)
{
	if(i<l||r<i) return ;
	if(l==r)
	{
		seg[pos]={abs(val),val,val,abs(val),abs(val),abs(val),val};
		return ;
	}
	int mid=(l+r)/2;
	update(l,mid,i,val,pos*2);
	update(mid+1,r,i,val,pos*2+1);
	seg[pos]=merge(seg[pos*2],seg[pos*2+1]);
}
vector<edge> ds[MAXN];
int L[MAXN],R[MAXN],pos[MAXN],tdfs=0;
long long len[MAXN];
void dfs(int i,int pre)
{
	L[i]=++tdfs;
	for(auto v:ds[i]) if(v.nex!=pre)
	{
		pos[v.pos]=v.nex;
		dfs(v.nex,i);
	}
	R[i]=++tdfs;
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n,q;
	long long w;
	cin>>n>>q>>w;
	for(int i=1;i<n;i++)
	{
		long long l,r,v;
		cin>>l>>r>>v;
		ds[l].push_back({r,i,v}),ds[r].push_back({l,i,v});
		len[i]=v;
	}
	dfs(1,1);
	for(int i=1;i<n;i++)
	{
		update(1,n*2,L[pos[i]],len[i],1);
		update(1,n*2,R[pos[i]],-len[i],1);
	}
	long long last=0;
	while(q--)
	{
		long long d,e;
		cin>>d>>e;
		d=(d+last)%(n-1)+1,len[d]=e=(e+last)%w;
		update(1,n*2,L[pos[d]],e,1);
		update(1,n*2,R[pos[d]],-e,1);
		cout<<(last=seg[1].ans)<<"\n";
	}
}

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