oj.uz

Submission #789558

# Submission time Handle Problem Language Result Execution time Memory
789558 2023-07-21T13:44:23 Z MISM06 LOSTIKS (INOI20_lostiks) C++14
100 / 100
 1717 ms 395568 KB 
//0 1 1 0 1
//0 1 0 0 1
//1 0 0 1 1
//0 1 1 0 1
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast,unroll-loops")
// #pragma GCC target("avx2")

using namespace std;

#define F 			first
#define S 			second
#define pb 			push_back
#define sze			size()
#define	all(x)		x.begin() , x.end()
#define wall__		cout << "--------------------------------------\n";
#define kids		int mid = (tl + tr) >> 1, cl = v << 1, cr = v << 1 | 1
#define file_io		freopen("input.cpp", "r", stdin); freopen("output.cpp", "w", stdout);

typedef long long ll;
typedef long double dl;
typedef pair < int , int > pii;
typedef pair < int , ll > pil;
typedef pair < ll , int > pli;
typedef pair < ll , ll > pll;
typedef pair < int , pii > piii;
typedef pair < ll, pll > plll;


const ll N = (1 << 20) + 10, M = 23;
const ll mod = 1e9 + 7;
const ll inf = 2e16;
const ll INF = 1e9 + 10;
const ll lg = 20;

ll n, s, t, h[N], st[N], en[N], m, timer = 0, par[lg][N], id[N], rid[N], dis[M * 2][M * 2];
int inp[M * 2][M * 2];
vector < int > g[N];
piii lc[M];
ll dp[M][N];

void dfs (int v, int p) {
	h[v] = h[p] + 1;
	st[v] = ++timer;
	par[0][v] = p;
	for (int i = 1; i < lg; i++) par[i][v] = par[i - 1][par[i - 1][v]];
	for (auto u : g[v]) {
		if (u == p) continue;
		dfs(u, v);
	}
	en[v] = timer;
}
inline bool be_anc (int v, int u) {
	return (st[v] <= st[u] && en[v] >= en[u]);
}
inline int lca (int v, int u) {
	if (be_anc(v, u)) return v;
	if (be_anc(u, v)) return u;
	for (int i = lg - 1; i >= 0; --i) {
		if (!be_anc(par[i][v], u)) v = par[i][v];
	}
	return par[0][v];
}
inline bool is_in_path (int x, int v, int u) {
	if (x == v || x == u || x == lca(v, u)) return 1;
	if (be_anc(x, v) && !be_anc(x, u)) return 1;
	if (be_anc(x, u) && !be_anc(x, v)) return 1;
	return 0;
}
void solve () {

	cin >> n >> s >> t;
	for (int i = 1; i < n; i++) {
		int v, u, w;
		cin >> v >> u >> w;
		if (v == u) continue;
		if (w != 0) {
			lc[m] = {w, {v, u}};
			++m;
		}
		g[v].pb(u);
		g[u].pb(v);
	}
	if (s == t) {
		cout << 0 << '\n';
		return;
	}
	en[0] = INF;
	dfs(s, 0);
	for (int i = 0; i < m; i++) {
		if (st[lc[i].S.F] > st[lc[i].S.S]) swap(lc[i].S.F, lc[i].S.S);
		int v = lc[i].S.F;
		id[v] = i; rid[i] = v;
	}
	id[s] = m; rid[m] = s; id[t] = m + 1; rid[m + 1] = t;
	for (int i = 0; i < m; i++) {
		int v = lc[i].F;
		id[v] = m + 2 + i;
		rid[m + 2 + i] = v;
	}
	for (int i = 0; i <= m + 1 + m; i++) {
		for (int j = 0; j <= m + 1 + m; j++) {
			for (int x = 0; x < m; x++) {
				if (is_in_path(lc[x].S.F, rid[i], rid[j]) && is_in_path(lc[x].S.S, rid[i], rid[j])) 
					inp[i][j] += (1 << x);
				int xx = rid[i], y = rid[j];
				dis[i][j] = h[xx] + h[y] - 2 * h[lca(xx, y)];
			}
		}
	}
	for (int mask = 0; mask < (1 << m); mask++) {
		for (int v = 0; v <= m; v++) {
			dp[v][mask] = inf;
			if (inp[v][m] & mask) continue;
			if ((mask & inp[v][m + 1]) == 0) dp[v][mask] = dis[v][id[t]];
			for (int i = 0; i < m; i++) {
				if (((1 << i) & mask) == 0) continue;
				int w = lc[i].F;
				if ((inp[id[w]][v] & mask) == 0 && (inp[id[w]][i] & mask) == 0) {
					dp[v][mask] = min(dp[v][mask], dp[i][mask ^ (1 << i)] + dis[v][id[w]] + dis[id[w]][i]);
				}
			}
		}
	}
	if (dp[m][(1 << m) - 1] >= inf) cout << -1 << '\n';
	else cout << dp[m][(1 << m) - 1];

}


