oj.uz

Submission #999181

# Submission time Handle Problem Language Result Execution time Memory
999181 2024-06-15T07:52:53 Z vjudge1 LOSTIKS (INOI20_lostiks) C++17
23 / 100
 2000 ms 101716 KB 
#include <bits/stdc++.h>

using namespace std;

#define int long long
#define inf 0x3F3F3F3F3F3F3F3F

struct DSU
{
	vector<int> e;
	void init(int n)
	{
		e.assign(n + 1, -1);
	}
	int get(int x)
	{
		if (e[x] < 0) return x;
		return e[x] = get(e[x]);
	}
	void unite(int x, int y)
	{
		x = get(x), y = get(y);
		if (x == y) return;
		if (e[x] > e[y]) swap(x, y);
		e[x] += e[y];
		e[y] = x;
	}
};

const int MXN = 1e6 + 5;
const int LOG = 20;

int n, S, T, A, B, b = 0;
vector<int> adj[MXN];
int p[LOG][MXN], dep[MXN], in[MXN], out[MXN], tim;
int id[MXN];

void dfs(int a)
{
	in[a] = ++tim;
	for (int &v : adj[a])
	{
		if (v == p[0][a]) continue;
		p[0][v] = a;
		dep[v] = dep[a] + 1;
		dfs(v);
	}
	out[a] = tim;
}

vector<array<int, 3>> m;

int anc(int u, int v)
{
	return in[u] <= in[v] && out[v] <= out[u];
}
int LCA(int u, int v)
{
	if (anc(u, v)) return u;
	if (anc(v, u)) return v;
	for (int i = LOG - 1; i >= 0; i--)
	{
		if (anc(p[i][u], v)) continue;
		u = p[i][u];
	}
	return p[0][u];
}
int DIST(int u, int v)
{
	return dep[u] + dep[v] - 2 * dep[LCA(u, v)];
}

signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> S >> T;
	DSU dsu;
	dsu.init(n);
	for (int i = 1; i < n; i++)
	{
		int u, v, w;
		cin >> u >> v >> w;
		adj[u].push_back(v);
		adj[v].push_back(u);
		if (!w) dsu.unite(u, v);
		else m.push_back({u, v, w});
	}
	p[0][S] = S;
	dfs(S);
	for (array<int, 3> &i : m) if (p[0][i[0]] == i[1]) swap(i[0], i[1]);
	A = dsu.get(S), B = dsu.get(T);
	int ASD = 0;
	for (int i = 1; i <= n; i++)
	{
		if (dsu.get(i) == i) id[i] = ++ASD;
	}
	for (int i = 1; i < LOG; i++) for (int j = 1; j <= n; j++) p[i][j] = p[i - 1][p[i - 1][j]];
	vector<int> o(m.size());
	iota(o.begin(), o.end(), 0);
	int res = inf;
	while (1)
	{
		DSU d;
		d.init(ASD);
		int f = 1, cur = S, ans = 0;
		for (int &i : o)
		{
			if (d.get(id[A]) == d.get(id[B])) break;
			if (d.get(id[dsu.get(m[i][0])]) != d.get(id[A]) || d.get(id[dsu.get(m[i][2])]) != d.get(id[A]))
			{
				f = 0;
				break;
			}
			d.unite(id[dsu.get(m[i][1])], id[A]);
			ans += DIST(cur, m[i][2]) + DIST(m[i][2], m[i][0]);
			cur = m[i][0];
		}
		if (f && d.get(id[A]) == d.get(id[B])) 
		{
			res = min(res, ans + DIST(cur, T));
		}
		if (!next_permutation(o.begin(), o.end())) break;
	}
	cout << (res >= inf ? -1 : res) << '\n';
}

Subtask #1
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 61788 KB Output is correct
2 Correct 10 ms 61788 KB Output is correct
3 Correct 69 ms 78164 KB Output is correct
4 Correct 45 ms 48980 KB Output is correct
5 Correct 72 ms 48884 KB Output is correct
6 Correct 53 ms 57424 KB Output is correct
7 Correct 48 ms 97836 KB Output is correct
8 Correct 45 ms 97724 KB Output is correct
9 Correct 79 ms 97880 KB Output is correct
10 Correct 45 ms 97736 KB Output is correct
11 Correct 44 ms 97876 KB Output is correct
12 Correct 44 ms 98388 KB Output is correct
13 Correct 39 ms 98192 KB Output is correct
14 Correct 38 ms 97876 KB Output is correct
15 Correct 40 ms 98388 KB Output is correct
16 Correct 42 ms 98912 KB Output is correct
17 Correct 41 ms 99068 KB Output is correct
18 Correct 41 ms 99204 KB Output is correct
19 Correct 62 ms 101716 KB Output is correct
20 Correct 62 ms 101460 KB Output is correct
21 Correct 46 ms 101500 KB Output is correct
22 Correct 9 ms 67932 KB Output is correct
23 Correct 9 ms 67956 KB Output is correct
24 Correct 9 ms 67932 KB Output is correct
25 Correct 12 ms 67808 KB Output is correct
26 Correct 9 ms 67932 KB Output is correct

Subtask #2
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 67932 KB Output is correct
2 Correct 10 ms 67928 KB Output is correct
3 Correct 194 ms 67932 KB Output is correct
4 Correct 214 ms 67928 KB Output is correct
5 Execution timed out 2079 ms 70492 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 61788 KB Output is correct
2 Correct 10 ms 61788 KB Output is correct
3 Correct 69 ms 78164 KB Output is correct
4 Correct 45 ms 48980 KB Output is correct
5 Correct 72 ms 48884 KB Output is correct
6 Correct 53 ms 57424 KB Output is correct
7 Correct 48 ms 97836 KB Output is correct
8 Correct 45 ms 97724 KB Output is correct
9 Correct 79 ms 97880 KB Output is correct
10 Correct 45 ms 97736 KB Output is correct
11 Correct 44 ms 97876 KB Output is correct
12 Correct 44 ms 98388 KB Output is correct
13 Correct 39 ms 98192 KB Output is correct
14 Correct 38 ms 97876 KB Output is correct
15 Correct 40 ms 98388 KB Output is correct
16 Correct 42 ms 98912 KB Output is correct
17 Correct 41 ms 99068 KB Output is correct
18 Correct 41 ms 99204 KB Output is correct
19 Correct 62 ms 101716 KB Output is correct
20 Correct 62 ms 101460 KB Output is correct
21 Correct 46 ms 101500 KB Output is correct
22 Correct 9 ms 67932 KB Output is correct
23 Correct 9 ms 67956 KB Output is correct
24 Correct 9 ms 67932 KB Output is correct
25 Correct 12 ms 67808 KB Output is correct
26 Correct 9 ms 67932 KB Output is correct
27 Correct 9 ms 67932 KB Output is correct
28 Correct 10 ms 67928 KB Output is correct
29 Correct 194 ms 67932 KB Output is correct
30 Correct 214 ms 67928 KB Output is correct
31 Execution timed out 2079 ms 70492 KB Time limit exceeded
32 Halted 0 ms 0 KB -