oj.uz

Submission #999272

# Submission time Handle Problem Language Result Execution time Memory
999272 2024-06-15T08:54:44 Z vjudge1 LOSTIKS (INOI20_lostiks) C++17
100 / 100
 1225 ms 492096 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;
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:101:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::array<long long int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  101 |  for (int i = 0; i < m.size(); i++) for (int j = 0; j < (1LL << (int)m.size()); j++) dp[i][j] = inf;
      |                  ~~^~~~~~~~~~
Main.cpp:102:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::array<long long int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |  for (int i = 0; i < m.size(); i++)
      |                  ~~^~~~~~~~~~
Main.cpp:114:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::array<long long int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  114 |   for (int i = 0; i < m.size(); i++)
      |                   ~~^~~~~~~~~~
Main.cpp:121:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::array<long long int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  121 |   for (int i = 0; i < m.size(); i++)
      |                   ~~^~~~~~~~~~
Main.cpp:124:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::array<long long int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  124 |    for (int j = 0; j < m.size(); j++)
      |                    ~~^~~~~~~~~~
Main.cpp:135:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::array<long long int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  135 |   for (int i = 0; i < m.size(); i++)
      |                   ~~^~~~~~~~~~

Subtask #1
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 71512 KB Output is correct
2 Correct 9 ms 73564 KB Output is correct
3 Correct 48 ms 108292 KB Output is correct
4 Correct 47 ms 108768 KB Output is correct
5 Correct 48 ms 109812 KB Output is correct
6 Correct 52 ms 108628 KB Output is correct
7 Correct 46 ms 108884 KB Output is correct
8 Correct 47 ms 108880 KB Output is correct
9 Correct 51 ms 109140 KB Output is correct
10 Correct 49 ms 108772 KB Output is correct
11 Correct 47 ms 108724 KB Output is correct
12 Correct 46 ms 111188 KB Output is correct
13 Correct 44 ms 110160 KB Output is correct
14 Correct 46 ms 109648 KB Output is correct
15 Correct 45 ms 111440 KB Output is correct
16 Correct 46 ms 112260 KB Output is correct
17 Correct 46 ms 112328 KB Output is correct
18 Correct 48 ms 112984 KB Output is correct
19 Correct 50 ms 118864 KB Output is correct
20 Correct 50 ms 118612 KB Output is correct
21 Correct 52 ms 118096 KB Output is correct
22 Correct 9 ms 73820 KB Output is correct
23 Correct 9 ms 79980 KB Output is correct
24 Correct 10 ms 82008 KB Output is correct
25 Correct 9 ms 84056 KB Output is correct
26 Correct 10 ms 82012 KB Output is correct

Subtask #2
36.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 71516 KB Output is correct
2 Correct 9 ms 73560 KB Output is correct
3 Correct 10 ms 88156 KB Output is correct
4 Correct 11 ms 88164 KB Output is correct
5 Correct 73 ms 187224 KB Output is correct
6 Correct 70 ms 187480 KB Output is correct
7 Correct 74 ms 187480 KB Output is correct
8 Correct 78 ms 187472 KB Output is correct
9 Correct 72 ms 187472 KB Output is correct
10 Correct 68 ms 187716 KB Output is correct
11 Correct 71 ms 187476 KB Output is correct
12 Correct 69 ms 187484 KB Output is correct
13 Correct 68 ms 187480 KB Output is correct
14 Correct 73 ms 187472 KB Output is correct
15 Correct 75 ms 187728 KB Output is correct
16 Correct 79 ms 187484 KB Output is correct
17 Correct 72 ms 187484 KB Output is correct
18 Correct 70 ms 187484 KB Output is correct
19 Correct 68 ms 187480 KB Output is correct
20 Correct 70 ms 187740 KB Output is correct
21 Correct 73 ms 187728 KB Output is correct
22 Correct 69 ms 188144 KB Output is correct
23 Correct 70 ms 188172 KB Output is correct
24 Correct 81 ms 188108 KB Output is correct
25 Correct 1225 ms 233824 KB Output is correct

