Submission #914051

#	Time	Username	Problem	Language	Result	Execution time	Memory
914051		Jasiekstrz	LOSTIKS (INOI20_lostiks)	C++17	100 / 100	1823 ms	288468 KiB

Main

#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
const int N=1e6;
const int M=20;
const int INF=1e9+7;
vector<pair<int,int>> e[N+10];
int dep[N+10];
int jmp[N+10][M+2];
int keys[N+10];
int doors[M+10];
int dp[(1<<M)+10][M+2];
int dk[M+2][M+2];
int wh_k[M+2];
int wh_d[M+2];
void find_doors(int x,int p,int msk,int t)
{
	if(x==t)
		doors[M]=msk;
	dep[x]=dep[p]+1;
	jmp[x][0]=p;
	for(int i=1;jmp[x][i-1]!=-0;i++)
		jmp[x][i]=jmp[jmp[x][i-1]][i-1];
	for(int i=0;i<M;i++)
	{
		if(keys[x]&(1<<i))
			doors[i]|=msk;
	}
	for(auto [v,c]:e[x])
	{
		if(v==p)
			continue;
		for(int i=0;i<M;i++)
		{
			if(c&(1<<i))
			{
				wh_d[i]=x;
				doors[i]|=msk;
			}
		}
		find_doors(v,x,msk|c,t);
	}
	return;
}
int dis(int x,int y)
{
	int ans=0;
	if(dep[x]<dep[y])
		swap(x,y);
	for(int i=M;i>=0;i--)
	{
		if(dep[jmp[x][i]]>=dep[y])
		{
			x=jmp[x][i];
			ans+=(1<<i);
		}
	}
	if(x==y)
		return ans;
	for(int i=M;i>=0;i--)
	{
		if(jmp[x][i]!=jmp[y][i])
		{
			x=jmp[x][i];
			y=jmp[y][i];
			ans+=(2<<i);
		}
	}
	return ans+2;
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int n,m=0;
	int s,t;
	int ans=INF;
	cin>>n;
	cin>>s>>t;
	for(int i=1;i<n;i++)
	{
		int a,b,c;
		cin>>a>>b>>c;
		if(c!=0)
		{
			wh_k[m]=c;
			keys[c]|=(1<<m);
			c=(1<<m);
			m++;
		}
		e[a].emplace_back(b,c);
		e[b].emplace_back(a,c);
	}
	find_doors(s,0,0,t);
	wh_k[m]=t;
	wh_d[m]=s;
	for(int i=0;i<=m;i++)
	{
		for(int j=0;j<=m;j++)
			dk[i][j]=dis(wh_d[i],wh_k[j]);
	}
	for(int i=0;i<m;i++)
		dp[0][i]=INF;
	for(int msk=1;msk<(1<<m);msk++)
	{
		for(int i=0;i<=m;i++)
		{
			dp[msk][i]=INF;
			if((msk&(1<<i))==0 || ((msk^(1<<i))|doors[i])!=(msk^(1<<i)))
				continue;
			for(int j=0;j<=m;j++)
				dp[msk][i]=min(dp[msk][i],dp[msk^(1<<i)][j]+dk[j][i]);
			dp[msk][i]+=dk[i][i];
		}
		if((msk|doors[M])==msk)
		{
			for(int i=0;i<=m;i++)
				ans=min(ans,dp[msk][i]+dk[i][m]);
		}
	}
	if(doors[M]==0)
		ans=min(ans,dk[m][m]);
	cout<<(ans==INF ? -1:ans)<<"\n";
	return 0;
}

• Subtask 1: 23 / 23
• Subtask 2: 36 / 36
• Subtask 3: 41 / 41