oj.uz

Submission #783219

# Submission time Handle Problem Language Result Execution time Memory
783219 2023-07-14T18:10:23 Z amirhoseinfar1385 LOSTIKS (INOI20_lostiks) C++14
36 / 100
 233 ms 186004 KB 
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+10,lg=21;
struct yal{
	int u,v,w;
	int getad(int fu){
		int ret=(u^v^fu);
		return ret;
	}
};
yal alled[maxn];
vector<int>adj[maxn];
int n,m,visa[maxn],lca[lg][maxn*2],wtf[2*maxn],ghabl[maxn],vis[maxn],high[maxn],timea,para[maxn],s,t;
pair<int,int>stf[maxn];
int dp[(1<<20)][20];
vector<int>allind[(1<<20)];
vector<int>allv;
vector<int>z;
 
void aval(){
	for(int i=1;i<(1<<20);i++)
	{
		int j=0;
		for(;;j++){
			if((i>>j)&1){
				break;
			}
		}
		allind[i]=allind[i^(1<<j)];
		allind[i].push_back(j);
	}
	int ha=-1;
	for(int i=1;i<2*maxn;i++){
		if(__builtin_popcount(i)==1){
			ha++;
		}
		wtf[i]=ha;
	}
}
 
void dfs(int u,int par=0){
	high[u]=high[par]+1;
	z.push_back(u);
	stf[u].first=(int)z.size()-1;
	for(auto x:adj[u]){
		int v=alled[x].getad(u);
		if(v!=par){
			if(v!=alled[x].v){
				swap(alled[x].u,alled[x].v);
			}
			para[v]=x;
			dfs(v,u);
			z.push_back(u);
		}
	}
	stf[u].second=(int)z.size()-1;
}
 
void callca(){
	for(int i=0;i<lg;i++){
		for(int j=0;j<(int)z.size();j++){
			if(i==0){
				lca[i][j]=z[j];
				continue;
			}
			if(high[lca[i-1][j]]<high[lca[i-1][j+(1<<(i-1))]]){
				lca[i][j]=lca[i-1][j];
			}
			else{
				lca[i][j]=lca[i-1][j+(1<<(i-1))];
			}
		}
	}
}
 
int getlca(int u,int v){
	int fu=min(stf[u].first,stf[v].first);
	int fv=max(stf[u].first,stf[v].first);
	u=fu;
	v=fv;
	int len=v-u+1;
	int te=wtf[len];
	if(high[lca[te][u]]<high[lca[te][v-(1<<te)+1]]){
		return lca[te][u];
	}
	return lca[te][v-(1<<te)+1];
}
 
int dis(int u,int v){
	int uv=getlca(u,v);
	int ret=high[u]+high[v]-2*high[uv];
	return ret;
}
 
void solve(int u){
	//cout<<u<<endl;
	if(vis[u]==1){
		return ;
	}
	if(visa[u]==1){
		cout<<1<<"\n";
		exit(0);
	}
	visa[u]=1;
	solve(alled[para[u]].getad(u));
	if(alled[para[u]].w!=0){
		allv.push_back(para[u]);
		solve(alled[para[u]].w);
	}
	vis[u]=1;
	return ;
}
 
