oj.uz

Submission #1025208

# Submission time Handle Problem Language Result Execution time Memory
1025208 2024-07-16T17:36:58 Z Amirreza_Fakhri LOSTIKS (INOI20_lostiks) C++17
36 / 100
 640 ms 193372 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);
		}
	}
	for (int i = 0; i < (1<<m); i++) {
		for (int j = 0; j < m; j++) dp[i][j] = inf*inf;
	}
	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 4 ms 31320 KB Output is correct
2 Correct 4 ms 31324 KB Output is correct
3 Correct 34 ms 52416 KB Output is correct
4 Correct 35 ms 52368 KB Output is correct
5 Correct 35 ms 52312 KB Output is correct
6 Correct 35 ms 52316 KB Output is correct
7 Correct 36 ms 52304 KB Output is correct
8 Correct 38 ms 52316 KB Output is correct
9 Correct 41 ms 52560 KB Output is correct
10 Correct 39 ms 52308 KB Output is correct
11 Correct 37 ms 52308 KB Output is correct
12 Correct 34 ms 53084 KB Output is correct
13 Correct 35 ms 52828 KB Output is correct
14 Correct 34 ms 52564 KB Output is correct
15 Incorrect 36 ms 53072 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 4 ms 31324 KB Output is correct
2 Correct 4 ms 31324 KB Output is correct
3 Correct 5 ms 31324 KB Output is correct
4 Correct 5 ms 31324 KB Output is correct
5 Correct 315 ms 113724 KB Output is correct
6 Correct 303 ms 113756 KB Output is correct
7 Correct 314 ms 113816 KB Output is correct
8 Correct 316 ms 113756 KB Output is correct
9 Correct 304 ms 113756 KB Output is correct
10 Correct 297 ms 113756 KB Output is correct
11 Correct 306 ms 113756 KB Output is correct
12 Correct 300 ms 113752 KB Output is correct
13 Correct 308 ms 113824 KB Output is correct
14 Correct 300 ms 113820 KB Output is correct
15 Correct 320 ms 113796 KB Output is correct
16 Correct 300 ms 113752 KB Output is correct
17 Correct 294 ms 113752 KB Output is correct
18 Correct 297 ms 113756 KB Output is correct
19 Correct 285 ms 113752 KB Output is correct
20 Correct 294 ms 113752 KB Output is correct
21 Correct 298 ms 113756 KB Output is correct
22 Correct 292 ms 114088 KB Output is correct
23 Correct 292 ms 114012 KB Output is correct
24 Correct 294 ms 114092 KB Output is correct
25 Correct 640 ms 193372 KB Output is correct

Subtask #3
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 31320 KB Output is correct
2 Correct 4 ms 31324 KB Output is correct
3 Correct 34 ms 52416 KB Output is correct
4 Correct 35 ms 52368 KB Output is correct
5 Correct 35 ms 52312 KB Output is correct
6 Correct 35 ms 52316 KB Output is correct
7 Correct 36 ms 52304 KB Output is correct
8 Correct 38 ms 52316 KB Output is correct
9 Correct 41 ms 52560 KB Output is correct
10 Correct 39 ms 52308 KB Output is correct
11 Correct 37 ms 52308 KB Output is correct
12 Correct 34 ms 53084 KB Output is correct
13 Correct 35 ms 52828 KB Output is correct
14 Correct 34 ms 52564 KB Output is correct
15 Incorrect 36 ms 53072 KB Output isn't correct
16 Halted 0 ms 0 KB -