#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1000005;
vector<array<int, 2>> adj[N];
int cost[N];
int n, t, m;
void dfs(int node, int par, int height) {
array<int, 2> most={0, 0};
for (auto next : adj[node]) {
if (next[0] == par) continue;
dfs(next[0], node, height + 1);
if (cost[next[0]] > most[1]) most[1] = cost[next[0]];
if (most[1] > most[0]) swap(most[1], most[0]);
}
if (par != -1 && adj[node].size() == 1) {
cost[node] = height - 1;
} else if (par != -1 && adj[node].size() == 2) {
cost[node] = height;
} else {
cost[node] = adj[node].size() - 2 + most[1];
}
}
int dp[1 << 9][1 << 9][11][11][2];
int minMax(int mouse, bool el, int blocked, int dirty, int turn, bool moved) {
if (dp[blocked][dirty][mouse][turn][el] != -1) return dp[blocked][dirty][mouse][turn][el];
if (turn >= 10) return 10;
if (el) {
int best = 10;
for (int i = 0; i < n - 1; i++) {
if (!(dirty & (1 << i)) && !(blocked & (1 << i))) {
best =min(best, minMax(mouse, !el, (blocked | (1 << i)), dirty, turn + 1, false));
}
if (dirty & (1 << i)) {
best = min(best, minMax(mouse, !el, blocked, (dirty ^ (1 << i)), turn + 1, false));
}
}
if (moved) {
best = min(best, minMax(mouse, !el, blocked, dirty, turn, false));
}
dp[blocked][dirty][mouse][turn][el] = best;
return best;
//best = min(best, minMax(mouse, !el, blocked, diry, turn));
} else {
int best = turn;
bool travelled = false;
for (auto next : adj[mouse]) {
if (!(blocked & (1 << next[1]))&& !(dirty & 1 << next[1])) {
travelled = true;
if (next[0] != t) {
best = max(best, minMax(next[0], !el, blocked, (dirty | (1 << next[1])), turn, true));
}
}
}
if (!travelled) best = max(best, minMax(mouse, !el, blocked, dirty, turn, false));
dp[blocked][dirty][mouse][turn][el] = best;
bitset<9> a(blocked);
bitset<9> b(dirty);
return best;
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> t >> m;
bool connected = false;
for (int i = 0; i < (1 << 9); i++) {
for (int j = 0; j < (1 << 9); j++) {
for (int k = 0; k < 11; k++) {
for (int l = 0; l < 11; l++) {
for (int m = 0; m < 2; m++) dp[i][j][k][l][m] = -1;
}
}
}
}
for (int i = 0; i < n - 1; i++) {
int a, b;
cin >> a >> b;
adj[a].push_back({b, i});
adj[b].push_back({a, i});
}
if (false/*(a == t && b == m) || (a == m && b == t)*/) {
dfs(t, -1, 0);
cout << cost[m] << "\n";
} else {
cout << minMax(m, true, 0, 0, 0, false) << "\n";
}
}
/*
10 1 2
1 2
2 3
2 4
3 9
3 5
4 7
4 6
6 8
7 10
*/
Compilation message
mousetrap.cpp: In function 'int main()':
mousetrap.cpp:79:10: warning: unused variable 'connected' [-Wunused-variable]
79 | bool connected = false;
| ^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
150 ms |
272084 KB |
Output is correct |
| 2 |
Correct |
167 ms |
272016 KB |
Output is correct |
| 3 |
Incorrect |
156 ms |
272080 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
826 ms |
524288 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
150 ms |
272084 KB |
Output is correct |
| 2 |
Correct |
167 ms |
272016 KB |
Output is correct |
| 3 |
Incorrect |
156 ms |
272080 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
150 ms |
272084 KB |
Output is correct |
| 2 |
Correct |
167 ms |
272016 KB |
Output is correct |
| 3 |
Incorrect |
156 ms |
272080 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
