oj.uz

Submission #783217

# Submission time Handle Problem Language Result Execution time Memory
783217 2023-07-14T18:05:53 Z amirhoseinfar1385 LOSTIKS (INOI20_lostiks) C++14
36 / 100
 778 ms 1048576 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,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 ;
	}
	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 130 ms 142620 KB Output is correct
2 Correct 131 ms 142580 KB Output is correct
3 Correct 190 ms 168272 KB Output is correct
4 Correct 185 ms 168208 KB Output is correct
5 Correct 184 ms 168272 KB Output is correct
6 Correct 194 ms 168184 KB Output is correct
7 Correct 184 ms 168312 KB Output is correct
8 Correct 185 ms 168288 KB Output is correct
9 Correct 185 ms 168572 KB Output is correct
10 Correct 206 ms 168352 KB Output is correct
11 Correct 210 ms 168348 KB Output is correct
12 Correct 186 ms 170200 KB Output is correct
13 Correct 192 ms 169824 KB Output is correct
14 Correct 182 ms 169476 KB Output is correct
15 Runtime error 778 ms 1048576 KB Execution killed with signal 9
16 Halted 0 ms 0 KB -

Subtask #2
36.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 144 ms 142656 KB Output is correct
2 Correct 150 ms 142560 KB Output is correct
3 Correct 140 ms 142572 KB Output is correct
4 Correct 136 ms 142776 KB Output is correct
5 Correct 147 ms 145124 KB Output is correct
6 Correct 144 ms 144736 KB Output is correct
7 Correct 162 ms 144420 KB Output is correct
8 Correct 142 ms 144380 KB Output is correct
9 Correct 135 ms 144488 KB Output is correct
10 Correct 234 ms 185540 KB Output is correct
11 Correct 226 ms 185456 KB Output is correct
12 Correct 234 ms 185512 KB Output is correct
13 Correct 226 ms 185456 KB Output is correct
14 Correct 225 ms 185460 KB Output is correct
15 Correct 143 ms 145164 KB Output is correct
16 Correct 143 ms 144572 KB Output is correct
17 Correct 145 ms 144432 KB Output is correct
18 Correct 214 ms 185672 KB Output is correct
19 Correct 223 ms 185668 KB Output is correct
20 Correct 332 ms 185600 KB Output is correct
21 Correct 226 ms 185744 KB Output is correct
22 Correct 213 ms 185952 KB Output is correct
23 Correct 219 ms 186040 KB Output is correct
24 Correct 209 ms 185976 KB Output is correct
25 Correct 138 ms 142604 KB Output is correct

Subtask #3
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 130 ms 142620 KB Output is correct
2 Correct 131 ms 142580 KB Output is correct
3 Correct 190 ms 168272 KB Output is correct
4 Correct 185 ms 168208 KB Output is correct
5 Correct 184 ms 168272 KB Output is correct
6 Correct 194 ms 168184 KB Output is correct
7 Correct 184 ms 168312 KB Output is correct
8 Correct 185 ms 168288 KB Output is correct
9 Correct 185 ms 168572 KB Output is correct
10 Correct 206 ms 168352 KB Output is correct
11 Correct 210 ms 168348 KB Output is correct
12 Correct 186 ms 170200 KB Output is correct
13 Correct 192 ms 169824 KB Output is correct
14 Correct 182 ms 169476 KB Output is correct
15 Runtime error 778 ms 1048576 KB Execution killed with signal 9
16 Halted 0 ms 0 KB -