oj.uz

Submission #999539

# Submission time Handle Problem Language Result Execution time Memory
999539 2024-06-15T17:44:59 Z aykhn LOSTIKS (INOI20_lostiks) C++17
100 / 100
 1132 ms 316784 KB 
#include <bits/stdc++.h>

using namespace std;

#define inf 0x3F3F3F3F

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;
vector<array<int, 2>> adj[MXN];
int p[LOG][MXN], dep[MXN], in[MXN], out[MXN], tim;
int b[MXN], need[MXN];
int dp[20][(1LL << 20)];
vector<array<int, 3>> m;

void dfs(int a)
{
	in[a] = ++tim;
	for (array<int, 2> &v : adj[a])
	{
		if (v[0] == p[0][a]) continue;
		p[0][v[0]] = a;
		dep[v[0]] = dep[a] + 1;
		need[v[0]] = need[a];
		if (v[1])
		{
			int ind = lower_bound(m.begin(), m.end(), array<int, 3> {a, v[0], v[1]}) - m.begin();
			need[v[0]] = need[a] | (1LL << ind);
		}
		dfs(v[0]);
	}
	out[a] = tim;
}

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, w});
		adj[v].push_back({u, w});
		if (w) m.push_back({u, v, w});
		if (!w) dsu.unite(u, v);
	}
	sort(m.begin(), m.end());
	p[0][S] = S;
	dfs(S);
	for (array<int, 3> &i : m) if (p[0][i[0]] == i[1]) swap(i[0], i[1]);
	dfs(S);
	for (int i = 1; i < LOG; i++) for (int j = 1; j <= n; j++) p[i][j] = p[i - 1][p[i - 1][j]];
	for (int i = 0; i < m.size(); i++) for (int j = 0; j < (1LL << (int)m.size()); j++) dp[i][j] = inf;
	for (int i = 0; i < m.size(); i++)
	{
		b[i] = (need[m[i][0]] ^ need[m[i][2]] ^ need[LCA(m[i][0], m[i][2])]);
	}
	if (dsu.get(S) == dsu.get(T)) 
	{
		cout << DIST(S, T) << '\n';
		return 0;
	}
	for (int msk = 1; msk < (1LL << (int)(m.size())); msk++)
	{
		if (__builtin_popcount(msk) == 1)
		for (int i = 0; i < m.size(); i++)
		{
			if (!b[i] && (msk >> i & 1)) 
			{
				dp[i][msk] = DIST(S, m[i][2]) + DIST(m[i][2], m[i][0]);
			}
		}
		for (int i = 0; i < m.size(); i++)
		{
			if (dp[i][msk] >= inf) continue;
			for (int j = 0; j < m.size(); j++)
			{
				if ((msk >> j & 1)) continue;
				if (((msk ^ b[j]) & b[j])) continue;
				dp[j][msk | (1LL << j)] = min(dp[j][msk | (1LL << j)], dp[i][msk] + DIST(m[i][0], m[j][2]) + DIST(m[j][2], m[j][0]));
			}
		}
	}
	int res = inf;
	for (int msk = 1; msk < (1LL << (int)m.size()); msk++)
	{
		for (int i = 0; i < m.size(); i++)
		{
			if (dp[i][msk] >= inf) continue;
			if (((msk ^ need[T]) & need[T])) continue;
			res = min(res, dp[i][msk] + DIST(m[i][0], T));
 		}
	}
	cout << (res >= inf ? -1 : res) << '\n';
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:100:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |  for (int i = 0; i < m.size(); i++) for (int j = 0; j < (1LL << (int)m.size()); j++) dp[i][j] = inf;
      |                  ~~^~~~~~~~~~
Main.cpp:101:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  101 |  for (int i = 0; i < m.size(); i++)
      |                  ~~^~~~~~~~~~
Main.cpp:113:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  113 |   for (int i = 0; i < m.size(); i++)
      |                   ~~^~~~~~~~~~
