oj.uz

Submission #1025213

# Submission time Handle Problem Language Result Execution time Memory
1025213 2024-07-16T17:51:42 Z Amirreza_Fakhri LOSTIKS (INOI20_lostiks) C++17
100 / 100
 1130 ms 403332 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
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 31324 KB Output is correct
2 Correct 5 ms 31324 KB Output is correct
3 Correct 40 ms 53876 KB Output is correct
4 Correct 41 ms 54104 KB Output is correct
5 Correct 43 ms 54100 KB Output is correct
6 Correct 46 ms 54096 KB Output is correct
7 Correct 51 ms 54352 KB Output is correct
8 Correct 43 ms 54356 KB Output is correct
9 Correct 45 ms 54452 KB Output is correct
10 Correct 41 ms 54352 KB Output is correct
11 Correct 43 ms 54352 KB Output is correct
12 Correct 48 ms 54964 KB Output is correct
13 Correct 41 ms 54100 KB Output is correct
14 Correct 40 ms 53840 KB Output is correct
15 Correct 43 ms 54864 KB Output is correct
16 Correct 43 ms 55376 KB Output is correct
17 Correct 43 ms 55388 KB Output is correct
18 Correct 52 ms 55636 KB Output is correct
19 Correct 44 ms 58204 KB Output is correct
20 Correct 46 ms 57932 KB Output is correct
21 Correct 44 ms 57940 KB Output is correct
22 Correct 5 ms 31320 KB Output is correct
23 Correct 5 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 Correct 5 ms 31320 KB Output is correct

Subtask #2
36.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 31332 KB Output is correct
2 Correct 5 ms 31376 KB Output is correct
3 Correct 5 ms 31324 KB Output is correct
4 Correct 5 ms 31320 KB Output is correct
5 Correct 350 ms 121948 KB Output is correct
6 Correct 343 ms 122016 KB Output is correct
7 Correct 341 ms 122020 KB Output is correct
8 Correct 339 ms 121868 KB Output is correct
9 Correct 338 ms 121944 KB Output is correct
10 Correct 335 ms 121948 KB Output is correct
11 Correct 343 ms 121944 KB Output is correct
12 Correct 332 ms 121988 KB Output is correct
13 Correct 334 ms 121948 KB Output is correct
14 Correct 326 ms 121948 KB Output is correct
15 Correct 343 ms 122000 KB Output is correct
16 Correct 335 ms 121944 KB Output is correct
17 Correct 346 ms 121948 KB Output is correct
18 Correct 323 ms 121948 KB Output is correct
19 Correct 320 ms 121948 KB Output is correct
20 Correct 318 ms 122092 KB Output is correct
21 Correct 304 ms 122116 KB Output is correct
22 Correct 322 ms 122184 KB Output is correct
23 Correct 291 ms 122192 KB Output is correct
24 Correct 324 ms 122296 KB Output is correct
25 Correct 685 ms 210512 KB Output is correct

Subtask #3
41.0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 31324 KB Output is correct
2 Correct 5 ms 31324 KB Output is correct
3 Correct 40 ms 53876 KB Output is correct
4 Correct 41 ms 54104 KB Output is correct
5 Correct 43 ms 54100 KB Output is correct
6 Correct 46 ms 54096 KB Output is correct
7 Correct 51 ms 54352 KB Output is correct
8 Correct 43 ms 54356 KB Output is correct
9 Correct 45 ms 54452 KB Output is correct
10 Correct 41 ms 54352 KB Output is correct
11 Correct 43 ms 54352 KB Output is correct
12 Correct 48 ms 54964 KB Output is correct
13 Correct 41 ms 54100 KB Output is correct
14 Correct 40 ms 53840 KB Output is correct
15 Correct 43 ms 54864 KB Output is correct
16 Correct 43 ms 55376 KB Output is correct
17 Correct 43 ms 55388 KB Output is correct
18 Correct 52 ms 55636 KB Output is correct
19 Correct 44 ms 58204 KB Output is correct
20 Correct 46 ms 57932 KB Output is correct
21 Correct 44 ms 57940 KB Output is correct
22 Correct 5 ms 31320 KB Output is correct
23 Correct 5 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 Correct 5 ms 31320 KB Output is correct
27 Correct 5 ms 31332 KB Output is correct
28 Correct 5 ms 31376 KB Output is correct
29 Correct 5 ms 31324 KB Output is correct
30 Correct 5 ms 31320 KB Output is correct
31 Correct 350 ms 121948 KB Output is correct
32 Correct 343 ms 122016 KB Output is correct
33 Correct 341 ms 122020 KB Output is correct
34 Correct 339 ms 121868 KB Output is correct
35 Correct 338 ms 121944 KB Output is correct
36 Correct 335 ms 121948 KB Output is correct
37 Correct 343 ms 121944 KB Output is correct
38 Correct 332 ms 121988 KB Output is correct
39 Correct 334 ms 121948 KB Output is correct
40 Correct 326 ms 121948 KB Output is correct
41 Correct 343 ms 122000 KB Output is correct
42 Correct 335 ms 121944 KB Output is correct
43 Correct 346 ms 121948 KB Output is correct
44 Correct 323 ms 121948 KB Output is correct
45 Correct 320 ms 121948 KB Output is correct
46 Correct 318 ms 122092 KB Output is correct
47 Correct 304 ms 122116 KB Output is correct
48 Correct 322 ms 122184 KB Output is correct
49 Correct 291 ms 122192 KB Output is correct
50 Correct 324 ms 122296 KB Output is correct
51 Correct 685 ms 210512 KB Output is correct
52 Correct 821 ms 277976 KB Output is correct
53 Correct 857 ms 277076 KB Output is correct
54 Correct 806 ms 276304 KB Output is correct
55 Correct 819 ms 276128 KB Output is correct
56 Correct 810 ms 276048 KB Output is correct
57 Correct 830 ms 277872 KB Output is correct
58 Correct 5 ms 31320 KB Output is correct
59 Correct 5 ms 31324 KB Output is correct
60 Correct 5 ms 31344 KB Output is correct
61 Correct 806 ms 277948 KB Output is correct
62 Correct 853 ms 297296 KB Output is correct
63 Correct 812 ms 286124 KB Output is correct
64 Correct 52 ms 56788 KB Output is correct
65 Correct 55 ms 56916 KB Output is correct
66 Correct 814 ms 278096 KB Output is correct
67 Correct 800 ms 277072 KB Output is correct
68 Correct 958 ms 364128 KB Output is correct
69 Correct 958 ms 363952 KB Output is correct
70 Correct 978 ms 364112 KB Output is correct
71 Correct 953 ms 363856 KB Output is correct
72 Correct 976 ms 363840 KB Output is correct
73 Correct 979 ms 364880 KB Output is correct
74 Correct 990 ms 365652 KB Output is correct
75 Correct 982 ms 364624 KB Output is correct
76 Correct 966 ms 365724 KB Output is correct
77 Correct 918 ms 364956 KB Output is correct
78 Correct 942 ms 364192 KB Output is correct
79 Correct 985 ms 363940 KB Output is correct
80 Correct 1006 ms 362316 KB Output is correct
81 Correct 1051 ms 372164 KB Output is correct
82 Correct 1077 ms 373804 KB Output is correct
83 Correct 1031 ms 373864 KB Output is correct
84 Correct 995 ms 380500 KB Output is correct
85 Correct 1071 ms 403332 KB Output is correct
86 Correct 1130 ms 402512 KB Output is correct
87 Correct 1111 ms 402680 KB Output is correct