#include "catdog.h"
#include <bits/stdc++.h>
using namespace std;
/* sorry, this is the bare minimum :'( */
using ll = long long;
using ii = pair<int, int>;
using vi = vector<int>;
#define all(v) begin(v), end(v)
#define sz(v) (int)(v).size()
#define fi first
#define se second
const int N = 1e5 + 5;
const int inf = 1e9 + 5;
int n;
int state[N];
int dp[N][3];
vi g[N];
void chkmin(int& x, int y) {
x = min(x, y);
}
void solve(int u, int dad = 0) {
for(int v : g[u]) if(v != dad) {
solve(v, u);
}
dp[u][0] = dp[u][1] = dp[u][2] = inf;
dp[u][state[u]] = 0;
for(int v : g[u]) if(v != dad) {
vi me(dp[u], dp[u]+3), ch(dp[v], dp[v]+3);
dp[u][0] = dp[u][1] = dp[u][2] = inf;
for(int i : {0,1,2}) {
for(int j : {0,1,2}) {
chkmin(dp[u][i], me[i] + ch[j] + 1);
if((i|j) != 3) {
chkmin(dp[u][i|j], me[i] + ch[j]);
}
}
}
}
cout << "u = " << u << endl;
for(int i = 0; i < 3; ++i) {
cout << dp[u][i] << ' ';
} cout << endl;
}
void initialize(int _n, std::vector<int> A, std::vector<int> B) {
n = _n;
for(int i = 0; i < sz(A); ++i) {
g[A[i]].emplace_back(B[i]);
g[B[i]].emplace_back(A[i]);
}
}
int cat(int v) {
cout << "cat at " << v << endl;
state[v] = 1;
solve(1);
return *min_element(dp[1], dp[1]+4);
}
int dog(int v) {
cout << "dog at " << v << endl;
state[v] = 2;
solve(1);
return *min_element(dp[1], dp[1]+4);
}
int neighbor(int v) {
cout << "no at " << v << endl;
state[v] = 0;
solve(1);
return *min_element(dp[1], dp[1]+4);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
2668 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
2668 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
2668 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