Main.cpp:120:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  120 |   for (int i = 0; i < m.size(); i++)
      |                   ~~^~~~~~~~~~
Main.cpp:123:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  123 |    for (int j = 0; j < m.size(); j++)
      |                    ~~^~~~~~~~~~
Main.cpp:134:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  134 |   for (int i = 0; i < m.size(); i++)
      |                   ~~^~~~~~~~~~

Subtask #1
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 72280 KB Output is correct
2 Correct 9 ms 74332 KB Output is correct
3 Correct 45 ms 99164 KB Output is correct
4 Correct 43 ms 99456 KB Output is correct
5 Correct 48 ms 99152 KB Output is correct
6 Correct 48 ms 99152 KB Output is correct
7 Correct 54 ms 99364 KB Output is correct
8 Correct 46 ms 99412 KB Output is correct
9 Correct 43 ms 99664 KB Output is correct
10 Correct 45 ms 99236 KB Output is correct
11 Correct 48 ms 99408 KB Output is correct
12 Correct 42 ms 101972 KB Output is correct
13 Correct 42 ms 101208 KB Output is correct
14 Correct 41 ms 100692 KB Output is correct
15 Correct 43 ms 102228 KB Output is correct
16 Correct 43 ms 103252 KB Output is correct
17 Correct 44 ms 103252 KB Output is correct
18 Correct 43 ms 104020 KB Output is correct
19 Correct 47 ms 110672 KB Output is correct
20 Correct 48 ms 110416 KB Output is correct
21 Correct 46 ms 110020 KB Output is correct
22 Correct 8 ms 74328 KB Output is correct
23 Correct 9 ms 80576 KB Output is correct
24 Correct 9 ms 82524 KB Output is correct
25 Correct 9 ms 84568 KB Output is correct
26 Correct 9 ms 82668 KB Output is correct

Subtask #2
36.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 72280 KB Output is correct
2 Correct 8 ms 74332 KB Output is correct
3 Correct 9 ms 88920 KB Output is correct
4 Correct 9 ms 88668 KB Output is correct
5 Correct 69 ms 134492 KB Output is correct
6 Correct 70 ms 134456 KB Output is correct
7 Correct 73 ms 134488 KB Output is correct
8 Correct 78 ms 134492 KB Output is correct
9 Correct 75 ms 134224 KB Output is correct
10 Correct 67 ms 134652 KB Output is correct
11 Correct 69 ms 134492 KB Output is correct
12 Correct 69 ms 134616 KB Output is correct
13 Correct 70 ms 134652 KB Output is correct
14 Correct 72 ms 134488 KB Output is correct
15 Correct 72 ms 134284 KB Output is correct
16 Correct 72 ms 134580 KB Output is correct
17 Correct 72 ms 134644 KB Output is correct
18 Correct 69 ms 134748 KB Output is correct
19 Correct 68 ms 134748 KB Output is correct
20 Correct 69 ms 134684 KB Output is correct
21 Correct 70 ms 134744 KB Output is correct
22 Correct 69 ms 135256 KB Output is correct
23 Correct 69 ms 135256 KB Output is correct
24 Correct 69 ms 135256 KB Output is correct
25 Correct 1132 ms 150356 KB Output is correct

