oj.uz

Submission #1025209

# Submission time Handle Problem Language Result Execution time Memory
1025209 2024-07-16T17:38:08 Z Amirreza_Fakhri LOSTIKS (INOI20_lostiks) C++17
36 / 100
 725 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 == 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 4 ms 31320 KB Output is correct
2 Correct 4 ms 31320 KB Output is correct
3 Correct 48 ms 52292 KB Output is correct
4 Correct 37 ms 52400 KB Output is correct
5 Correct 37 ms 52304 KB Output is correct
6 Correct 35 ms 52312 KB Output is correct
7 Correct 37 ms 52316 KB Output is correct
8 Correct 37 ms 52436 KB Output is correct
9 Correct 35 ms 52572 KB Output is correct
10 Correct 35 ms 52340 KB Output is correct
11 Correct 41 ms 52308 KB Output is correct
12 Correct 34 ms 53072 KB Output is correct
13 Correct 45 ms 52824 KB Output is correct
14 Correct 41 ms 52564 KB Output is correct
15 Correct 35 ms 53080 KB Output is correct
16 Correct 36 ms 54920 KB Output is correct
17 Correct 35 ms 54956 KB Output is correct
18 Correct 39 ms 55124 KB Output is correct
19 Correct 38 ms 57572 KB Output is correct
20 Correct 40 ms 57524 KB Output is correct
21 Correct 40 ms 57432 KB Output is correct
22 Correct 4 ms 31324 KB Output is correct
23 Correct 4 ms 31324 KB Output is correct
24 Correct 4 ms 31416 KB Output is correct
25 Correct 4 ms 31324 KB Output is correct
26 Incorrect 4 ms 31440 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 4 ms 31324 KB Output is correct
2 Correct 4 ms 31324 KB Output is correct
3 Correct 4 ms 31376 KB Output is correct
4 Correct 5 ms 31320 KB Output is correct
5 Correct 305 ms 113756 KB Output is correct
6 Correct 304 ms 113808 KB Output is correct
7 Correct 317 ms 113756 KB Output is correct
8 Correct 295 ms 113752 KB Output is correct
9 Correct 319 ms 113756 KB Output is correct
10 Correct 302 ms 113756 KB Output is correct
11 Correct 299 ms 113824 KB Output is correct
12 Correct 300 ms 113752 KB Output is correct
13 Correct 312 ms 113824 KB Output is correct
14 Correct 298 ms 113752 KB Output is correct
15 Correct 312 ms 113796 KB Output is correct
16 Correct 332 ms 113752 KB Output is correct
17 Correct 334 ms 113756 KB Output is correct
18 Correct 323 ms 113752 KB Output is correct
19 Correct 315 ms 113880 KB Output is correct
20 Correct 330 ms 114004 KB Output is correct
21 Correct 326 ms 113752 KB Output is correct
22 Correct 329 ms 114080 KB Output is correct
23 Correct 329 ms 114012 KB Output is correct
24 Correct 322 ms 114012 KB Output is correct
25 Correct 725 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 31320 KB Output is correct
3 Correct 48 ms 52292 KB Output is correct
4 Correct 37 ms 52400 KB Output is correct
5 Correct 37 ms 52304 KB Output is correct
6 Correct 35 ms 52312 KB Output is correct
7 Correct 37 ms 52316 KB Output is correct
8 Correct 37 ms 52436 KB Output is correct
9 Correct 35 ms 52572 KB Output is correct
10 Correct 35 ms 52340 KB Output is correct
11 Correct 41 ms 52308 KB Output is correct
12 Correct 34 ms 53072 KB Output is correct
13 Correct 45 ms 52824 KB Output is correct
14 Correct 41 ms 52564 KB Output is correct
15 Correct 35 ms 53080 KB Output is correct
16 Correct 36 ms 54920 KB Output is correct
17 Correct 35 ms 54956 KB Output is correct
18 Correct 39 ms 55124 KB Output is correct
19 Correct 38 ms 57572 KB Output is correct
20 Correct 40 ms 57524 KB Output is correct
21 Correct 40 ms 57432 KB Output is correct
22 Correct 4 ms 31324 KB Output is correct
23 Correct 4 ms 31324 KB Output is correct
24 Correct 4 ms 31416 KB Output is correct
25 Correct 4 ms 31324 KB Output is correct
26 Incorrect 4 ms 31440 KB Output isn't correct
27 Halted 0 ms 0 KB -