oj.uz

Submission #768509

# Submission time Handle Problem Language Result Execution time Memory
768509 2023-06-28T08:16:25 Z parsadox2 LOSTIKS (INOI20_lostiks) C++14
36 / 100
 1539 ms 394652 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());
#define int long long
const int maxn = 1e6 + 10 , maxm = 21 , inf = 1e18;
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 127 ms 368740 KB Output is correct
2 Correct 122 ms 368680 KB Output is correct
3 Correct 174 ms 393232 KB Output is correct
4 Correct 165 ms 393312 KB Output is correct
5 Correct 157 ms 393304 KB Output is correct
6 Correct 175 ms 393276 KB Output is correct
7 Correct 156 ms 393472 KB Output is correct
8 Correct 153 ms 393392 KB Output is correct
9 Correct 155 ms 393568 KB Output is correct
10 Correct 154 ms 393348 KB Output is correct
11 Correct 154 ms 393352 KB Output is correct
12 Correct 152 ms 394508 KB Output is correct
13 Correct 159 ms 394256 KB Output is correct
14 Correct 158 ms 393936 KB Output is correct
15 Incorrect 154 ms 394652 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 116 ms 368612 KB Output is correct
2 Correct 115 ms 368616 KB Output is correct
3 Correct 118 ms 368716 KB Output is correct
4 Correct 118 ms 368716 KB Output is correct
5 Correct 120 ms 370380 KB Output is correct
6 Correct 118 ms 370316 KB Output is correct
7 Correct 122 ms 370300 KB Output is correct
8 Correct 118 ms 370344 KB Output is correct
9 Correct 119 ms 370428 KB Output is correct
10 Correct 118 ms 370424 KB Output is correct
11 Correct 118 ms 370396 KB Output is correct
12 Correct 121 ms 370420 KB Output is correct
13 Correct 117 ms 370388 KB Output is correct
14 Correct 117 ms 370352 KB Output is correct
15 Correct 116 ms 370392 KB Output is correct
16 Correct 118 ms 370412 KB Output is correct
17 Correct 121 ms 370324 KB Output is correct
18 Correct 132 ms 370468 KB Output is correct
19 Correct 118 ms 370476 KB Output is correct
20 Correct 118 ms 370428 KB Output is correct
21 Correct 131 ms 370536 KB Output is correct
22 Correct 120 ms 370812 KB Output is correct
23 Correct 119 ms 370720 KB Output is correct
24 Correct 116 ms 370748 KB Output is correct
25 Correct 1539 ms 368724 KB Output is correct

Subtask #3
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 127 ms 368740 KB Output is correct
2 Correct 122 ms 368680 KB Output is correct
3 Correct 174 ms 393232 KB Output is correct
4 Correct 165 ms 393312 KB Output is correct
5 Correct 157 ms 393304 KB Output is correct
6 Correct 175 ms 393276 KB Output is correct
7 Correct 156 ms 393472 KB Output is correct
8 Correct 153 ms 393392 KB Output is correct
9 Correct 155 ms 393568 KB Output is correct
10 Correct 154 ms 393348 KB Output is correct
11 Correct 154 ms 393352 KB Output is correct
12 Correct 152 ms 394508 KB Output is correct
13 Correct 159 ms 394256 KB Output is correct
14 Correct 158 ms 393936 KB Output is correct
15 Incorrect 154 ms 394652 KB Output isn't correct
16 Halted 0 ms 0 KB -