Subtask #3
41.0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 71512 KB Output is correct
2 Correct 9 ms 73564 KB Output is correct
3 Correct 48 ms 108292 KB Output is correct
4 Correct 47 ms 108768 KB Output is correct
5 Correct 48 ms 109812 KB Output is correct
6 Correct 52 ms 108628 KB Output is correct
7 Correct 46 ms 108884 KB Output is correct
8 Correct 47 ms 108880 KB Output is correct
9 Correct 51 ms 109140 KB Output is correct
10 Correct 49 ms 108772 KB Output is correct
11 Correct 47 ms 108724 KB Output is correct
12 Correct 46 ms 111188 KB Output is correct
13 Correct 44 ms 110160 KB Output is correct
14 Correct 46 ms 109648 KB Output is correct
15 Correct 45 ms 111440 KB Output is correct
16 Correct 46 ms 112260 KB Output is correct
17 Correct 46 ms 112328 KB Output is correct
18 Correct 48 ms 112984 KB Output is correct
19 Correct 50 ms 118864 KB Output is correct
20 Correct 50 ms 118612 KB Output is correct
21 Correct 52 ms 118096 KB Output is correct
22 Correct 9 ms 73820 KB Output is correct
23 Correct 9 ms 79980 KB Output is correct
24 Correct 10 ms 82008 KB Output is correct
25 Correct 9 ms 84056 KB Output is correct
26 Correct 10 ms 82012 KB Output is correct
27 Correct 9 ms 71516 KB Output is correct
28 Correct 9 ms 73560 KB Output is correct
29 Correct 10 ms 88156 KB Output is correct
30 Correct 11 ms 88164 KB Output is correct
31 Correct 73 ms 187224 KB Output is correct
32 Correct 70 ms 187480 KB Output is correct
33 Correct 74 ms 187480 KB Output is correct
34 Correct 78 ms 187472 KB Output is correct
35 Correct 72 ms 187472 KB Output is correct
36 Correct 68 ms 187716 KB Output is correct
37 Correct 71 ms 187476 KB Output is correct
38 Correct 69 ms 187484 KB Output is correct
39 Correct 68 ms 187480 KB Output is correct
40 Correct 73 ms 187472 KB Output is correct
41 Correct 75 ms 187728 KB Output is correct
42 Correct 79 ms 187484 KB Output is correct
43 Correct 72 ms 187484 KB Output is correct
44 Correct 70 ms 187484 KB Output is correct
45 Correct 68 ms 187480 KB Output is correct
46 Correct 70 ms 187740 KB Output is correct
47 Correct 73 ms 187728 KB Output is correct
48 Correct 69 ms 188144 KB Output is correct
49 Correct 70 ms 188172 KB Output is correct
50 Correct 81 ms 188108 KB Output is correct
51 Correct 1225 ms 233824 KB Output is correct
52 Correct 947 ms 310868 KB Output is correct
53 Correct 883 ms 317524 KB Output is correct
54 Correct 867 ms 315988 KB Output is correct
55 Correct 909 ms 303292 KB Output is correct
56 Correct 879 ms 312912 KB Output is correct
57 Correct 928 ms 315016 KB Output is correct
58 Correct 10 ms 75864 KB Output is correct
59 Correct 10 ms 84060 KB Output is correct
60 Correct 11 ms 79964 KB Output is correct
61 Correct 904 ms 300744 KB Output is correct
62 Correct 919 ms 332840 KB Output is correct
63 Correct 906 ms 327732 KB Output is correct
64 Correct 54 ms 118864 KB Output is correct
65 Correct 57 ms 117840 KB Output is correct
66 Correct 906 ms 305284 KB Output is correct
67 Correct 898 ms 309072 KB Output is correct
68 Correct 780 ms 376816 KB Output is correct
69 Correct 769 ms 379336 KB Output is correct
70 Correct 833 ms 378704 KB Output is correct
71 Correct 783 ms 377792 KB Output is correct
72 Correct 833 ms 378452 KB Output is correct
73 Correct 836 ms 380608 KB Output is correct
74 Correct 820 ms 379732 KB Output is correct
75 Correct 814 ms 381268 KB Output is correct
76 Correct 835 ms 380752 KB Output is correct
77 Correct 830 ms 380776 KB Output is correct
78 Correct 747 ms 386476 KB Output is correct
79 Correct 733 ms 388176 KB Output is correct
80 Correct 725 ms 384084 KB Output is correct
81 Correct 741 ms 407216 KB Output is correct
82 Correct 805 ms 411364 KB Output is correct
83 Correct 753 ms 408816 KB Output is correct
84 Correct 843 ms 436308 KB Output is correct
85 Correct 834 ms 492096 KB Output is correct
86 Correct 824 ms 488788 KB Output is correct
87 Correct 828 ms 488748 KB Output is correct