oj.uz

Submission #783215

# Submission time Handle Problem Language Result Execution time Memory
783215 2023-07-14T18:00:40 Z amirhoseinfar1385 LOSTIKS (INOI20_lostiks) C++17
36 / 100
 911 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 129 ms 142588 KB Output is correct
2 Correct 130 ms 142652 KB Output is correct
3 Correct 183 ms 168192 KB Output is correct
4 Correct 193 ms 168268 KB Output is correct
5 Correct 183 ms 168264 KB Output is correct
6 Correct 182 ms 168252 KB Output is correct
7 Correct 192 ms 168392 KB Output is correct
8 Correct 188 ms 168280 KB Output is correct
9 Correct 184 ms 168456 KB Output is correct
10 Correct 185 ms 168328 KB Output is correct
11 Correct 190 ms 168348 KB Output is correct
12 Correct 179 ms 170176 KB Output is correct
13 Correct 177 ms 169884 KB Output is correct
14 Correct 187 ms 169408 KB Output is correct
15 Runtime error 911 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 135 ms 142556 KB Output is correct
2 Correct 138 ms 142636 KB Output is correct
3 Correct 138 ms 142728 KB Output is correct
4 Correct 144 ms 142764 KB Output is correct
5 Correct 144 ms 145060 KB Output is correct
6 Correct 142 ms 144752 KB Output is correct
7 Correct 141 ms 144464 KB Output is correct
8 Correct 147 ms 144536 KB Output is correct
9 Correct 141 ms 144604 KB Output is correct
10 Correct 220 ms 185420 KB Output is correct
11 Correct 228 ms 185544 KB Output is correct
12 Correct 218 ms 185420 KB Output is correct
13 Correct 220 ms 185420 KB Output is correct
14 Correct 220 ms 185548 KB Output is correct
15 Correct 142 ms 145140 KB Output is correct
16 Correct 141 ms 144568 KB Output is correct
17 Correct 144 ms 144492 KB Output is correct
18 Correct 229 ms 185932 KB Output is correct
19 Correct 226 ms 185780 KB Output is correct
20 Correct 219 ms 185704 KB Output is correct
21 Correct 229 ms 185652 KB Output is correct
22 Correct 219 ms 185932 KB Output is correct
23 Correct 221 ms 185904 KB Output is correct
24 Correct 222 ms 186056 KB Output is correct
25 Correct 138 ms 142616 KB Output is correct

Subtask #3
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 129 ms 142588 KB Output is correct
2 Correct 130 ms 142652 KB Output is correct
3 Correct 183 ms 168192 KB Output is correct
4 Correct 193 ms 168268 KB Output is correct
5 Correct 183 ms 168264 KB Output is correct
6 Correct 182 ms 168252 KB Output is correct
7 Correct 192 ms 168392 KB Output is correct
8 Correct 188 ms 168280 KB Output is correct
9 Correct 184 ms 168456 KB Output is correct
10 Correct 185 ms 168328 KB Output is correct
11 Correct 190 ms 168348 KB Output is correct
12 Correct 179 ms 170176 KB Output is correct
13 Correct 177 ms 169884 KB Output is correct
14 Correct 187 ms 169408 KB Output is correct
15 Runtime error 911 ms 1048576 KB Execution killed with signal 9
16 Halted 0 ms 0 KB -