int main() {
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int q = 1;
	// cin >> q;
	while (q--) {solve();}
    return 0;
}
/*
*/
//shrek is love;

Subtask #1
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 25172 KB Output is correct
2 Correct 14 ms 25172 KB Output is correct
3 Correct 72 ms 46632 KB Output is correct
4 Correct 72 ms 46628 KB Output is correct
5 Correct 72 ms 46660 KB Output is correct
6 Correct 89 ms 46556 KB Output is correct
7 Correct 92 ms 46708 KB Output is correct
8 Correct 81 ms 46772 KB Output is correct
9 Correct 72 ms 46844 KB Output is correct
10 Correct 73 ms 46736 KB Output is correct
11 Correct 75 ms 46616 KB Output is correct
12 Correct 73 ms 48224 KB Output is correct
13 Correct 73 ms 47876 KB Output is correct
14 Correct 77 ms 47608 KB Output is correct
15 Correct 78 ms 48288 KB Output is correct
16 Correct 85 ms 48852 KB Output is correct
17 Correct 76 ms 48960 KB Output is correct
18 Correct 78 ms 49276 KB Output is correct
19 Correct 86 ms 52548 KB Output is correct
20 Correct 77 ms 52452 KB Output is correct
21 Correct 77 ms 52228 KB Output is correct
22 Correct 13 ms 25204 KB Output is correct
23 Correct 12 ms 25172 KB Output is correct
24 Correct 13 ms 25220 KB Output is correct
25 Correct 12 ms 25172 KB Output is correct
26 Correct 12 ms 25172 KB Output is correct

Subtask #2
36.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 25172 KB Output is correct
2 Correct 11 ms 25156 KB Output is correct
3 Correct 12 ms 25300 KB Output is correct
4 Correct 12 ms 25356 KB Output is correct
5 Correct 367 ms 108904 KB Output is correct
6 Correct 274 ms 109004 KB Output is correct
7 Correct 392 ms 109052 KB Output is correct
8 Correct 305 ms 108984 KB Output is correct
9 Correct 330 ms 108912 KB Output is correct
10 Correct 143 ms 109004 KB Output is correct
11 Correct 146 ms 109104 KB Output is correct
12 Correct 140 ms 108952 KB Output is correct
13 Correct 169 ms 109004 KB Output is correct
14 Correct 147 ms 109120 KB Output is correct
15 Correct 318 ms 108980 KB Output is correct
16 Correct 363 ms 109048 KB Output is correct
17 Correct 319 ms 109004 KB Output is correct
18 Correct 150 ms 109128 KB Output is correct
19 Correct 156 ms 109116 KB Output is correct
20 Correct 143 ms 109068 KB Output is correct
21 Correct 146 ms 109124 KB Output is correct
22 Correct 140 ms 109412 KB Output is correct
23 Correct 145 ms 109316 KB Output is correct
24 Correct 144 ms 109388 KB Output is correct
25 Correct 1046 ms 197464 KB Output is correct