void calghabl(int u,int par=0){
	ghabl[u]+=ghabl[par];
	for(auto x:adj[u]){
		int v=alled[x].getad(u);
		if(v!=par){
			calghabl(v,u);
		}
	}
}
 
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	aval();
	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();
	vis[s]=1;
	solve(t);
	m=allv.size();
	for(int i=0;i<m;i++){
		ghabl[alled[allv[i]].v]+=(1<<i);
	}
	calghabl(s);
	for(int i=1;i<(int)(1<<m);i++){
		for(auto x:allind[i]){
			int fake=1e9;
			if((ghabl[alled[allv[x]].u]&i)!=ghabl[alled[allv[x]].u]||(ghabl[alled[allv[x]].w]&i)!=ghabl[alled[allv[x]].w]){
				dp[i][x]=fake;
				continue;
			}
			if(__builtin_popcount(i)==1){
				dp[i][x]=dis(alled[allv[x]].u,alled[allv[x]].w)+dis(alled[allv[x]].w,s);
				continue;
			}
			for(auto y:allind[i^(1<<x)]){
				fake=min(fake,dis(alled[allv[y]].u,alled[allv[x]].w)+dis(alled[allv[x]].u,alled[allv[x]].w)+dp[(1<<x)^i][y]);
			}
			dp[i][x]=fake;
		}
	}
	if(m==0){
		int res=dis(s,t);
		cout<<res<<"\n";
		return 0;
	}
	else{
		int res=1e9;
		for(auto x:allind[(1<<m)-1]){
			res=min(res,dp[(1<<m)-1][x]+dis(alled[allv[x]].u,t));
		}
		cout<<res<<"\n";
	}
}

Subtask #1
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 127 ms 142608 KB Output is correct
2 Correct 128 ms 142580 KB Output is correct
3 Correct 182 ms 168180 KB Output is correct
4 Correct 180 ms 168128 KB Output is correct
5 Correct 184 ms 168200 KB Output is correct
6 Correct 212 ms 168180 KB Output is correct
7 Correct 180 ms 168264 KB Output is correct
8 Correct 183 ms 168312 KB Output is correct
9 Correct 182 ms 168412 KB Output is correct
10 Correct 196 ms 168236 KB Output is correct
11 Correct 182 ms 168264 KB Output is correct
12 Correct 175 ms 170108 KB Output is correct
13 Correct 179 ms 169780 KB Output is correct
14 Correct 194 ms 169372 KB Output is correct
15 Incorrect 172 ms 170432 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #2
36.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 128 ms 142664 KB Output is correct
2 Correct 128 ms 142552 KB Output is correct
3 Correct 128 ms 142656 KB Output is correct
4 Correct 135 ms 142744 KB Output is correct
5 Correct 135 ms 145004 KB Output is correct
6 Correct 131 ms 144736 KB Output is correct
7 Correct 146 ms 144448 KB Output is correct
8 Correct 132 ms 144332 KB Output is correct
9 Correct 130 ms 144424 KB Output is correct
10 Correct 205 ms 185420 KB Output is correct
11 Correct 221 ms 185420 KB Output is correct
12 Correct 205 ms 185436 KB Output is correct
13 Correct 222 ms 185388 KB Output is correct
14 Correct 208 ms 185496 KB Output is correct
15 Correct 134 ms 145204 KB Output is correct
16 Correct 131 ms 144516 KB Output is correct
17 Correct 133 ms 144420 KB Output is correct
18 Correct 205 ms 185604 KB Output is correct
19 Correct 208 ms 185752 KB Output is correct
20 Correct 233 ms 185616 KB Output is correct
21 Correct 203 ms 185712 KB Output is correct
22 Correct 209 ms 186004 KB Output is correct
23 Correct 207 ms 185864 KB Output is correct
24 Correct 203 ms 185920 KB Output is correct
25 Correct 154 ms 142556 KB Output is correct

Subtask #3
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 127 ms 142608 KB Output is correct
2 Correct 128 ms 142580 KB Output is correct
3 Correct 182 ms 168180 KB Output is correct
4 Correct 180 ms 168128 KB Output is correct
5 Correct 184 ms 168200 KB Output is correct
6 Correct 212 ms 168180 KB Output is correct
7 Correct 180 ms 168264 KB Output is correct
8 Correct 183 ms 168312 KB Output is correct
9 Correct 182 ms 168412 KB Output is correct
10 Correct 196 ms 168236 KB Output is correct
11 Correct 182 ms 168264 KB Output is correct
12 Correct 175 ms 170108 KB Output is correct
13 Correct 179 ms 169780 KB Output is correct
14 Correct 194 ms 169372 KB Output is correct
15 Incorrect 172 ms 170432 KB Output isn't correct
16 Halted 0 ms 0 KB -