제출 #1303665

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1303665		MuhammadSaram	Dynamic Diameter (CEOI19_diameter)	C++20	100 / 100	1225 ms	45232 KiB

diameter

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define endl '\n'

const int M = 1e5 + 1;

struct node
{
	int x, l, i;
};

int subt[M], st[M], en[M], par[M], nx[M], id[M], cnt[M], ind[M], rev[M], t, t1, n;
node seg[M*2];
vector<pair<int,int>> nei[M],nei1[M];
vector<node> seg1[M];

void push(int v,int lc,int rc)
{
	seg[lc].x+=seg[v].l, seg[lc].l+=seg[v].l;
	seg[rc].x+=seg[v].l, seg[rc].l+=seg[v].l;
	seg[v].l=0;
}

node merge(node a, node b)
{
	if (b.x>a.x) a=b;
	a.l=0;
	return a;
}

void modify(int l,int r,int x,int v=0,int s=0,int e=n)
{
	if (l>=e or r<=s) return;
	if (l<=s && e<=r)
	{
		if (s+1==e) seg[v].i=s;
		seg[v].x+=x, seg[v].l+=x;
		return;
	}
	int mid=(s+e)/2, lc=v+1, rc=v+(mid-s)*2;
	push(v,lc,rc);
	modify(l,r,x,lc,s,mid);
	modify(l,r,x,rc,mid,e);
	seg[v]=merge(seg[lc],seg[rc]);
}

node get(int l,int r,int v=0,int s=0,int e=n)
{
	if (l>=e or r<=s) return {0,0,0};
	if (l<=s && e<=r) return seg[v];
	int mid=(s+e)/2, lc=v+1, rc=v+(mid-s)*2;
	push(v,lc,rc);
	return merge(get(l,r,lc,s,mid),get(l,r,rc,mid,e));
}

void push1(int v,int lc,int rc,int i)
{
	seg1[i][lc].x+=seg1[i][v].l, seg1[i][lc].l+=seg1[i][v].l;
	seg1[i][rc].x+=seg1[i][v].l, seg1[i][rc].l+=seg1[i][v].l;
	seg1[i][v].l=0;
}

void mod(int l,int r,int x,int i,int v,int s,int e)
{
	if (l>=e or r<=s) return;
	if (l<=s && e<=r)
	{
		seg1[i][v].x+=x, seg1[i][v].l+=x;
		return;
	}
	int mid=(s+e)/2, lc=v+1, rc=v+(mid-s)*2;
	push1(v,lc,rc,i);
	mod(l,r,x,i,lc,s,mid);
	mod(l,r,x,i,rc,mid,e);
	seg1[i][v]=merge(seg1[i][lc],seg1[i][rc]);
}

int get1(int l,int r,int i,int v,int s,int e)
{
	if (l>=e or r<=s) return -M*3;
	if (l<=s && e<=r) return seg1[i][v].x;
	int mid=(s+e)/2, lc=v+1, rc=v+(mid-s)*2;
	push1(v,lc,rc,i);
	return max(get1(l,r,i,lc,s,mid),get1(l,r,i,rc,mid,e));
}

void dfs(int u)
{
	subt[u]=1;
	for (int i=0;i+1<nei[u].size();i++)
		if (nei[u][i].first==par[u])
			swap(nei[u][i],nei[u][i+1]);
	if (par[u]) nei[u].pop_back();
	for (auto [i,w]:nei[u])
		if (i!=par[u])
			par[i]=u, dfs(i), subt[u]+=subt[i];
	for (int i=(int)nei[u].size()-1;i>0;i--)
		if (subt[nei[u][i].first]>subt[nei[u][i-1].first])
			swap(nei[u][i], nei[u][i-1]);
}

void doit(int u)
{
	if (nei[u].empty()) return;
	nx[nei[u][0].first]=nx[u], id[nei[u][0].first]=id[u], ind[nei[u][0].first]=ind[u]+1, cnt[id[u]]++;
	for (auto [i,w]:nei[u])
	{
		if (i!=nei[u][0].first)
			nx[i]=i, id[i]=t1++, ind[i]=0, cnt[id[i]]++;
		doit(i);
	}
}

void et(int u,int val=0)
{
	st[u]=t++, rev[st[u]]=u;
	modify(st[u],st[u]+1,val);
	for (auto [i,w]:nei[u])
		et(i,val+w), nei1[u].push_back({en[i],i});
	en[u]=t;
}

signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(NULL), cout.tie(NULL);

	int q,W;
	cin>>n>>q>>W;
	int u[n], v[n], w[n];
	for (int i=0;i<n-1;i++)
	{
		cin>>u[i]>>v[i]>>w[i];
		nei[u[i]].push_back({v[i],w[i]});
		nei[v[i]].push_back({u[i],w[i]});
	}
	dfs(1);
	et(1);
	nx[1]=1, id[1]=t1++, cnt[0]++, ind[1]=0;
	doit(1);
	for (int i=0;i<t1;i++)
		seg1[i]=vector<node>(cnt[i]*2);
	for (int i=1;i<=n;i++)
	{
		int x=get(st[nx[i]],st[nx[i]]+1).x;
		mod(ind[i],ind[i]+1,(nei[i].size()?get(en[nei[i][0].first],en[i]).x-2*get(st[i],st[i]+1).x+x:0),id[i],0,0,cnt[id[i]]);
	}
	for (int i=0;i<n-1;i++)
		if (st[v[i]]>st[u[i]]) swap(u[i],v[i]);
	int ls=0;
	while (q--)
	{
		int d,e;
		cin>>d>>e;
		d=(d+ls)%(n-1), e=(e+ls)%W;
		modify(st[u[d]],en[u[d]],e-w[d]);
		int up=u[d];
		if (nx[up]!=up)
			mod(ind[up],cnt[id[up]],w[d]-e,id[up],0,0,cnt[id[up]]);
		while (par[up])
		{
			if (up==nx[up])
			{
				int o=get1(ind[par[up]],ind[par[up]]+1,id[par[up]],0,0,cnt[id[par[up]]]);
				mod(ind[par[up]],ind[par[up]]+1,get(en[nei[par[up]][0].first],en[par[up]]).x-2*get(st[par[up]],st[par[up]]+1).x+get(st[nx[par[up]]],st[nx[par[up]]]+1).x-o,id[par[up]],0,0,cnt[id[par[up]]]),up=par[up];
			}
			else up=nx[up];
		}
		node nd=get(0,n);
		int val=nd.x, mx=0,u=rev[nd.i];
		while (par[u])
		{
			if (nei[par[u]][0].first==u)
				mx=max(mx,get1(0,ind[par[u]]+1,id[par[u]],0,0,cnt[id[par[u]]])-get(st[nx[u]],st[nx[u]]+1).x), u=nx[u];
			else
			{
				int x=lower_bound(nei1[par[u]].begin(),nei1[par[u]].end(),make_pair(en[u],0ll))-begin(nei1[par[u]]);
				mx=max(mx,merge(get(st[par[u]],st[nei[par[u]][x].first]),get(en[nei[par[u]][x].first],en[par[u]])).x-2*get(st[par[u]],st[par[u]]+1).x);
				u=par[u];
			}
		}
		ls=val+mx, w[d]=e;
		cout<<ls<<endl;
	}
	
	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