oj.uz

Submission #1025204

# Submission time Handle Problem Language Result Execution time Memory
1025204 2024-07-16T17:32:23 Z Amirreza_Fakhri LOSTIKS (INOI20_lostiks) C++17
36 / 100
 574 ms 126288 KB 
// In the name of the God
#include <bits/stdc++.h>
#define ll long long
//#define int long long
#define pb push_back
#define F first
#define S second
#define mp make_pair
#define pii pair <int, int>
#define smin(x, y) (x) = min((x), (y))
#define smax(x, y) (x) = max((x), (y))
#define all(x) (x).begin(), (x).end()
using namespace std;

//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx2")

const int inf = 1e9+7;
const int mod = 998244353;
const int maxn = 1e6+5, lg = 20;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int n, m, s, t, ti = 0, h[maxn], in[maxn], out[maxn], par[maxn][lg], dist[lg][lg], ne[lg][lg], dp[1<<lg][lg];
vector <int> adj[maxn];
vector <pair <pii, int>> g;

void dfs(int v, int p) {
	par[v][0] = p;
	for (int i = 1; i < lg; i++) par[v][i] = par[par[v][i-1]][i-1];
	in[v] = ti++;
	for (int u : adj[v]) {
		if (u == p) continue;
		h[u] = h[v]+1;
		dfs(u, v);
	}
	out[v] = ti;
}

int lca(int v, int u) {
	if (h[v] < h[u]) swap(v, u);
	int x = h[v]-h[u];
	for (int i = 0; i < lg; i++) {
		if (x&(1<<i)) v = par[v][i];
	}
	if (v == u) return v;
	for (int i = lg-1; i >= 0; i--) {
		if (par[v][i] != par[u][i]) v = par[v][i], u = par[u][i];
	}
	return par[v][0];
}

int d(int v, int u) {
	int z = lca(u, v);
	return h[v]+h[u]-h[z]*2;
}

bool isd(int v, int u) {
	return in[v] <= in[u] and out[v] >= out[u];
}

int f(int v, int u) {
	int res = 0, z = lca(u, v);
	for (int i = 0; i < m; i++) {
		int x = g[i].F.F, y = g[i].F.S;
		bool f = 0;
		f = (isd(y, v)&isd(z, x))|(isd(y, u)&isd(z, x));
		if (f) res += 1<<i;
	}
	return res;
}

int32_t main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> s >> t; s--, t--;
    for (int i = 1; i < n; i++) {
    	int v, u, w; cin >> v >> u >> w; v--, u--, w--;
    	adj[v].pb(u), adj[u].pb(v);
    	if (w != -1) g.pb(mp(mp(v, u), w));
	}
	m = g.size();
	dfs(s, s);
	for (auto &p : g) if (h[p.F.F] > h[p.F.S]) swap(p.F.F, p.F.S);
	for (int i = 0; i < m; i++) {
		for (int j = 0; j < m; j++) {
			dist[i][j] = d(g[i].F.F, g[j].S);
			ne[i][j] = f(g[i].F.F, g[j].S);
		}
	}
	memset(dp, 63, sizeof dp);
	for (int i = 0; i < m; i++) {
		if (f(s, g[i].S) == 0 and f(g[i].S	, g[i].F.F) == 0) dp[1<<i][i] = d(s, g[i].S)+d(g[i].S, g[i].F.F);
	}
	for (int i = 0; i < (1<<m); i++) {
		for (int j = 0; j < m; j++) {
			if (i&(1<<j)) {
				for (int k = 0; k < m; k++) {
					if (!(i&(1<<k))) {
						if ((ne[j][k]|i) == i and (ne[k][k]|i) == i) smin(dp[i+(1<<k)][k], dp[i][j]+dist[j][k]+dist[k][k]);
					}
				}
			}
		}
	}
	if (s == t) return cout << 0 << '\n', 0;
	int ali = 1, p = t;
	while (p != s) {
		for (int i = 0; i < m; i++) {
			if (g[i].F.S == p) {
				ali = i;
				goto TH;
			}
		}
		p = par[p][0];
	}
	TH:;
	if (ali == -1) return cout << d(s, t) << '\n', 0;
	int amir = d(g[ali].F.F, t), ans = inf*2;
	for (int i = 0; i < (1<<m); i++) smin(ans, amir+dp[i][ali]);
	cout << ans << '\n';
    return 0;
}












/*
srand(time(0));
cout << (rand()%1900) + 1 << ' ' << (rand()%2)+5 << '\n';
*/

Subtask #1
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 111448 KB Output is correct
2 Correct 15 ms 111464 KB Output is correct
3 Correct 46 ms 124504 KB Output is correct
4 Correct 46 ms 124500 KB Output is correct
5 Correct 52 ms 124756 KB Output is correct
6 Correct 48 ms 124500 KB Output is correct
7 Correct 53 ms 124836 KB Output is correct
8 Correct 50 ms 124752 KB Output is correct
9 Correct 50 ms 124796 KB Output is correct
10 Correct 48 ms 124756 KB Output is correct
11 Correct 50 ms 124704 KB Output is correct
12 Correct 53 ms 126288 KB Output is correct
13 Correct 52 ms 125776 KB Output is correct
14 Correct 53 ms 125524 KB Output is correct
15 Incorrect 52 ms 126288 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #2
36.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 111288 KB Output is correct
2 Correct 15 ms 111424 KB Output is correct
3 Correct 15 ms 111452 KB Output is correct
4 Correct 15 ms 111428 KB Output is correct
5 Correct 322 ms 111736 KB Output is correct
6 Correct 307 ms 111776 KB Output is correct
7 Correct 318 ms 111704 KB Output is correct
8 Correct 312 ms 111952 KB Output is correct
9 Correct 324 ms 111704 KB Output is correct
10 Correct 298 ms 111784 KB Output is correct
11 Correct 277 ms 111708 KB Output is correct
12 Correct 290 ms 111788 KB Output is correct
13 Correct 288 ms 111708 KB Output is correct
14 Correct 280 ms 111708 KB Output is correct
15 Correct 296 ms 111800 KB Output is correct
16 Correct 294 ms 111704 KB Output is correct
17 Correct 295 ms 111712 KB Output is correct
18 Correct 279 ms 111764 KB Output is correct
19 Correct 271 ms 111708 KB Output is correct
20 Correct 289 ms 111928 KB Output is correct
21 Correct 269 ms 111960 KB Output is correct
22 Correct 279 ms 111964 KB Output is correct
23 Correct 272 ms 111960 KB Output is correct
24 Correct 271 ms 111964 KB Output is correct
25 Correct 574 ms 111452 KB Output is correct

Subtask #3
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 111448 KB Output is correct
2 Correct 15 ms 111464 KB Output is correct
3 Correct 46 ms 124504 KB Output is correct
4 Correct 46 ms 124500 KB Output is correct
5 Correct 52 ms 124756 KB Output is correct
6 Correct 48 ms 124500 KB Output is correct
7 Correct 53 ms 124836 KB Output is correct
8 Correct 50 ms 124752 KB Output is correct
9 Correct 50 ms 124796 KB Output is correct
10 Correct 48 ms 124756 KB Output is correct
11 Correct 50 ms 124704 KB Output is correct
12 Correct 53 ms 126288 KB Output is correct
13 Correct 52 ms 125776 KB Output is correct
14 Correct 53 ms 125524 KB Output is correct
15 Incorrect 52 ms 126288 KB Output isn't correct
16 Halted 0 ms 0 KB -