oj.uz

Submission #782386

# Submission time Handle Problem Language Result Execution time Memory
782386 2023-07-13T22:43:37 Z amirhoseinfar1385 LOSTIKS (INOI20_lostiks) C++17
36 / 100
 769 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<2*n;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){
	//cout<<"vo: "<<u<<" "<<v<<"\n";
	int fu=min(stf[u].first,stf[v].first);
	int fv=max(stf[u].first,stf[v].first);
	u=fu;
	v=fv;
	//u=stf[u].second,v=stf[v].first;
	int len=v-u+1;
	int te=wtf[len];
	//cout<<"magedarin "<<u<<" "<<v<<" "<<te<<"\n";
	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);
	//cout<<"eytof "<<u<<" "<<v<<" "<<uv<<"\n";
	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;
	//cout<<"salam"<<endl;
	solve(t);
	//cout<<"salam"<<endl;
	m=allv.size();
	for(int i=0;i<m;i++){
		ghabl[alled[allv[i]].v]+=(1<<i);
	}
	calghabl(s);
	//cout<<"salam"<<endl;
	for(int i=1;i<(int)(1<<m);i++){
		for(auto x:allind[i]){
			int fake=1e9;
		//	cout<<i<<" "<<x<<" "<<ghabl[alled[allv[x]].u]<<" "<<ghabl[alled[allv[x]].w]<<" "<<alled[allv[x]].u<<" "<<alled[allv[x]].w<<"\n";
			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);
		//		cout<<i<<" "<<x<<" "<<dp[i][x]<<" "<<alled[allv[x]].u<<" "<<alled[allv[x]].w<<"\n";
				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]);
			}
		//	cout<<"wtf: "<<i<<" "<<x<<" "<<fake<<"\n";
			dp[i][x]=fake;
		}
	}
	if(m==0){
		int res=dis(s,t);
		cout<<res<<"\n";
		return 0;
	}
	else{
	//	cout<<m<<":\n";
	//	for(auto x:allv){
	//		cout<<x<<" ";
	//	}
	//	cout<<"\n";
		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 142652 KB Output is correct
2 Correct 127 ms 142568 KB Output is correct
3 Correct 180 ms 168240 KB Output is correct
4 Correct 198 ms 168320 KB Output is correct
5 Correct 180 ms 168208 KB Output is correct
6 Correct 182 ms 168192 KB Output is correct
7 Correct 186 ms 168368 KB Output is correct
8 Correct 184 ms 168272 KB Output is correct
9 Correct 180 ms 168492 KB Output is correct
10 Correct 180 ms 168292 KB Output is correct
11 Correct 179 ms 168260 KB Output is correct
12 Correct 179 ms 170244 KB Output is correct
13 Correct 177 ms 169824 KB Output is correct
14 Correct 179 ms 169588 KB Output is correct
15 Runtime error 769 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 131 ms 142532 KB Output is correct
2 Correct 129 ms 142652 KB Output is correct
3 Correct 128 ms 142600 KB Output is correct
4 Correct 128 ms 142684 KB Output is correct
5 Correct 139 ms 145176 KB Output is correct
6 Correct 131 ms 144720 KB Output is correct
7 Correct 131 ms 144384 KB Output is correct
8 Correct 128 ms 144384 KB Output is correct
9 Correct 137 ms 144504 KB Output is correct
10 Correct 203 ms 185500 KB Output is correct
11 Correct 202 ms 185544 KB Output is correct
12 Correct 206 ms 185420 KB Output is correct
13 Correct 204 ms 185472 KB Output is correct
14 Correct 205 ms 185548 KB Output is correct
15 Correct 134 ms 145068 KB Output is correct
16 Correct 130 ms 144460 KB Output is correct
17 Correct 131 ms 144464 KB Output is correct
18 Correct 202 ms 185680 KB Output is correct
19 Correct 208 ms 185788 KB Output is correct
20 Correct 202 ms 185628 KB Output is correct
21 Correct 204 ms 185676 KB Output is correct
22 Correct 203 ms 185944 KB Output is correct
23 Correct 205 ms 185932 KB Output is correct
24 Correct 202 ms 185980 KB Output is correct
25 Correct 125 ms 142568 KB Output is correct

Subtask #3
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 127 ms 142652 KB Output is correct
2 Correct 127 ms 142568 KB Output is correct
3 Correct 180 ms 168240 KB Output is correct
4 Correct 198 ms 168320 KB Output is correct
5 Correct 180 ms 168208 KB Output is correct
6 Correct 182 ms 168192 KB Output is correct
7 Correct 186 ms 168368 KB Output is correct
8 Correct 184 ms 168272 KB Output is correct
9 Correct 180 ms 168492 KB Output is correct
10 Correct 180 ms 168292 KB Output is correct
11 Correct 179 ms 168260 KB Output is correct
12 Correct 179 ms 170244 KB Output is correct
13 Correct 177 ms 169824 KB Output is correct
14 Correct 179 ms 169588 KB Output is correct
15 Runtime error 769 ms 1048576 KB Execution killed with signal 9
16 Halted 0 ms 0 KB -