Submission #806780

#	Time	Username	Problem	Language	Result	Execution time	Memory
806780		ashcomp	LOSTIKS (INOI20_lostiks)	C++14	100 / 100	1404 ms	518304 KiB

Main

#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;
}
 
inline 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))];
			}
		}
	}
}
 
inline 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];
}
 
inline 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: 23 / 23
• Subtask 2: 36 / 36
• Subtask 3: 41 / 41