oj.uz

Submission #789552

# Submission time Handle Problem Language Result Execution time Memory
789552 2023-07-21T13:34:01 Z MISM06 LOSTIKS (INOI20_lostiks) C++14
0 / 100
 92 ms 48004 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 ((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;
				if (be_anc(lc[i].S.F, rid[v]) && lc[i].S.F != rid[v]) {
					dp[v][mask] = inf;
					break;
				}
				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 13 ms 25176 KB Output is correct
2 Correct 14 ms 25172 KB Output is correct
3 Correct 78 ms 47948 KB Output is correct
4 Correct 80 ms 48000 KB Output is correct
5 Correct 92 ms 48000 KB Output is correct
6 Incorrect 76 ms 48004 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 25172 KB Output is correct
2 Correct 13 ms 25172 KB Output is correct
3 Correct 15 ms 25300 KB Output is correct
4 Incorrect 16 ms 25236 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 25176 KB Output is correct
2 Correct 14 ms 25172 KB Output is correct
3 Correct 78 ms 47948 KB Output is correct
4 Correct 80 ms 48000 KB Output is correct
5 Correct 92 ms 48000 KB Output is correct
6 Incorrect 76 ms 48004 KB Output isn't correct
7 Halted 0 ms 0 KB -