Subtask #3
41.0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 72280 KB Output is correct
2 Correct 9 ms 74332 KB Output is correct
3 Correct 45 ms 99164 KB Output is correct
4 Correct 43 ms 99456 KB Output is correct
5 Correct 48 ms 99152 KB Output is correct
6 Correct 48 ms 99152 KB Output is correct
7 Correct 54 ms 99364 KB Output is correct
8 Correct 46 ms 99412 KB Output is correct
9 Correct 43 ms 99664 KB Output is correct
10 Correct 45 ms 99236 KB Output is correct
11 Correct 48 ms 99408 KB Output is correct
12 Correct 42 ms 101972 KB Output is correct
13 Correct 42 ms 101208 KB Output is correct
14 Correct 41 ms 100692 KB Output is correct
15 Correct 43 ms 102228 KB Output is correct
16 Correct 43 ms 103252 KB Output is correct
17 Correct 44 ms 103252 KB Output is correct
18 Correct 43 ms 104020 KB Output is correct
19 Correct 47 ms 110672 KB Output is correct
20 Correct 48 ms 110416 KB Output is correct
21 Correct 46 ms 110020 KB Output is correct
22 Correct 8 ms 74328 KB Output is correct
23 Correct 9 ms 80576 KB Output is correct
24 Correct 9 ms 82524 KB Output is correct
25 Correct 9 ms 84568 KB Output is correct
26 Correct 9 ms 82668 KB Output is correct
27 Correct 9 ms 72280 KB Output is correct
28 Correct 8 ms 74332 KB Output is correct
29 Correct 9 ms 88920 KB Output is correct
30 Correct 9 ms 88668 KB Output is correct
31 Correct 69 ms 134492 KB Output is correct
32 Correct 70 ms 134456 KB Output is correct
33 Correct 73 ms 134488 KB Output is correct
34 Correct 78 ms 134492 KB Output is correct
35 Correct 75 ms 134224 KB Output is correct
36 Correct 67 ms 134652 KB Output is correct
37 Correct 69 ms 134492 KB Output is correct
38 Correct 69 ms 134616 KB Output is correct
39 Correct 70 ms 134652 KB Output is correct
40 Correct 72 ms 134488 KB Output is correct
41 Correct 72 ms 134284 KB Output is correct
42 Correct 72 ms 134580 KB Output is correct
43 Correct 72 ms 134644 KB Output is correct
44 Correct 69 ms 134748 KB Output is correct
45 Correct 68 ms 134748 KB Output is correct
46 Correct 69 ms 134684 KB Output is correct
47 Correct 70 ms 134744 KB Output is correct
48 Correct 69 ms 135256 KB Output is correct
49 Correct 69 ms 135256 KB Output is correct
50 Correct 69 ms 135256 KB Output is correct
51 Correct 1132 ms 150356 KB Output is correct
52 Correct 848 ms 180280 KB Output is correct
53 Correct 868 ms 180808 KB Output is correct
54 Correct 840 ms 182608 KB Output is correct
55 Correct 877 ms 176468 KB Output is correct
56 Correct 869 ms 179444 KB Output is correct
57 Correct 875 ms 180304 KB Output is correct
58 Correct 9 ms 76380 KB Output is correct
59 Correct 9 ms 84568 KB Output is correct
60 Correct 9 ms 80600 KB Output is correct
61 Correct 816 ms 178592 KB Output is correct
62 Correct 814 ms 183888 KB Output is correct
63 Correct 811 ms 178004 KB Output is correct
64 Correct 49 ms 108516 KB Output is correct
65 Correct 51 ms 107344 KB Output is correct
66 Correct 818 ms 183120 KB Output is correct
67 Correct 834 ms 182100 KB Output is correct
68 Correct 723 ms 212308 KB Output is correct
69 Correct 695 ms 213072 KB Output is correct
70 Correct 692 ms 209448 KB Output is correct
71 Correct 687 ms 209492 KB Output is correct
72 Correct 678 ms 211792 KB Output is correct
73 Correct 667 ms 212160 KB Output is correct
74 Correct 695 ms 213300 KB Output is correct
75 Correct 689 ms 215120 KB Output is correct
76 Correct 698 ms 216400 KB Output is correct
77 Correct 702 ms 214612 KB Output is correct
78 Correct 656 ms 212952 KB Output is correct
79 Correct 658 ms 213844 KB Output is correct
80 Correct 644 ms 209744 KB Output is correct
81 Correct 652 ms 237652 KB Output is correct
82 Correct 682 ms 238372 KB Output is correct
83 Correct 675 ms 238144 KB Output is correct
84 Correct 687 ms 255804 KB Output is correct
85 Correct 741 ms 316784 KB Output is correct
86 Correct 715 ms 315216 KB Output is correct
87 Correct 714 ms 315476 KB Output is correct