Submission #935527

#	Time	Username	Problem	Language	Result	Execution time	Memory
935527		PM1	LOSTIKS (INOI20_lostiks)	C++17	0 / 100	203 ms	52716 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];
vector<pair<int,int>>g[mxn];
void dfs(int z ,int ww=0){
	if(t==z || ww)marky[z]=1,key[z]=ww;
	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]=1;
			bl[i.fr][0]=z;
			d[i.fr]=d[z]+1;
			dfs(i.fr,i.sc);
		}
	}
}
void pre(int z,int ww=0){
	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]=1;
			bl[i.fr][0]=z;
			d[i.fr]=d[z]+1;
			pre(i.fr,i.sc);
		}
	}
}
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++){
		int x,y,w;
		cin>>x>>y>>w;
		g[x].push_back({y,w});
		g[y].push_back({x,w});
	}
	dfs(s);
	int now=s,ans=0;
	while(now!=t){
		pre(s);
		int x=tiz[t];
		if(!marky[x]){
			ans+=lca(t,now);
			break;
		}
		int y=tiz[key[x]];
		while(marky[y]){
			x=y;
			y=tiz[key[x]];
		}

		ans+=lca(now,key[x])+lca(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