oj.uz

Submission #789557

# Submission time Handle Problem Language Result Execution time Memory
789557 2023-07-21T13:38:43 Z MISM06 LOSTIKS (INOI20_lostiks) C++14
23 / 100
 2000 ms 74004 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];
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;
}
inline ll dis (int v, int u) {
	return h[v] + h[u] - (2 * h[lca(v, u)]);
}
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);
			}
		}
	}
	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(rid[v], 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(rid[v], w) + dis(w, rid[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 12 ms 25128 KB Output is correct
3 Correct 71 ms 46540 KB Output is correct
4 Correct 73 ms 46588 KB Output is correct
5 Correct 73 ms 46652 KB Output is correct
6 Correct 71 ms 46540 KB Output is correct
7 Correct 80 ms 46716 KB Output is correct
8 Correct 77 ms 46716 KB Output is correct
9 Correct 75 ms 46828 KB Output is correct
10 Correct 74 ms 46728 KB Output is correct
11 Correct 75 ms 46616 KB Output is correct
12 Correct 73 ms 48204 KB Output is correct
13 Correct 82 ms 47884 KB Output is correct
14 Correct 75 ms 47600 KB Output is correct
15 Correct 74 ms 48356 KB Output is correct
16 Correct 81 ms 50252 KB Output is correct
17 Correct 76 ms 50264 KB Output is correct
18 Correct 77 ms 50640 KB Output is correct
19 Correct 86 ms 53884 KB Output is correct
20 Correct 80 ms 53772 KB Output is correct
21 Correct 78 ms 53560 KB Output is correct
22 Correct 13 ms 25128 KB Output is correct
23 Correct 12 ms 25172 KB Output is correct
24 Correct 13 ms 25172 KB Output is correct
25 Correct 13 ms 25132 KB Output is correct
26 Correct 13 ms 25172 KB Output is correct

Subtask #2
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 25172 KB Output is correct
2 Correct 11 ms 25068 KB Output is correct
3 Correct 14 ms 25244 KB Output is correct
4 Correct 13 ms 25216 KB Output is correct
5 Execution timed out 2090 ms 74004 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 25172 KB Output is correct
2 Correct 12 ms 25128 KB Output is correct
3 Correct 71 ms 46540 KB Output is correct
4 Correct 73 ms 46588 KB Output is correct
5 Correct 73 ms 46652 KB Output is correct
6 Correct 71 ms 46540 KB Output is correct
7 Correct 80 ms 46716 KB Output is correct
8 Correct 77 ms 46716 KB Output is correct
9 Correct 75 ms 46828 KB Output is correct
10 Correct 74 ms 46728 KB Output is correct
11 Correct 75 ms 46616 KB Output is correct
12 Correct 73 ms 48204 KB Output is correct
13 Correct 82 ms 47884 KB Output is correct
14 Correct 75 ms 47600 KB Output is correct
15 Correct 74 ms 48356 KB Output is correct
16 Correct 81 ms 50252 KB Output is correct
17 Correct 76 ms 50264 KB Output is correct
18 Correct 77 ms 50640 KB Output is correct
19 Correct 86 ms 53884 KB Output is correct
20 Correct 80 ms 53772 KB Output is correct
21 Correct 78 ms 53560 KB Output is correct
22 Correct 13 ms 25128 KB Output is correct
23 Correct 12 ms 25172 KB Output is correct
24 Correct 13 ms 25172 KB Output is correct
25 Correct 13 ms 25132 KB Output is correct
26 Correct 13 ms 25172 KB Output is correct
27 Correct 11 ms 25172 KB Output is correct
28 Correct 11 ms 25068 KB Output is correct
29 Correct 14 ms 25244 KB Output is correct
30 Correct 13 ms 25216 KB Output is correct
31 Execution timed out 2090 ms 74004 KB Time limit exceeded
32 Halted 0 ms 0 KB -