oj.uz

Submission #789118

# Submission time Handle Problem Language Result Execution time Memory
789118 2023-07-21T05:28:36 Z MISM06 LOSTIKS (INOI20_lostiks) C++14
0 / 100
 2000 ms 64924 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;
}
bool be_anc (int v, int u) {
	return (st[v] <= st[u] && en[v] >= en[u]);
}
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];
}
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;
}
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;
				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 11 ms 25172 KB Output is correct
2 Correct 12 ms 25172 KB Output is correct
3 Correct 88 ms 46644 KB Output is correct
4 Correct 74 ms 46584 KB Output is correct
5 Correct 73 ms 46664 KB Output is correct
6 Correct 78 ms 46552 KB Output is correct
7 Correct 72 ms 46684 KB Output is correct
8 Correct 72 ms 46716 KB Output is correct
9 Correct 73 ms 46748 KB Output is correct
10 Correct 71 ms 46728 KB Output is correct
11 Correct 74 ms 46700 KB Output is correct
12 Correct 96 ms 48228 KB Output is correct
13 Correct 72 ms 47920 KB Output is correct
14 Correct 72 ms 47584 KB Output is correct
15 Incorrect 86 ms 48320 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #2
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 25168 KB Output is correct
2 Correct 11 ms 25080 KB Output is correct
3 Correct 13 ms 25244 KB Output is correct
4 Correct 13 ms 25300 KB Output is correct
5 Execution timed out 2069 ms 64924 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 25172 KB Output is correct
2 Correct 12 ms 25172 KB Output is correct
3 Correct 88 ms 46644 KB Output is correct
4 Correct 74 ms 46584 KB Output is correct
5 Correct 73 ms 46664 KB Output is correct
6 Correct 78 ms 46552 KB Output is correct
7 Correct 72 ms 46684 KB Output is correct
8 Correct 72 ms 46716 KB Output is correct
9 Correct 73 ms 46748 KB Output is correct
10 Correct 71 ms 46728 KB Output is correct
11 Correct 74 ms 46700 KB Output is correct
12 Correct 96 ms 48228 KB Output is correct
13 Correct 72 ms 47920 KB Output is correct
14 Correct 72 ms 47584 KB Output is correct
15 Incorrect 86 ms 48320 KB Output isn't correct
16 Halted 0 ms 0 KB -