oj.uz

Submission #1043218

# Submission time Handle Problem Language Result Execution time Memory
1043218 2024-08-04T05:00:23 Z javotaz LOSTIKS (INOI20_lostiks) C++17
0 / 100
 51 ms 41872 KB 
// In the Name of Allah

#include<bits/stdc++.h>
using namespace std;

#pragma GCC optimize("Ofast,unroll-loops,fast-math")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,avx,avx2,sse4.2,popcnt,tune=native")

typedef long long ll;

#define F first
#define S second
#define pii pair<int, int>
#define pb push_back
#define pp pop_back
#define all(x) x.begin(), x.end()

const int N = 1e6 + 12, M = 20;
vector<pii> g[N];
int n, s, t, h[N], f[N][M];
pii par[N];
vector<int> v[M + 3];
bool don[N], op[N];

void ip() {
	cin >> n >> s >> t;
	for (int i = 1; i < n; i++) {
		int u, v, w;
		cin >> u >> v >> w;
		g[u].pb({v, w});
		g[v].pb({u, w});
	}
}

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

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

int dfs(int a, int b, int c = 0) {
	if (don[b] == true) {
		cout << -1;
		exit(0);
	}
	don[b] = true;
	v[c].pb(a);
	par[a] = {a, 0};
	while (!v[c].empty()) {
		int u = v[c].back();
		v[c].pp();
		for (auto i: g[u])
			if (i.F != par[u].F)
				v[c].pb(i.F), par[i.F] = {u, i.S};
	}
	int u = b;
	vector<pii> d;
	while (u != a) {
		d.pb(par[u]);
		u = par[u].F;
	}
	reverse(all(d));
	int ans = 0;
	int pl = a;
	for (auto i: d) 
		if (i.S && !op[i.S]) {
			ans += dfs(pl, i.S, c + 1);
			ans += dis(i.S, i.F);
			pl = i.F;
		}
	ans += dis(pl, b);
	don[b] = false;
	op[b] = true;
	return ans;
}

void dfs1(int u) {
	for (auto i: g[u])
		if (i.F != f[u][0]) {
			f[i.F][0] = u;
			h[i.F] = h[u] + 1;
			for (int j = 1; j < M; ++j)
				f[i.F][j] = f[f[i.F][j - 1]][j - 1];
			dfs1(i.F);
		}
}

void solve() {
	for (int i = 0; i < M; i++)
		f[1][i] = 1;
	dfs1(1);
	cout << dfs(s, t);
}

int32_t main() {
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	ip(), solve();
	return 0;
}

Subtask #1
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 25436 KB Output is correct
2 Correct 5 ms 25444 KB Output is correct
3 Correct 37 ms 39508 KB Output is correct
4 Correct 44 ms 39764 KB Output is correct
5 Correct 41 ms 39764 KB Output is correct
6 Correct 42 ms 39512 KB Output is correct
7 Correct 51 ms 39752 KB Output is correct
8 Correct 48 ms 39764 KB Output is correct
9 Correct 50 ms 40016 KB Output is correct
10 Correct 51 ms 39760 KB Output is correct
11 Correct 48 ms 39768 KB Output is correct
12 Correct 44 ms 40528 KB Output is correct
13 Incorrect 44 ms 41872 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #2
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 25432 KB Output is correct
2 Correct 5 ms 25436 KB Output is correct
3 Incorrect 5 ms 25440 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 25436 KB Output is correct
2 Correct 5 ms 25444 KB Output is correct
3 Correct 37 ms 39508 KB Output is correct
4 Correct 44 ms 39764 KB Output is correct
5 Correct 41 ms 39764 KB Output is correct
6 Correct 42 ms 39512 KB Output is correct
7 Correct 51 ms 39752 KB Output is correct
8 Correct 48 ms 39764 KB Output is correct
9 Correct 50 ms 40016 KB Output is correct
10 Correct 51 ms 39760 KB Output is correct
11 Correct 48 ms 39768 KB Output is correct
12 Correct 44 ms 40528 KB Output is correct
13 Incorrect 44 ms 41872 KB Output isn't correct
14 Halted 0 ms 0 KB -