Submission #1043234

#	Time	Username	Problem	Language	Result	Execution time	Memory
1043234		javotaz	LOSTIKS (INOI20_lostiks)	C++17	0 / 100	73 ms	41136 KiB

Main

// 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
• Subtask 2: 0 / 36
• Subtask 3: 0 / 41