oj.uz

Submission #624111

# Submission time Handle Problem Language Result Execution time Memory
624111 2022-08-07T09:24:03 Z Arinoor LOSTIKS (INOI20_lostiks) C++17
36 / 100
 318 ms 270000 KB 
#include <bits/stdc++.h>
using namespace std;

#define pb				push_back
#define mp				make_pair
#define fi				first
#define se				second
#define all(x)			x.begin(), x.end()
#define bug(x)			cout << #x << " : " << x << '\n'
#define ios				ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0)

typedef long long ll;
typedef pair<int, int> pii;

const int maxn = 1e6 + 10;
const int maxm = 30;
const int maxlg = 20;
const int mod = 1e9 + 7;
const ll inf = 1e17 + 10;

int e[maxn], h[maxn], par[maxn][maxlg], lck[maxn][maxlg], V[maxm], ind[maxn];
int dt[maxm], dl[maxm];
int d[maxm][maxm], l[maxm][maxm];
ll dp[1 << maxlg][maxm];
vector<pii> E;
vector<pii> edge;
vector<int> G[maxn], S;

void dfs(int v, int p = 0, int pe = -1){
	par[v][0] = p;
	if(~pe)
		lck[v][0] = 1 << pe;
	for(int i = 1; i < maxlg and par[v][i - 1]; i ++){
		par[v][i] = par[par[v][i - 1]][i - 1];
		lck[v][i] = lck[v][i - 1] | lck[par[v][i - 1]][i - 1];
	}
	for(int eg : G[v]){
		int u = edge[eg].fi + edge[eg].se - v;
		if(u != p){
			h[u] = h[v] + 1;
			dfs(u, v, e[eg]);
		}
	}
}

int get_par(int v, int h){
	for(int i = 0; i < maxlg; i ++)
		if(h >> i & 1)
			v = par[v][i];
	return v;
}

int get_lock(int v, int h){
	int res = 0;
	for(int i = 0; i < maxlg; i ++){
		if(h >> i & 1){
			res |= lck[v][i];
			v = par[v][i];
		}
	}
	return res;
}

int lca(int v, int u){
	if(h[v] < h[u])
		swap(u, v);
	v = get_par(v, h[v] - h[u]);
	if(v == u)
		return v;
	for(int i = maxlg - 1; ~i; i --){
		if(par[v][i] ^ par[u][i]){
			v = par[v][i];
			u = par[u][i];
		}
	}
	return par[v][0];
}

int dist(int u, int v){
	int w = lca(u, v);
	return h[v] + h[u] - 2 * h[w];
}

int lock_path(int u, int v){
	int w = lca(u, v);
	return get_lock(u, h[u] - h[w]) | get_lock(v, h[v] - h[w]);
}

int main(){
	ios;
	int n, s, t;
	cin >> n >> s >> t;
	for(int i = 0; i < n - 1; i ++){
		int u, v, w;
		cin >> u >> v >> w;
		edge.pb(mp(u, v));
		G[u].pb(i);
		G[v].pb(i);
		if(w){
			e[i] = E.size();
			E.pb(mp(i, w));
		}
		else{
			e[i] = -1;
		}
	}
	dfs(1);
	int m = E.size();
	for(int i = 0; i < m; i ++){
		int u = edge[E[i].fi].fi;
		int v = edge[E[i].fi].se;
		if(dist(E[i].se, u) < dist(E[i].se, v))
			V[i] = u;
		else
			V[i] = v;
		S.pb(V[i]);
	}
	S.pb(s);
	sort(all(S));
	S.resize(unique(all(S)) - S.begin());
	for(int v : S)
		ind[v] = lower_bound(all(S), v) - S.begin();
	n = S.size();
	for(int i = 0; i < n; i ++){
		int v = S[i];
		dt[i] = dist(v, t);
		dl[i] = lock_path(v, t);
		for(int j = 0; j < m; j ++){
			int u = V[j];
			int w = E[j].se;
			d[i][j] = dist(v, w) + dist(w, u);
			l[i][j] = lock_path(v, w) | lock_path(w, u);
		}
	}
	for(int msk = 0; msk < 1 << m; msk ++){
		for(int i = 0; i < n; i ++){
			if(!(dl[i] & msk)){
				dp[msk][i] = dt[i];
				continue;
			}
			dp[msk][i] = inf;
			for(int msk2 = msk; ; msk2 -= msk2 & -msk2){
				if(!msk2) break;
				int bit = __builtin_ctz(msk2);
				if(!(l[i][bit] & msk)){
					dp[msk][i] = min(dp[msk][i], d[i][bit] + dp[msk ^ (1 << bit)][ind[V[bit]]]);
				}
			}
		}
	}
	cout << dp[(1 << m) - 1][ind[s]] << '\n';
}

