#include<bits/stdc++.h>
using namespace std;
#define ii pair <int, int>
#define app push_back
const int N = 1e5 + 7;
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]].app(b[i]);
g[b[i]].app(a[i]);
}
g[0].app(1);
}
int type[N];
int ans = 0;
int cnt[2];
void dfs(int u, int p, int part) {
if (type[u] == -1) {
++cnt[type[u]];
for (int v : g[u]) {
if (v != p) {
dfs(v, u, part);
}
}
}
else {
ans += type[u] ^ part;
for (int v : g[u]) {
if (v != p) {
dfs(v, u, type[u]);
}
}
}
}
int f() {
ans = cnt[0] = cnt[1] = 0;
dfs(0, 0, -1);
return ans + min(cnt[0], cnt[1]);
}
int cat(int u) {
type[u] = 0;
return f();
}
int dog(int u) {
type[u] = 1;
return f();
}
int neighbor(int u) {
type[u] = -1;
return f();
}
#ifdef HOME
signed main() {
freopen("input.txt", "r", stdin);
int n;
cin >> n;
vector <int> a, b;
for (int i = 0; i < n - 1; ++i) {
int u, v;
cin >> u >> v;
a.app(u); b.app(v);
}
initialize(n, a, b);
int q;
cin >> q;
for (int i = 0; i < q; ++i) {
int t, u;
cin >> t >> u;
if (t == 1) cout << cat(u) << '\n';
else if (t == 2) cout << dog(u) << '\n';
else cout << neighbor(u) << '\n';
}
}
#endif
Compilation message
catdog.cpp: In function 'void dfs(int, int, int)':
catdog.cpp:19:22: warning: array subscript is below array bounds [-Warray-bounds]
++cnt[type[u]];
~~~~~~~~~~~^
catdog.cpp:19:22: warning: array subscript is below array bounds [-Warray-bounds]
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
2680 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
2680 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
2680 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
