oj.uz

Submission #789116

# Submission time Handle Problem Language Result Execution time Memory
789116 2023-07-21T05:14:18 Z MISM06 LOSTIKS (INOI20_lostiks) C++17
0 / 100
 2000 ms 47288 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;

int 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);
	}
	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 + 1; 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 12 ms 25084 KB Output is correct
2 Correct 11 ms 25100 KB Output is correct
3 Correct 65 ms 38976 KB Output is correct
4 Correct 63 ms 38976 KB Output is correct
5 Correct 62 ms 39004 KB Output is correct
6 Correct 66 ms 38980 KB Output is correct
7 Correct 64 ms 38968 KB Output is correct
8 Correct 64 ms 39000 KB Output is correct
9 Correct 64 ms 39168 KB Output is correct
10 Correct 66 ms 39064 KB Output is correct
11 Correct 63 ms 39044 KB Output is correct
12 Correct 69 ms 40448 KB Output is correct
13 Correct 67 ms 40248 KB Output is correct
14 Correct 65 ms 39884 KB Output is correct
15 Incorrect 74 ms 40652 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 25172 KB Output is correct
2 Correct 12 ms 25120 KB Output is correct
3 Correct 17 ms 25300 KB Output is correct
4 Correct 16 ms 25300 KB Output is correct
5 Execution timed out 2059 ms 47288 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 25084 KB Output is correct
2 Correct 11 ms 25100 KB Output is correct
3 Correct 65 ms 38976 KB Output is correct
4 Correct 63 ms 38976 KB Output is correct
5 Correct 62 ms 39004 KB Output is correct
6 Correct 66 ms 38980 KB Output is correct
7 Correct 64 ms 38968 KB Output is correct
8 Correct 64 ms 39000 KB Output is correct
9 Correct 64 ms 39168 KB Output is correct
10 Correct 66 ms 39064 KB Output is correct
11 Correct 63 ms 39044 KB Output is correct
12 Correct 69 ms 40448 KB Output is correct
13 Correct 67 ms 40248 KB Output is correct
14 Correct 65 ms 39884 KB Output is correct
15 Incorrect 74 ms 40652 KB Output isn't correct
16 Halted 0 ms 0 KB -