Submission #782006

#	Time	Username	Problem	Language	Result	Execution time	Memory
782006		amirhoseinfar1385	LOSTIKS (INOI20_lostiks)	C++17	0 / 100	62 ms	40048 KiB

Main

#include<bits/stdc++.h>
using namespace std;
struct yal{
	int u,v,w;
	int getad(int fu){
		int ret=(u^v^fu);
		return ret;
	}
};
const int maxn=1000000+10,lg=21;
yal alled[maxn];
vector<int>adj[maxn];
int vis[maxn],n,s,t;
int lca[lg][maxn],par[maxn],high[maxn],timea=0;
pair<int,int>stf[maxn];

void dfs(int u,int para=0){
	lca[0][u]=para;
	timea++;
	stf[u].first=timea;
	high[u]=high[para]+1;
	for(auto x:adj[u]){
		int v=alled[x].getad(u);
		if(v!=para){
			par[v]=x;
			dfs(v,u);
		}
	}
	stf[u].second=timea;
}

void callca(){
	for(int i=1;i<lg;i++){
		for(int j=1;j<=n;j++){
			lca[i][j]=lca[i-1][lca[i-1][j]];
		}
	}
}
int last=0;

int zird(int u,int v){
	if(stf[v].first<=stf[u].first&&stf[v].second>=stf[u].second){
		return 1;
	}
	return 0;
}

int getlca(int u,int v){
	if(zird(u,v)){
		return v;
	}
	if(zird(v,u)){
		return u;
	}
	for(int i=lg-1;i>=0;i--){
		if(lca[i][u]!=0&&zird(v,lca[i][u])==0){
			u=lca[i][u];
		}
	}
	u=lca[0][u];
	return u;
}

long long dis(int u,int v){
	int uv=getlca(u,v);
	int ret=high[u]+high[v]-2*high[uv];
	return ret;
}

long long solve(int u){
	if(vis[u]==1){
		return 0;
	}

	long long ret=solve(alled[par[u]].getad(u));
	//cout<<u<<" "<<par[u]<<" "<<alled[par[u]].w<<"\n";
	if(alled[par[u]].w!=0){
		ret+=solve(alled[par[u]].w);
	}
	ret+=dis(last,u);
	last=u;
	vis[u]=1;
//	cout<<u<<" "<<ret<<"\n";
	return ret;
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n;
	cin>>s>>t;
	for(int i=0;i<n-1;i++){
		cin>>alled[i].u>>alled[i].v>>alled[i].w;
		adj[alled[i].u].push_back(i);
		adj[alled[i].v].push_back(i);
	}
	dfs(s);
	callca();
	last=s;
	vis[s]=1;
	cout<<solve(t)<<"\n";
}

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