oj.uz

Submission #782048

# Submission time Handle Problem Language Result Execution time Memory
782048 2023-07-13T15:06:00 Z amirhoseinfar1385 LOSTIKS (INOI20_lostiks) C++17
0 / 100
 71 ms 41600 KB 
#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);
long long solve1(int u){
	if(vis[u]==1){
		return 0;
	}
	long long ret=solve1(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,alled[par[u]].getad(u));
		last=alled[par[u]].getad(u);
	}
	vis[u]=1;
	//cout<<u<<" dsa "<<ret<<" "<<last<<"\n";
//	cout<<u<<" "<<ret<<"\n";
	return ret;
}

long long solve(int u){
	if(vis[u]==1){
		long long ret=dis(last,u);
		last=u;
		//cout<<"man1: "<<u<<" "<<ret<<"\n";
		return ret;
	}
	long long ret=solve1(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);
	//cout<<u<<" asd "<<ret<<" "<<last<<"\n";
	last=u;
	vis[u]=1;
	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.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 24004 KB Output is correct
2 Correct 14 ms 23892 KB Output is correct
3 Correct 71 ms 39312 KB Output is correct
4 Correct 50 ms 39968 KB Output is correct
5 Correct 50 ms 40076 KB Output is correct
6 Correct 50 ms 40012 KB Output is correct
7 Correct 53 ms 40156 KB Output is correct
8 Correct 65 ms 40112 KB Output is correct
9 Correct 51 ms 40288 KB Output is correct
10 Correct 50 ms 40140 KB Output is correct
11 Correct 63 ms 40136 KB Output is correct
12 Correct 65 ms 41600 KB Output is correct
13 Incorrect 62 ms 41196 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #2
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23892 KB Output is correct
2 Correct 11 ms 23944 KB Output is correct
3 Incorrect 12 ms 23932 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 24004 KB Output is correct
2 Correct 14 ms 23892 KB Output is correct
3 Correct 71 ms 39312 KB Output is correct
4 Correct 50 ms 39968 KB Output is correct
5 Correct 50 ms 40076 KB Output is correct
6 Correct 50 ms 40012 KB Output is correct
7 Correct 53 ms 40156 KB Output is correct
8 Correct 65 ms 40112 KB Output is correct
9 Correct 51 ms 40288 KB Output is correct
10 Correct 50 ms 40140 KB Output is correct
11 Correct 63 ms 40136 KB Output is correct
12 Correct 65 ms 41600 KB Output is correct
13 Incorrect 62 ms 41196 KB Output isn't correct
14 Halted 0 ms 0 KB -