oj.uz

Submission #1025205

# Submission time Handle Problem Language Result Execution time Memory
1025205 2024-07-16T17:33:59 Z Amirreza_Fakhri LOSTIKS (INOI20_lostiks) C++17
36 / 100
 609 ms 215124 KB 
// In the name of the God
#include <bits/stdc++.h>
#define ll long long
#define int long long
#define pb push_back
#define F first
#define S second
#define mp make_pair
#define pii pair <int, int>
#define smin(x, y) (x) = min((x), (y))
#define smax(x, y) (x) = max((x), (y))
#define all(x) (x).begin(), (x).end()
using namespace std;

//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx2")

const int inf = 1e9+7;
const int mod = 998244353;
const int maxn = 1e6+5, lg = 20;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int n, m, s, t, ti = 0, h[maxn], in[maxn], out[maxn], par[maxn][lg], dist[lg][lg], ne[lg][lg], dp[1<<lg][lg];
vector <int> adj[maxn];
vector <pair <pii, int>> g;

void dfs(int v, int p) {
	par[v][0] = p;
	for (int i = 1; i < lg; i++) par[v][i] = par[par[v][i-1]][i-1];
	in[v] = ti++;
	for (int u : adj[v]) {
		if (u == p) continue;
		h[u] = h[v]+1;
		dfs(u, v);
	}
	out[v] = ti;
}

int lca(int v, int u) {
	if (h[v] < h[u]) swap(v, u);
	int x = h[v]-h[u];
	for (int i = 0; i < lg; i++) {
		if (x&(1<<i)) v = par[v][i];
	}
	if (v == u) return v;
	for (int i = lg-1; i >= 0; i--) {
		if (par[v][i] != par[u][i]) v = par[v][i], u = par[u][i];
	}
	return par[v][0];
}

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

bool isd(int v, int u) {
	return in[v] <= in[u] and out[v] >= out[u];
}

int f(int v, int u) {
	int res = 0, z = lca(u, v);
	for (int i = 0; i < m; i++) {
		int x = g[i].F.F, y = g[i].F.S;
		bool f = 0;
		f = (isd(y, v)&isd(z, x))|(isd(y, u)&isd(z, x));
		if (f) res += 1<<i;
	}
	return res;
}

int32_t main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> s >> t; s--, t--;
    for (int i = 1; i < n; i++) {
    	int v, u, w; cin >> v >> u >> w; v--, u--, w--;
    	adj[v].pb(u), adj[u].pb(v);
    	if (w != -1) g.pb(mp(mp(v, u), w));
	}
	m = g.size();
	dfs(s, s);
	for (auto &p : g) if (h[p.F.F] > h[p.F.S]) swap(p.F.F, p.F.S);
	for (int i = 0; i < m; i++) {
		for (int j = 0; j < m; j++) {
			dist[i][j] = d(g[i].F.F, g[j].S);
			ne[i][j] = f(g[i].F.F, g[j].S);
		}
	}
	memset(dp, 63, sizeof dp);
	for (int i = 0; i < m; i++) {
		if (f(s, g[i].S) == 0 and f(g[i].S	, g[i].F.F) == 0) dp[1<<i][i] = d(s, g[i].S)+d(g[i].S, g[i].F.F);
	}
	for (int i = 0; i < (1<<m); i++) {
		for (int j = 0; j < m; j++) {
			if (i&(1<<j)) {
				for (int k = 0; k < m; k++) {
					if (!(i&(1<<k))) {
						if ((ne[j][k]|i) == i and (ne[k][k]|i) == i) smin(dp[i+(1<<k)][k], dp[i][j]+dist[j][k]+dist[k][k]);
					}
				}
			}
		}
	}
	if (s == t) return cout << 0 << '\n', 0;
	int ali = 1, p = t;
	while (p != s) {
		for (int i = 0; i < m; i++) {
			if (g[i].F.S == p) {
				ali = i;
				goto TH;
			}
		}
		p = par[p][0];
	}
	TH:;
	if (ali == -1) return cout << d(s, t) << '\n', 0;
	int amir = d(g[ali].F.F, t), ans = inf*inf;
	for (int i = 0; i < (1<<m); i++) smin(ans, amir+dp[i][ali]);
	cout << ans << '\n';
    return 0;
}












/*
srand(time(0));
cout << (rand()%1900) + 1 << ' ' << (rand()%2)+5 << '\n';
*/

Subtask #1
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 193372 KB Output is correct
2 Correct 22 ms 193372 KB Output is correct
3 Correct 57 ms 214516 KB Output is correct
4 Correct 56 ms 214356 KB Output is correct
5 Correct 58 ms 214504 KB Output is correct
6 Correct 58 ms 214352 KB Output is correct
7 Correct 60 ms 214608 KB Output is correct
8 Correct 57 ms 214352 KB Output is correct
9 Correct 60 ms 214528 KB Output is correct
10 Correct 57 ms 214608 KB Output is correct
11 Correct 56 ms 214356 KB Output is correct
12 Correct 58 ms 215120 KB Output is correct
13 Correct 64 ms 214864 KB Output is correct
14 Correct 55 ms 214612 KB Output is correct
15 Incorrect 57 ms 215124 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 22 ms 193368 KB Output is correct
2 Correct 25 ms 193372 KB Output is correct
3 Correct 23 ms 193472 KB Output is correct
4 Correct 22 ms 193364 KB Output is correct
5 Correct 315 ms 193736 KB Output is correct
6 Correct 325 ms 193616 KB Output is correct
7 Correct 315 ms 193840 KB Output is correct
8 Correct 297 ms 193624 KB Output is correct
9 Correct 322 ms 193840 KB Output is correct
10 Correct 303 ms 193620 KB Output is correct
11 Correct 305 ms 193868 KB Output is correct
12 Correct 307 ms 193816 KB Output is correct
13 Correct 306 ms 193628 KB Output is correct
14 Correct 298 ms 193620 KB Output is correct
15 Correct 312 ms 193616 KB Output is correct
16 Correct 314 ms 193828 KB Output is correct
17 Correct 321 ms 193624 KB Output is correct
18 Correct 307 ms 193872 KB Output is correct
19 Correct 298 ms 193904 KB Output is correct
20 Correct 302 ms 193884 KB Output is correct
21 Correct 311 ms 193940 KB Output is correct
22 Correct 291 ms 193884 KB Output is correct
23 Correct 295 ms 193876 KB Output is correct
24 Correct 306 ms 193880 KB Output is correct
25 Correct 609 ms 193372 KB Output is correct

Subtask #3
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 193372 KB Output is correct
2 Correct 22 ms 193372 KB Output is correct
3 Correct 57 ms 214516 KB Output is correct
4 Correct 56 ms 214356 KB Output is correct
5 Correct 58 ms 214504 KB Output is correct
6 Correct 58 ms 214352 KB Output is correct
7 Correct 60 ms 214608 KB Output is correct
8 Correct 57 ms 214352 KB Output is correct
9 Correct 60 ms 214528 KB Output is correct
10 Correct 57 ms 214608 KB Output is correct
11 Correct 56 ms 214356 KB Output is correct
12 Correct 58 ms 215120 KB Output is correct
13 Correct 64 ms 214864 KB Output is correct
14 Correct 55 ms 214612 KB Output is correct
15 Incorrect 57 ms 215124 KB Output isn't correct
16 Halted 0 ms 0 KB -