# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1054181 | NeroZein | Cats or Dogs (JOI18_catdog) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "bits/stdc++.h"
using namespace std;
#ifdef Nero
#include "Deb.h"
#else
#define debug(...)
#endif
const int N = 1003;
int a[N];
bool flag;
int dp[N][2];
vector<int> g[N];
void initialize(int n, vector<int> A, vector<int> B) {
for (int i = 0; i < n - 1; ++i) {
g[A[i]].push_back(B[i]);
g[B[i]].push_back(A[i]);
}
}
void dfs(int v, int p) {
dp[v][0] = dp[v][1] = 0;
for (int u : g[v]) {
if (u != p) {
dfs(u, v);
}
}
for (int j = 0; j < 2; ++j) {//0 cat, 1 dog
if ((a[v] == 2 && j == 0) || (a[v] == 1 && j == 1)) {
dp[v][j] = N;
continue;
}
for (int u : g[v]) {
if (u == p) {
continue;
}
dp[v][j] += min(dp[u][j], dp[u][j ^ 1] + 1);
}
}
//if (flag) {
//debug(v, dp[v][0], dp[v][1]);
//}
}
int cat(int v) {
a[v] = 1;
dfs(1, 1);
//debug(dp[8][0], dp[8][1]);
return min(dp[1][0], dp[1][1]);
}
int dog(int v) {
a[v] = 2;
flag = true;
dfs(1, 1);
return min(dp[1][0], dp[1][1]);
}
int neighbor(int v) {
a[v] = 0;
dfs(1, 1);
return min(dp[1][0], dp[1][1]);
}
//int main() {
//ios::sync_with_stdio(false);
//cin.tie(nullptr);
//int n;
//cin >> n;
//vector<int> A(n), B(n);
//for (int i = 0; i < n - 1; ++i) {
//cin >> A[i] >> B[i];
//}
//initialize(n, A, B);
//int q;
//cin >> q;
//while(q--) {
//int type, v;
//cin >> type >> v;
//int ans = 0;
//if (type == 1) {
//ans = cat(v);
//} else if (type == 2) {
//ans = dog(v);
//} else {
//ans = neighbor(v);
//}
//cout << ans << '\n';
//}
//return 0;
}