oj.uz

Submission #768499

# Submission time Handle Problem Language Result Execution time Memory
768499 2023-06-28T08:09:35 Z parsadox2 LOSTIKS (INOI20_lostiks) C++14
36 / 100
 1269 ms 212232 KB 
#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] << endl;
	return 0;
}

Subtask #1
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 196224 KB Output is correct
2 Correct 64 ms 196268 KB Output is correct
3 Correct 100 ms 210560 KB Output is correct
4 Correct 99 ms 210560 KB Output is correct
5 Correct 132 ms 210556 KB Output is correct
6 Correct 98 ms 210572 KB Output is correct
7 Correct 100 ms 210608 KB Output is correct
8 Correct 100 ms 210576 KB Output is correct
9 Correct 101 ms 210800 KB Output is correct
10 Correct 99 ms 210700 KB Output is correct
11 Correct 96 ms 210672 KB Output is correct
12 Correct 119 ms 212084 KB Output is correct
13 Correct 93 ms 211684 KB Output is correct
14 Correct 95 ms 211212 KB Output is correct
15 Incorrect 97 ms 212232 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #2
36.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 196312 KB Output is correct
2 Correct 66 ms 196336 KB Output is correct
3 Correct 64 ms 196312 KB Output is correct
4 Correct 64 ms 196312 KB Output is correct
5 Correct 79 ms 197268 KB Output is correct
6 Correct 67 ms 197260 KB Output is correct
7 Correct 68 ms 197268 KB Output is correct
8 Correct 70 ms 197272 KB Output is correct
9 Correct 73 ms 197268 KB Output is correct
10 Correct 73 ms 197264 KB Output is correct
11 Correct 72 ms 197236 KB Output is correct
12 Correct 69 ms 197276 KB Output is correct
13 Correct 68 ms 197224 KB Output is correct
14 Correct 70 ms 197240 KB Output is correct
15 Correct 73 ms 197236 KB Output is correct
16 Correct 76 ms 197340 KB Output is correct
17 Correct 78 ms 197300 KB Output is correct
18 Correct 71 ms 197376 KB Output is correct
19 Correct 74 ms 197372 KB Output is correct
20 Correct 70 ms 197472 KB Output is correct
21 Correct 72 ms 197408 KB Output is correct
22 Correct 70 ms 197724 KB Output is correct
23 Correct 71 ms 197764 KB Output is correct
24 Correct 71 ms 197752 KB Output is correct
25 Correct 1269 ms 196344 KB Output is correct

Subtask #3
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 196224 KB Output is correct
2 Correct 64 ms 196268 KB Output is correct
3 Correct 100 ms 210560 KB Output is correct
4 Correct 99 ms 210560 KB Output is correct
5 Correct 132 ms 210556 KB Output is correct
6 Correct 98 ms 210572 KB Output is correct
7 Correct 100 ms 210608 KB Output is correct
8 Correct 100 ms 210576 KB Output is correct
9 Correct 101 ms 210800 KB Output is correct
10 Correct 99 ms 210700 KB Output is correct
11 Correct 96 ms 210672 KB Output is correct
12 Correct 119 ms 212084 KB Output is correct
13 Correct 93 ms 211684 KB Output is correct
14 Correct 95 ms 211212 KB Output is correct
15 Incorrect 97 ms 212232 KB Output isn't correct
16 Halted 0 ms 0 KB -