#include "catdog.h"
#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;
const int MAXN = 1e5 + 5;
int N;
vector<int> adj[MAXN];
int dp[MAXN][3];
int state[MAXN];
void DfsInit(int u, int p) {
if (p) {
adj[u].erase(find(begin(adj[u]), end(adj[u]), p));
}
for (auto v : adj[u]) {
DfsInit(v, u);
}
}
void DfsDp(int u) {
dp[u][0] = dp[u][1] = dp[u][2] = 0;
for (auto v : adj[u]) {
DfsDp(v);
dp[u][0] += min({dp[v][0], dp[v][1] + 1, dp[v][2] + 1});
dp[u][1] += min({dp[v][0], dp[v][1] + 0, dp[v][2] + 1});
dp[u][2] += min({dp[v][0], dp[v][1] + 1, dp[v][2] + 0});
}
if (state[u] != 0) {
dp[u][state[u]] = min(dp[u][state[u]], dp[u][0]);
dp[u][0] = dp[u][state[u] ^ 3] = INF;
}
}
int Solve() {
DfsDp(1);
return min({dp[1][0], dp[1][1], dp[1][2]});
}
void initialize(int N, vector<int> A, vector<int> B) {
::N = N;
for (int i = 0; i + 1 < N; i++) {
adj[A[i]].emplace_back(B[i]);
adj[B[i]].emplace_back(A[i]);
}
DfsInit(1, 0);
}
int cat(int v) {
state[v] = 1;
return Solve();
}
int dog(int v) {
state[v] = 2;
return Solve();
}
int neighbor(int v) {
state[v] = 0;
return Solve();
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
2688 KB |
Output is correct |
2 |
Correct |
2 ms |
2688 KB |
Output is correct |
3 |
Correct |
2 ms |
2688 KB |
Output is correct |
4 |
Correct |
2 ms |
2688 KB |
Output is correct |
5 |
Correct |
2 ms |
2688 KB |
Output is correct |
6 |
Correct |
2 ms |
2688 KB |
Output is correct |
7 |
Correct |
2 ms |
2688 KB |
Output is correct |
8 |
Correct |
2 ms |
2688 KB |
Output is correct |
9 |
Correct |
2 ms |
2688 KB |
Output is correct |
10 |
Correct |
2 ms |
2688 KB |
Output is correct |
11 |
Correct |
2 ms |
2688 KB |
Output is correct |
12 |
Correct |
2 ms |
2688 KB |
Output is correct |
13 |
Correct |
2 ms |
2688 KB |
Output is correct |
14 |
Correct |
2 ms |
2688 KB |
Output is correct |
15 |
Correct |
2 ms |
2688 KB |
Output is correct |
16 |
Correct |
2 ms |
2688 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
2688 KB |
Output is correct |
2 |
Correct |
2 ms |
2688 KB |
Output is correct |
3 |
Correct |
2 ms |
2688 KB |
Output is correct |
4 |
Correct |
2 ms |
2688 KB |
Output is correct |
5 |
Correct |
2 ms |
2688 KB |
Output is correct |
6 |
Correct |
2 ms |
2688 KB |
Output is correct |
7 |
Correct |
2 ms |
2688 KB |
Output is correct |
8 |
Correct |
2 ms |
2688 KB |
Output is correct |
9 |
Correct |
2 ms |
2688 KB |
Output is correct |
10 |
Correct |
2 ms |
2688 KB |
Output is correct |
11 |
Correct |
2 ms |
2688 KB |
Output is correct |
12 |
Correct |
2 ms |
2688 KB |
Output is correct |
13 |
Correct |
2 ms |
2688 KB |
Output is correct |
14 |
Correct |
2 ms |
2688 KB |
Output is correct |
15 |
Correct |
2 ms |
2688 KB |
Output is correct |
16 |
Correct |
2 ms |
2688 KB |
Output is correct |
17 |
Correct |
12 ms |
2816 KB |
Output is correct |
18 |
Correct |
14 ms |
2688 KB |
Output is correct |
19 |
Correct |
8 ms |
2688 KB |
Output is correct |
20 |
Correct |
3 ms |
2688 KB |
Output is correct |
21 |
Correct |
4 ms |
2688 KB |
Output is correct |
22 |
Correct |
4 ms |
2688 KB |
Output is correct |
23 |
Correct |
16 ms |
2688 KB |
Output is correct |
24 |
Correct |
14 ms |
2688 KB |
Output is correct |
25 |
Correct |
7 ms |
2688 KB |
Output is correct |
26 |
Correct |
4 ms |
2688 KB |
Output is correct |
27 |
Correct |
4 ms |
2688 KB |
Output is correct |
28 |
Correct |
6 ms |
2688 KB |
Output is correct |
29 |
Correct |
16 ms |
2816 KB |
Output is correct |
30 |
Correct |
4 ms |
2816 KB |
Output is correct |
31 |
Correct |
3 ms |
2688 KB |
Output is correct |
32 |
Correct |
6 ms |
2688 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
2688 KB |
Output is correct |
2 |
Correct |
2 ms |
2688 KB |
Output is correct |
3 |
Correct |
2 ms |
2688 KB |
Output is correct |
4 |
Correct |
2 ms |
2688 KB |
Output is correct |
5 |
Correct |
2 ms |
2688 KB |
Output is correct |
6 |
Correct |
2 ms |
2688 KB |
Output is correct |
7 |
Correct |
2 ms |
2688 KB |
Output is correct |
8 |
Correct |
2 ms |
2688 KB |
Output is correct |
9 |
Correct |
2 ms |
2688 KB |
Output is correct |
10 |
Correct |
2 ms |
2688 KB |
Output is correct |
11 |
Correct |
2 ms |
2688 KB |
Output is correct |
12 |
Correct |
2 ms |
2688 KB |
Output is correct |
13 |
Correct |
2 ms |
2688 KB |
Output is correct |
14 |
Correct |
2 ms |
2688 KB |
Output is correct |
15 |
Correct |
2 ms |
2688 KB |
Output is correct |
16 |
Correct |
2 ms |
2688 KB |
Output is correct |
17 |
Correct |
12 ms |
2816 KB |
Output is correct |
18 |
Correct |
14 ms |
2688 KB |
Output is correct |
19 |
Correct |
8 ms |
2688 KB |
Output is correct |
20 |
Correct |
3 ms |
2688 KB |
Output is correct |
21 |
Correct |
4 ms |
2688 KB |
Output is correct |
22 |
Correct |
4 ms |
2688 KB |
Output is correct |
23 |
Correct |
16 ms |
2688 KB |
Output is correct |
24 |
Correct |
14 ms |
2688 KB |
Output is correct |
25 |
Correct |
7 ms |
2688 KB |
Output is correct |
26 |
Correct |
4 ms |
2688 KB |
Output is correct |
27 |
Correct |
4 ms |
2688 KB |
Output is correct |
28 |
Correct |
6 ms |
2688 KB |
Output is correct |
29 |
Correct |
16 ms |
2816 KB |
Output is correct |
30 |
Correct |
4 ms |
2816 KB |
Output is correct |
31 |
Correct |
3 ms |
2688 KB |
Output is correct |
32 |
Correct |
6 ms |
2688 KB |
Output is correct |
33 |
Execution timed out |
3082 ms |
7400 KB |
Time limit exceeded |
34 |
Halted |
0 ms |
0 KB |
- |