oj.uz

Submission #789117

# Submission time Handle Problem Language Result Execution time Memory
789117 2023-07-21T05:26:25 Z MISM06 LOSTIKS (INOI20_lostiks) C++17
0 / 100
 2000 ms 65988 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 (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 14 ms 25092 KB Output is correct
3 Correct 74 ms 46648 KB Output is correct
4 Correct 72 ms 46584 KB Output is correct
5 Correct 72 ms 46556 KB Output is correct
6 Correct 84 ms 46624 KB Output is correct
7 Correct 72 ms 46620 KB Output is correct
8 Correct 71 ms 46636 KB Output is correct
9 Correct 72 ms 46812 KB Output is correct
10 Correct 72 ms 46684 KB Output is correct
11 Correct 72 ms 46640 KB Output is correct
12 Correct 83 ms 48232 KB Output is correct
13 Correct 73 ms 47828 KB Output is correct
14 Correct 80 ms 47580 KB Output is correct
15 Incorrect 71 ms 48264 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #2
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 25060 KB Output is correct
2 Correct 13 ms 25172 KB Output is correct
3 Correct 17 ms 25300 KB Output is correct
4 Correct 14 ms 25220 KB Output is correct
5 Execution timed out 2082 ms 65988 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 14 ms 25092 KB Output is correct
3 Correct 74 ms 46648 KB Output is correct
4 Correct 72 ms 46584 KB Output is correct
5 Correct 72 ms 46556 KB Output is correct
6 Correct 84 ms 46624 KB Output is correct
7 Correct 72 ms 46620 KB Output is correct
8 Correct 71 ms 46636 KB Output is correct
9 Correct 72 ms 46812 KB Output is correct
10 Correct 72 ms 46684 KB Output is correct
11 Correct 72 ms 46640 KB Output is correct
12 Correct 83 ms 48232 KB Output is correct
13 Correct 73 ms 47828 KB Output is correct
14 Correct 80 ms 47580 KB Output is correct
15 Incorrect 71 ms 48264 KB Output isn't correct
16 Halted 0 ms 0 KB -