Submission #1289968

#	Time	Username	Problem	Language	Result	Execution time	Memory
1289968		boclobanchat	Grapevine (NOI22_grapevine)	C++20	100 / 100	865 ms	156356 KiB

Main

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+5;
const long long INF=1e18;
struct subtree
{
	int n;
	vector<long long> seg,lazy;
	vector< pair<int,int> > vi;
	vector<int> R;
	int getnode(int pos) { return vi[lower_bound(vi.begin(),vi.end(),(pair<int,int>){pos,0})-vi.begin()].second; }
	void build()
	{
		n=vi.size();
		sort(vi.begin(),vi.end());
		seg.resize(n*4+2,INF),lazy.resize(n*4+2);
	}
	void down(int pos)
	{
		long long val=lazy[pos];
		seg[pos*2]+=val,seg[pos*2+1]+=val;
		lazy[pos*2]+=val,lazy[pos*2+1]+=val;
		lazy[pos]=0;
	}
	void update(int l,int r,int i,long long val,int pos)
	{
		while(l<r)
		{
			int mid=(l+r)/2;
			down(pos);
			if(i<=mid) r=mid,pos*=2;
			else l=mid+1,pos=pos*2+1;
		}
		seg[pos]=val;
		while(pos) pos/=2,seg[pos]=min(seg[pos*2],seg[pos*2+1]);
	}
	void update(int l,int r,int u,int v,int val,int pos)
	{
		if(v<l||r<u) return ;
		if(u<=l&&r<=v)
		{
			seg[pos]+=val,lazy[pos]+=val;
			return ;
		}
		int mid=(l+r)/2;
		down(pos);
		update(l,mid,u,v,val,pos*2);
		update(mid+1,r,u,v,val,pos*2+1);
		seg[pos]=min(seg[pos*2],seg[pos*2+1]);
	}
	void update(int u,long long val)
	{
		u=getnode(u);
		update(1,n,u,val,1);
	}
	void update(int u,int v,int w)
	{
		u=getnode(u),v=getnode(v);
		if(u>v) swap(u,v);
		update(1,n,v,R[v],w,1);
	}
};
vector< pair<int,int> > ds[MAXN];
int sp[MAXN][20],dis[MAXN],root[MAXN],sub[MAXN],L[MAXN],R[MAXN],D[MAXN],F[MAXN],dep[MAXN],tdfs=0,cnt=0;
long long fen[MAXN];
bool ck[MAXN];
subtree T[MAXN];
void update(int i,int n,int val) { for(;i<=n;i+=i&-i) fen[i]+=val; }
long long get(int i) { long long ans=0;for(;i;i-=i&-i) ans+=fen[i];return ans; }
void dfs(int i,int pre)
{
	sp[i][0]=pre,L[i]=++tdfs;
	for(int j=1;j<=16;j++) sp[i][j]=sp[sp[i][j-1]][j-1];
	for(auto v:ds[i]) if(v.first!=pre)
	{
		dis[v.first]=dis[i]+1,F[v.first]=v.second;
		dfs(v.first,i);
	}
	R[i]=tdfs;
}
int lca(int a,int b)
{
	int x=dis[a],y=dis[b],m=min(x,y);
	for(int i=16;i+1;i--)
	{
		if((x-m)&(1<<i)) a=sp[a][i];
		if((y-m)&(1<<i)) b=sp[b][i];
	}
	if(a==b) return a;
	for(int i=16;i+1;i--) if(sp[a][i]!=sp[b][i]) a=sp[a][i],b=sp[b][i];
	return sp[a][0];
}
long long getdis(int a,int b) { return get(L[a])+get(L[b])-get(L[lca(a,b)])*2; }
void dfs2(int i,int pre)
{
	sub[i]=1;
	for(auto v:ds[i]) if(v.first!=pre&&!ck[v.first])
	{
		dfs2(v.first,i);
		sub[i]+=sub[v.first];
	}
}
void dfs3(int i,int pre,int rt)
{
	L[i]=++tdfs;
	T[rt].vi.push_back({i,tdfs});
	for(auto v:ds[i]) if(v.first!=pre&&!ck[v.first])
	{
		D[v.first]=D[i]+1;
		dfs3(v.first,i,rt);
	}
	T[rt].R[L[i]]=tdfs;
}
int centroid(int i,int pre,int c)
{
	for(auto v:ds[i]) if(v.first!=pre&&!ck[v.first]&&sub[v.first]*2>=c) return centroid(v.first,i,c);
	return i;
}
void decomp(int i,int pre)
{
	dfs2(i,i);
	int pos=centroid(i,i,sub[i]);
	ck[pos]=true,root[pos]=pre,dep[pos]=dep[pre]+1,D[pos]=tdfs=0;
	T[pos].R.resize(sub[i]+1);
	dfs3(pos,pos,pos);
	T[pos].build();
	for(auto v:ds[pos]) if(!ck[v.first]) decomp(v.first,pos);
}
void update(int pos)
{
	int p=pos;
	if(!ck[pos])
	{
		ck[pos]=true,cnt++;
		while(pos) T[pos].update(p,getdis(pos,p)),pos=root[pos];
	}
	else
	{
		ck[pos]=false,cnt--;
		while(pos) T[pos].update(p,INF),pos=root[pos];
	}
}
void update(int u,int v,int w,int n)
{
	if(dis[u]>dis[v]) swap(u,v);
	w-=F[v],F[v]+=w;
	update(L[v],n,w);
	update(R[v]+1,n,-w);
	if(dep[u]>dep[v]) swap(u,v);
	int node=u;
	while(node) T[node].update(u,v,w),node=root[node];
}
long long solve(int pos)
{
	if(!cnt) return -1;
	long long ans=INF;
	int p=pos;
	while(pos) ans=min(ans,T[pos].seg[1]+getdis(pos,p)),pos=root[pos];
	return ans;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n,q;
    cin>>n>>q;
    for(int i=1;i<n;i++)
    {
    	int l,r,v;
    	cin>>l>>r>>v;
    	ds[l].push_back({r,v}),ds[r].push_back({l,v});
	}
	decomp(1,0);
	tdfs=0;
	dfs(1,1);
	for(int i=2;i<=n;i++)
	{
		update(L[i],n,F[i]);
		update(R[i]+1,n,-F[i]);
	}
	for(int i=1;i<=n;i++) ck[i]=false;
	while(q--)
	{
		int t;
		cin>>t;
		if(t==1)
		{
			int p;
			cin>>p;
			cout<<solve(p)<<"\n";
		}
		else if(t==2)
		{
			int p;
			cin>>p;
			update(p);
		}
		else
		{
			int u,v,w;
			cin>>u>>v>>w;
			update(u,v,w,n);
		}
	}
}

• Subtask 1: 6 / 6
• Subtask 2: 14 / 14
• Subtask 3: 15 / 15
• Subtask 4: 15 / 15
• Subtask 5: 18 / 18
• Subtask 6: 32 / 32