Submission #768512

#	Time	Username	Problem	Language	Result	Execution time	Memory
768512		parsadox2	LOSTIKS (INOI20_lostiks)	C++14	100 / 100	1238 ms	409264 KiB

Main

#include <bits/stdc++.h>
#define pb 		push_back
#define F		first
#define S 		second
#define debug(x)    cout << #x << "= " << x << ", "
#define ll 		long long
#define fast 		ios::sync_with_stdio(false), cin.tie(0),  cout.tie(0)
#define SZ(x)         (int) x.size()
#define wall 		cout << endl;
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int maxn = 1e6 + 10 , maxm = 21 , inf = 1e9;
int n , key[maxm] , s , t , t_path[maxm] , door[maxm] , par[maxm][maxn] , dis[maxn] , path[maxm][maxm];
int mask[maxn] , dp[maxm][(1 << maxm)] , ps;
struct edge{
	int v , lock;
};

vector <edge> adj[maxn];
void dfs(int v)
{
	for(auto u : adj[v])  if(u.v != par[0][v])
	{
		par[0][u.v] = v;
		dis[u.v] = dis[v] + 1;
		mask[u.v] = mask[v];
		if(u.lock != -1) 
		{
			door[u.lock] = v;
			mask[u.v] |= (1 << u.lock);
		}
		dfs(u.v);
	}
}

int lca(int a , int b)
{
	if(dis[a] < dis[b])  swap(a , b);
	for(int i = 0 ; i < maxm ; i++)  if(((dis[a] - dis[b]) >> i) & 1)  a = par[i][a];
	if(a == b)  return a;
	for(int i = maxm - 1 ; i > -1 ; i--)  if(par[i][a] != par[i][b])
	{
		a = par[i][a];  b = par[i][b];
	}
	return par[0][a];
}

void solve(int v , int msk)
{
	if(dp[v][msk] != -1)  return;
	if(!(mask[t] & msk))
	{
		dp[v][msk] = t_path[v];
		return;
	}
	dp[v][msk] = inf;
	for(int i = 0 ; i < ps ; i++)  if(((msk >> i) & 1))
	{
		int tmask = (mask[key[i]] | mask[door[i]]);
		if(!(tmask & msk))
		{
			solve(i , (msk ^ (1 << i)));
			dp[v][msk] = min(dp[v][msk] , dp[i][(msk ^ (1 << i))] + path[v][i]);
		}
	}
}

int32_t main()
{
	fast;
	cin >> n;
	cin >> s >> t;
	for(int i = 0 ; i < n - 1 ; i++)
	{
		int v , u , w;  cin >> v >> u >> w;
		int tmp = -1;
		if(w != 0)
		{
			tmp = ps;
			key[ps] = w;
			ps++;
		}
		adj[v].pb({u , tmp});  adj[u].pb({v , tmp});
	}
	door[ps] = s;
	dfs(s);
	for(int i = 1 ; i < maxm ; i++)
		for(int j = 1 ; j <= n ; j++)
			par[i][j] = par[i - 1][par[i - 1][j]];
	for(int i = 0 ; i <= ps ; i++)  for(int j = 0 ; j < ps ; j++)  if(i != j)
	{
		path[i][j] = dis[door[i]] + dis[key[j]] + dis[key[j]] + dis[door[j]];
		int l1 = lca(door[i] , key[j]) , l2 = lca(door[j] , key[j]);
		path[i][j] -= (dis[l1] + dis[l2] + dis[l2] + dis[l1]);
	}
	for(int i = 0 ; i <= ps ; i++)
	{
		int l = lca(t , door[i]);  t_path[i] = dis[door[i]] + dis[t] - dis[l] - dis[l];
	}
	memset(dp , -1 , sizeof dp);
	solve(ps , (1 << ps) - 1);
	cout << (dp[ps][(1 << ps) - 1] == inf ? -1 : dp[ps][(1 << ps) - 1]) << endl;
	return 0;
}

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