oj.uz

Submission #789554

# Submission time Handle Problem Language Result Execution time Memory
789554 2023-07-21T13:35:57 Z MISM06 LOSTIKS (INOI20_lostiks) C++14
0 / 100
 2000 ms 72336 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]));
				}
			}
		}
	}
	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
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 25132 KB Output is correct
2 Correct 13 ms 25172 KB Output is correct
3 Correct 75 ms 47072 KB Output is correct
4 Correct 75 ms 47164 KB Output is correct
5 Correct 85 ms 47120 KB Output is correct
6 Correct 75 ms 47156 KB Output is correct
7 Correct 88 ms 48008 KB Output is correct
8 Correct 76 ms 48068 KB Output is correct
9 Correct 84 ms 48120 KB Output is correct
10 Correct 78 ms 47976 KB Output is correct
11 Correct 77 ms 48020 KB Output is correct
12 Correct 78 ms 49464 KB Output is correct
13 Correct 87 ms 49264 KB Output is correct
14 Correct 85 ms 48852 KB Output is correct
15 Incorrect 84 ms 49612 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #2
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 25088 KB Output is correct
2 Correct 13 ms 25172 KB Output is correct
3 Correct 14 ms 25300 KB Output is correct
4 Correct 16 ms 25220 KB Output is correct
5 Execution timed out 2072 ms 72336 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 25132 KB Output is correct
2 Correct 13 ms 25172 KB Output is correct
3 Correct 75 ms 47072 KB Output is correct
4 Correct 75 ms 47164 KB Output is correct
5 Correct 85 ms 47120 KB Output is correct
6 Correct 75 ms 47156 KB Output is correct
7 Correct 88 ms 48008 KB Output is correct
8 Correct 76 ms 48068 KB Output is correct
9 Correct 84 ms 48120 KB Output is correct
10 Correct 78 ms 47976 KB Output is correct
11 Correct 77 ms 48020 KB Output is correct
12 Correct 78 ms 49464 KB Output is correct
13 Correct 87 ms 49264 KB Output is correct
14 Correct 85 ms 48852 KB Output is correct
15 Incorrect 84 ms 49612 KB Output isn't correct
16 Halted 0 ms 0 KB -