oj.uz

Submission #1025212

# Submission time Handle Problem Language Result Execution time Memory
1025212 2024-07-16T17:49:25 Z Amirreza_Fakhri LOSTIKS (INOI20_lostiks) C++17
36 / 100
 693 ms 210668 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 = 22;

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 == inf*inf ? -1 : 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 5 ms 31320 KB Output is correct
2 Correct 5 ms 31324 KB Output is correct
3 Correct 39 ms 53688 KB Output is correct
4 Correct 43 ms 54096 KB Output is correct
5 Correct 48 ms 54244 KB Output is correct
6 Correct 43 ms 54100 KB Output is correct
7 Correct 42 ms 54352 KB Output is correct
8 Correct 41 ms 54356 KB Output is correct
9 Correct 42 ms 54356 KB Output is correct
10 Correct 45 ms 54364 KB Output is correct
11 Correct 45 ms 54352 KB Output is correct
12 Correct 40 ms 54876 KB Output is correct
13 Correct 39 ms 54100 KB Output is correct
14 Correct 40 ms 53848 KB Output is correct
15 Correct 42 ms 54884 KB Output is correct
16 Correct 42 ms 55452 KB Output is correct
17 Correct 42 ms 55380 KB Output is correct
18 Correct 44 ms 55636 KB Output is correct
19 Correct 43 ms 58196 KB Output is correct
20 Correct 45 ms 57936 KB Output is correct
21 Correct 44 ms 57948 KB Output is correct
22 Correct 4 ms 31320 KB Output is correct
23 Correct 4 ms 31324 KB Output is correct
24 Correct 5 ms 31324 KB Output is correct
25 Correct 5 ms 31324 KB Output is correct
26 Incorrect 5 ms 31324 KB Output isn't correct
27 Halted 0 ms 0 KB -

Subtask #2
36.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 31320 KB Output is correct
2 Correct 5 ms 31324 KB Output is correct
3 Correct 5 ms 31324 KB Output is correct
4 Correct 5 ms 31420 KB Output is correct
5 Correct 343 ms 121944 KB Output is correct
6 Correct 328 ms 121944 KB Output is correct
7 Correct 333 ms 122016 KB Output is correct
8 Correct 341 ms 121948 KB Output is correct
9 Correct 327 ms 121948 KB Output is correct
10 Correct 327 ms 121944 KB Output is correct
11 Correct 296 ms 121948 KB Output is correct
12 Correct 295 ms 121944 KB Output is correct
13 Correct 312 ms 121944 KB Output is correct
14 Correct 300 ms 121944 KB Output is correct
15 Correct 333 ms 121948 KB Output is correct
16 Correct 302 ms 122008 KB Output is correct
17 Correct 342 ms 121948 KB Output is correct
18 Correct 312 ms 122100 KB Output is correct
19 Correct 311 ms 122088 KB Output is correct
20 Correct 296 ms 121948 KB Output is correct
21 Correct 293 ms 122124 KB Output is correct
22 Correct 299 ms 122204 KB Output is correct
23 Correct 294 ms 122288 KB Output is correct
24 Correct 311 ms 122192 KB Output is correct
25 Correct 693 ms 210668 KB Output is correct

Subtask #3
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 31320 KB Output is correct
2 Correct 5 ms 31324 KB Output is correct
3 Correct 39 ms 53688 KB Output is correct
4 Correct 43 ms 54096 KB Output is correct
5 Correct 48 ms 54244 KB Output is correct
6 Correct 43 ms 54100 KB Output is correct
7 Correct 42 ms 54352 KB Output is correct
8 Correct 41 ms 54356 KB Output is correct
9 Correct 42 ms 54356 KB Output is correct
10 Correct 45 ms 54364 KB Output is correct
11 Correct 45 ms 54352 KB Output is correct
12 Correct 40 ms 54876 KB Output is correct
13 Correct 39 ms 54100 KB Output is correct
14 Correct 40 ms 53848 KB Output is correct
15 Correct 42 ms 54884 KB Output is correct
16 Correct 42 ms 55452 KB Output is correct
17 Correct 42 ms 55380 KB Output is correct
18 Correct 44 ms 55636 KB Output is correct
19 Correct 43 ms 58196 KB Output is correct
20 Correct 45 ms 57936 KB Output is correct
21 Correct 44 ms 57948 KB Output is correct
22 Correct 4 ms 31320 KB Output is correct
23 Correct 4 ms 31324 KB Output is correct
24 Correct 5 ms 31324 KB Output is correct
25 Correct 5 ms 31324 KB Output is correct
26 Incorrect 5 ms 31324 KB Output isn't correct
27 Halted 0 ms 0 KB -