oj.uz

Submission #1043234

# Submission time Handle Problem Language Result Execution time Memory
1043234 2024-08-04T05:21:17 Z javotaz LOSTIKS (INOI20_lostiks) C++17
0 / 100
 73 ms 41136 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 = 22;
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 10 ms 23900 KB Output is correct
2 Correct 10 ms 23952 KB Output is correct
3 Correct 65 ms 38992 KB Output is correct
4 Correct 62 ms 39000 KB Output is correct
5 Correct 59 ms 38944 KB Output is correct
6 Correct 54 ms 38868 KB Output is correct
7 Correct 64 ms 39148 KB Output is correct
8 Correct 58 ms 38980 KB Output is correct
9 Correct 73 ms 39180 KB Output is correct
10 Correct 52 ms 39176 KB Output is correct
11 Correct 66 ms 39008 KB Output is correct
12 Correct 65 ms 39788 KB Output is correct
13 Incorrect 57 ms 41136 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #2
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 23980 KB Output is correct
2 Correct 10 ms 23900 KB Output is correct
3 Incorrect 9 ms 23972 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 23900 KB Output is correct
2 Correct 10 ms 23952 KB Output is correct
3 Correct 65 ms 38992 KB Output is correct
4 Correct 62 ms 39000 KB Output is correct
5 Correct 59 ms 38944 KB Output is correct
6 Correct 54 ms 38868 KB Output is correct
7 Correct 64 ms 39148 KB Output is correct
8 Correct 58 ms 38980 KB Output is correct
9 Correct 73 ms 39180 KB Output is correct
10 Correct 52 ms 39176 KB Output is correct
11 Correct 66 ms 39008 KB Output is correct
12 Correct 65 ms 39788 KB Output is correct
13 Incorrect 57 ms 41136 KB Output isn't correct
14 Halted 0 ms 0 KB -