Subtask #3
41.0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 25172 KB Output is correct
2 Correct 14 ms 25172 KB Output is correct
3 Correct 72 ms 46632 KB Output is correct
4 Correct 72 ms 46628 KB Output is correct
5 Correct 72 ms 46660 KB Output is correct
6 Correct 89 ms 46556 KB Output is correct
7 Correct 92 ms 46708 KB Output is correct
8 Correct 81 ms 46772 KB Output is correct
9 Correct 72 ms 46844 KB Output is correct
10 Correct 73 ms 46736 KB Output is correct
11 Correct 75 ms 46616 KB Output is correct
12 Correct 73 ms 48224 KB Output is correct
13 Correct 73 ms 47876 KB Output is correct
14 Correct 77 ms 47608 KB Output is correct
15 Correct 78 ms 48288 KB Output is correct
16 Correct 85 ms 48852 KB Output is correct
17 Correct 76 ms 48960 KB Output is correct
18 Correct 78 ms 49276 KB Output is correct
19 Correct 86 ms 52548 KB Output is correct
20 Correct 77 ms 52452 KB Output is correct
21 Correct 77 ms 52228 KB Output is correct
22 Correct 13 ms 25204 KB Output is correct
23 Correct 12 ms 25172 KB Output is correct
24 Correct 13 ms 25220 KB Output is correct
25 Correct 12 ms 25172 KB Output is correct
26 Correct 12 ms 25172 KB Output is correct
27 Correct 11 ms 25172 KB Output is correct
28 Correct 11 ms 25156 KB Output is correct
29 Correct 12 ms 25300 KB Output is correct
30 Correct 12 ms 25356 KB Output is correct
31 Correct 367 ms 108904 KB Output is correct
32 Correct 274 ms 109004 KB Output is correct
33 Correct 392 ms 109052 KB Output is correct
34 Correct 305 ms 108984 KB Output is correct
35 Correct 330 ms 108912 KB Output is correct
36 Correct 143 ms 109004 KB Output is correct
37 Correct 146 ms 109104 KB Output is correct
38 Correct 140 ms 108952 KB Output is correct
39 Correct 169 ms 109004 KB Output is correct
40 Correct 147 ms 109120 KB Output is correct
41 Correct 318 ms 108980 KB Output is correct
42 Correct 363 ms 109048 KB Output is correct
43 Correct 319 ms 109004 KB Output is correct
44 Correct 150 ms 109128 KB Output is correct
45 Correct 156 ms 109116 KB Output is correct
46 Correct 143 ms 109068 KB Output is correct
47 Correct 146 ms 109124 KB Output is correct
48 Correct 140 ms 109412 KB Output is correct
49 Correct 145 ms 109316 KB Output is correct
50 Correct 144 ms 109388 KB Output is correct
51 Correct 1046 ms 197464 KB Output is correct
52 Correct 1128 ms 257632 KB Output is correct
53 Correct 1133 ms 257908 KB Output is correct
54 Correct 1130 ms 256196 KB Output is correct
55 Correct 1113 ms 255384 KB Output is correct
56 Correct 1133 ms 256344 KB Output is correct
57 Correct 1125 ms 257444 KB Output is correct
58 Correct 14 ms 25124 KB Output is correct
59 Correct 11 ms 25172 KB Output is correct
60 Correct 19 ms 25220 KB Output is correct
61 Correct 1158 ms 257672 KB Output is correct
62 Correct 1262 ms 273880 KB Output is correct
63 Correct 1166 ms 264140 KB Output is correct
64 Correct 86 ms 49620 KB Output is correct
65 Correct 88 ms 49756 KB Output is correct
66 Correct 1167 ms 257816 KB Output is correct
67 Correct 1175 ms 257516 KB Output is correct
68 Correct 1450 ms 335952 KB Output is correct
69 Correct 1307 ms 336528 KB Output is correct
70 Correct 1309 ms 335816 KB Output is correct
71 Correct 1407 ms 335852 KB Output is correct
72 Correct 1346 ms 335952 KB Output is correct
73 Correct 1199 ms 337096 KB Output is correct
74 Correct 1209 ms 337756 KB Output is correct
75 Correct 1239 ms 337568 KB Output is correct
76 Correct 1180 ms 338400 KB Output is correct
77 Correct 1219 ms 337204 KB Output is correct
78 Correct 1544 ms 343452 KB Output is correct
79 Correct 1459 ms 343084 KB Output is correct
80 Correct 1311 ms 341976 KB Output is correct
81 Correct 1367 ms 355076 KB Output is correct
82 Correct 1437 ms 356404 KB Output is correct
83 Correct 1362 ms 356192 KB Output is correct
84 Correct 1488 ms 365112 KB Output is correct
85 Correct 1578 ms 395568 KB Output is correct
86 Correct 1717 ms 394576 KB Output is correct
87 Correct 1630 ms 394604 KB Output is correct