Subtask #1
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23772 KB Output is correct
2 Correct 12 ms 23812 KB Output is correct
3 Correct 79 ms 45736 KB Output is correct
4 Correct 92 ms 45796 KB Output is correct
5 Correct 94 ms 45884 KB Output is correct
6 Correct 81 ms 45852 KB Output is correct
7 Correct 85 ms 45976 KB Output is correct
8 Correct 84 ms 45952 KB Output is correct
9 Correct 82 ms 46008 KB Output is correct
10 Correct 84 ms 45928 KB Output is correct
11 Correct 79 ms 45820 KB Output is correct
12 Correct 85 ms 46992 KB Output is correct
13 Correct 95 ms 48092 KB Output is correct
14 Correct 96 ms 46924 KB Output is correct
15 Incorrect 91 ms 47256 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 12 ms 23764 KB Output is correct
2 Correct 13 ms 23788 KB Output is correct
3 Correct 15 ms 24060 KB Output is correct
4 Correct 13 ms 24148 KB Output is correct
5 Correct 305 ms 148400 KB Output is correct
6 Correct 297 ms 148428 KB Output is correct
7 Correct 318 ms 148492 KB Output is correct
8 Correct 273 ms 148428 KB Output is correct
9 Correct 301 ms 148492 KB Output is correct
10 Correct 262 ms 148476 KB Output is correct
11 Correct 254 ms 148476 KB Output is correct
12 Correct 238 ms 148500 KB Output is correct
13 Correct 260 ms 148452 KB Output is correct
14 Correct 261 ms 148480 KB Output is correct
15 Correct 304 ms 148476 KB Output is correct
16 Correct 289 ms 148628 KB Output is correct
17 Correct 303 ms 148444 KB Output is correct
18 Correct 229 ms 148556 KB Output is correct
19 Correct 270 ms 148608 KB Output is correct
20 Correct 247 ms 148608 KB Output is correct
21 Correct 283 ms 148736 KB Output is correct
22 Correct 233 ms 148808 KB Output is correct
23 Correct 232 ms 148728 KB Output is correct
24 Correct 242 ms 148824 KB Output is correct
25 Correct 161 ms 270000 KB Output is correct

Subtask #3
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23772 KB Output is correct
2 Correct 12 ms 23812 KB Output is correct
3 Correct 79 ms 45736 KB Output is correct
4 Correct 92 ms 45796 KB Output is correct
5 Correct 94 ms 45884 KB Output is correct
6 Correct 81 ms 45852 KB Output is correct
7 Correct 85 ms 45976 KB Output is correct
8 Correct 84 ms 45952 KB Output is correct
9 Correct 82 ms 46008 KB Output is correct
10 Correct 84 ms 45928 KB Output is correct
11 Correct 79 ms 45820 KB Output is correct
12 Correct 85 ms 46992 KB Output is correct
13 Correct 95 ms 48092 KB Output is correct
14 Correct 96 ms 46924 KB Output is correct
15 Incorrect 91 ms 47256 KB Output isn't correct
16 Halted 0 ms 0 KB -