Submission #1111338

#	Time	Username	Problem	Language	Result	Execution time	Memory
1111338		boclobanchat	Grapevine (NOI22_grapevine)	C++14	100 / 100	2033 ms	182724 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define ii pair<int,int>
#define fi first
#define se second
const int MAXN=1e5+5;
const int sqr=320;
const long long INF=1e18;
const long long RNG=1e16;
vector<int> ds[MAXN];
vector<ii> init[MAXN];
int sub[MAXN],root[MAXN],L[MAXN],R[MAXN],dis[MAXN],dep[MAXN],sp[MAXN][20],tdfsus=0;
long long dp[MAXN],block[MAXN],P[MAXN];
bool ck[MAXN],dd[MAXN];
struct tree
{
	vector<long long> seg,lazy;
	vector<int> D;
	vector<ii> vi,range;
	int tdfs,n;
	void build(int cnt) { n=cnt,tdfs=0,seg.resize(n*4+2),lazy.resize(n*4+2),range.resize(n+2),D.resize(n+2); }
	void sortt() { sort(vi.begin(),vi.end()); }
	int findpos(int val) { return vi[lower_bound(vi.begin(),vi.end(),(ii){val,0})-vi.begin()].se; }
	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 u,int v,long long val,int pos)
	{
		if(u<=l&&r<=v)
		{
			seg[pos]+=val,lazy[pos]+=val;
			return ;
		}
		int mid=(l+r)/2;
		down(pos);
		if(v<=mid) update(l,mid,u,v,val,pos*2);
		else if(mid+1<=u) update(mid+1,r,u,v,val,pos*2+1);
		else
		{
			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 updnode(int i,long long val)
	{
		int pos=findpos(i);
		update(1,n,range[pos].fi,range[pos].fi,val,1);
	}
	void updpath(int l,int r,long long val)
	{
		l=findpos(l),r=findpos(r);
		if(D[l]>D[r]) swap(l,r);
		update(1,n,range[r].fi,range[r].se,val,1);
	}
	void dfs(int i,int pre,int pp)
	{
		tdfs++,vi.push_back({i,tdfs});
		int a=tdfs;
		if(pp) D[a]=D[pp]+1;
		range[a].fi=tdfs;
		for(auto v:ds[i]) if(v!=pre&&!ck[v]) dfs(v,i,a);
		range[a].se=tdfs;
	}
};
tree T[MAXN];
int getlog(long long n) { return 63-__builtin_clzll(n); }
void precalc(int i,int pre)
{
	for(auto v:init[i]) if(v.fi!=pre)
	{
		P[v.fi]=v.se,ds[v.fi].push_back(i),ds[i].push_back(v.fi);
		precalc(v.fi,i);
	}
}
void dfs(int i,int pre)
{
	L[i]=++tdfsus,sp[i][0]=pre;
	for(int j=1;j<=18;j++) sp[i][j]=sp[sp[i][j-1]][j-1];
	for(auto v:ds[i]) if(v!=pre)
	{
		dis[v]=dis[i]+1;
		dfs(v,i);
	}
	R[i]=tdfsus;
}
int lca(int a,int b)
{
	int x=dis[a],y=dis[b],m=min(x,y);
	for(int i=18;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=18;i+1;i--) if(sp[a][i]!=sp[b][i]) a=sp[a][i],b=sp[b][i];
	return sp[a][0];
}
void upddis(int i,long long val)
{
	int l=L[i],r=R[i],bl=l/sqr,br=r/sqr;
	if(bl==br) for(int j=l;j<=r;j++) dp[j]+=val;
	else
	{
		for(int j=l;j<(bl+1)*sqr;j++) dp[j]+=val;
		for(int j=br*sqr;j<=r;j++) dp[j]+=val;
		for(int j=bl+1;j<br;j++) block[j]+=val;
	}
}
long long dist(int a) { return dp[L[a]]+block[L[a]/sqr]; }
long long getdis(int a,int b) { return dist(a)+dist(b)-dist(lca(a,b))*2; }
void dfsus(int i,int pre)
{
	sub[i]=1;
	for(auto v:ds[i]) if(v!=pre&&!ck[v])
	{
		dfsus(v,i);
		sub[i]+=sub[v];
	}
}
int centroid(int i,int pre,int c)
{
	for(auto v:ds[i]) if(v!=pre&&!ck[v]&&sub[v]*2>c) return centroid(v,i,c);
	return i;
}
void CD(int i,int pre)
{
	dfsus(i,i);
	int pos=centroid(i,i,sub[i]);
	ck[pos]=true,T[pos].build(sub[i]),T[pos].dfs(pos,pos,0),T[pos].sortt(),T[pos].seg[1]=T[pos].lazy[1]=INF;
	if(pre) root[pos]=pre,dep[pos]=dep[pre]+1;
	for(auto v:ds[pos]) if(!ck[v]) CD(v,pos);
}
long long query1(int node)
{
	long long ans=INF,pos=node;
	while(node) ans=min(ans,getdis(node,pos)+T[node].seg[1]),node=root[node];
	return ans;
}
void query2(int node)
{
	int pos=node;
	if(!dd[node])
	{
		dd[node]=true;
		while(node) T[node].updnode(pos,-INF),node=root[node];
	}
	else
	{
		dd[node]=false;
		while(node) T[node].updnode(pos,INF),node=root[node];
	}
}
void query3(int l,int r,long long val)
{
	if(dep[l]<dep[r]) swap(l,r);
	int node=r;
	while(node) T[node].updpath(l,r,val),node=root[node];
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n,q,pre=1;
    cin>>n>>q;
    for(int i=1;i<n;i++)
    {
    	int l,r,v;
    	cin>>l>>r>>v;
    	init[l].push_back({r,v}),init[r].push_back({l,v});
	}
	precalc(1,1);
	dfs(1,1);
	CD(1,0);
	for(int i=2;i<=n;i++) query3(sp[i][0],i,P[i]),upddis(i,P[i]);
	while(q--)
	{
		int t;
		cin>>t;
		if(t==1)
		{
			int p;
			cin>>p;
			long long ans=query1(p);
			if(ans>=RNG) cout<<"-1\n";
			else cout<<ans<<"\n";
		}
		else if(t==2)
		{
			int p;
			cin>>p;
			query2(p);
		}
		else
		{
			long long l,r,val;
			cin>>l>>r>>val;
			if(dis[l]<dis[r]) swap(l,r);
			query3(r,l,val-P[l]);
			upddis(l,val-P[l]);
			P[l]=val;
		}
	}
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:169:13: warning: unused variable 'pre' [-Wunused-variable]
  169 |     int n,q,pre=1;
      |             ^~~

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