Submission #935478

#	Time	Username	Problem	Language	Result	Execution time	Memory
935478		PM1	LOSTIKS (INOI20_lostiks)	C++17	0 / 100	62 ms	67316 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define fr first
#define sc second
const int mxn=1e6+5;
int n,m,s,t,par[mxn],cnt=0,mark[mxn],dis[mxn],comp[mxn],key[mxn],d[mxn],bl[mxn][20],res[mxn][20],tiz[mxn];
bool marky[mxn];
struct yall{
	int u,uu,w;
}yal[mxn];
vector<int>v[mxn];
vector<pair<int,int>>g[mxn];
void dfs(int z,int ww=0){
	if(mark[z] || ww)comp[z]=++cnt,key[comp[z]]=ww,mark[cnt]=1;
	if(ww  || z==t)marky[cnt]=1;
	for(auto j:v[z]){
		int i=yal[j].u^yal[j].uu^z;
		if(par[z]!=i){
			par[i]=z;
			dfs(i,yal[j].w);
			mark[z]+=mark[i];
			dis[comp[i]]++;
		}
	}
	if(comp[z]==0 && mark[z]>=2)comp[z]=++cnt;
	for(auto j:v[z]){
		int i=yal[j].u^yal[j].uu^z;
		if(par[z]!=i){
			if(mark[z]>1 && mark[i]){
				g[comp[z]].push_back({comp[i],dis[comp[i]]});
			}
		}
	}
	if(mark[z]>1)mark[z]=1;


}
void pre(int z){
	if(marky[z] && !tiz[z])tiz[z]=z;
	for(int i=1;i<20;i++){
		bl[z][i]=bl[bl[z][i-1]][i-1];
		res[z][i]=res[z][i-1]+res[bl[z][i-1]][i-1];
	}
	for(auto i:g[z]){
		if(bl[z][0]!=i.fr){
			tiz[i.fr]=tiz[z];
			res[i.fr][0]=i.sc;
			bl[i.fr][0]=z;
			d[i.fr]=d[z]+1;
			pre(i.fr);
		}
	}
}
int lca(int x,int y){
	int num=0;
	if(d[x]<d[y])swap(x,y);
	for(int i=19;i>=0;i--){
		if((1<<i)<=d[x]-d[y]){
			num+=res[x][i];
			x=bl[x][i];
		}
	}
	if(x==y)return num;

	for(int i=19;i>=0;i--){
		if(bl[x][i]!=bl[y][i]){
			num+=res[x][i]+res[y][i];
			x=bl[x][i];
			y=bl[y][i];
		}
	}
	return num+res[x][0]+res[y][0];
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>s>>t;
	for(int i=1;i<n;i++){
		cin>>yal[i].u>>yal[i].uu>>yal[i].w;
		mark[yal[i].w]=1;
		v[yal[i].u].push_back(i);
		v[yal[i].uu].push_back(i);
	}
	mark[s]=mark[t]=1;
	dfs(s);
	lca(5,3);
	pre(comp[s]);
	int now=comp[s],ans=0;
	while(now!=comp[t]){
		pre(comp[s]);
		int x=tiz[comp[t]];
		if(!marky[x]){
			ans+=lca(t,now);
			break;
		}
		int y=tiz[comp[key[x]]];
		while(marky[y]){
			x=y;
			y=tiz[comp[key[x]]];
		}

		ans+=lca(now,comp[key[x]])+lca(comp[key[x]],x)-1;
		now=bl[x][0];
		marky[x]=0;
	}
	cout<<ans;
	return 0;
}

• Subtask 1: 0 / 23
• Subtask 2: 0 / 36
• Subtask 3: 0 / 41