#include "catdog.h"
#include <bits/stdc++.h>
using namespace std;
template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl
using ll = long long;
const int maxn = 1e6 + 5;
struct dsu0 {
vector<int> par, siz;
int n;
int cc;
int largest;
void init(int n) {
assert(n>0);
this->n=n;
cc=n;
par.resize(n+10);siz.resize(n+10);
for (int i=0; i<n; i++) par[i]=i,siz[i]=1;
largest=1;
}
int parent(int x) {
assert(x>=0 && x<n);
return par[x]==x?x:par[x]=parent(par[x]);
}
bool join(int x, int y) {
x=parent(x);y=parent(y);
if (x==y) return false;
cc--;
if (siz[x]<siz[y]) swap(x,y);
siz[x]+=siz[y];par[y]=x;
largest=max(largest,siz[x]);
return true;
}
};
const int NONE = -1;
const int CAT = 0;
const int DOG = 1;
int n;
vector<int> g[maxn];
vector<pair<int,int>> edges;
int state[maxn];
void initialize(int N, std::vector<int> A, std::vector<int> B) {
n = N;
for (int i=0; i<n-1; i++) {
int u = A[i];
int v = B[i];
u--; v--;
assert(u>=0 && v>=0); // assume given to us 1-indexed
assert(u<n && v<n);
g[u].push_back(v);
g[v].push_back(u);
edges.push_back({u,v});
}
for (int i=0; i<n; i++) {
state[i] = NONE;
}
}
void print() {
return;
for (int i=0; i<n; i++) {
cout<<state[i]<<" ";
}
cout<<endl;
}
int solve() {
int res = n+10;
for (int mask=0; mask<(1<<(n-1)); mask++) {
dsu0 dsu;
dsu.init(n);
for (int j=0; j<n-1; j++) {
if (!(mask>>j&1)) {
int u = edges[j].first;
int v = edges[j].second;
dsu.join(u, v);
}
}
map<int,int> mp;
bool ok = true;
for (int i=0; i<n && ok; i++) {
int cc = dsu.parent(i);
if (state[i] == NONE) continue;
if (!mp.count(cc)) {
mp[cc] = state[cc];
}
if (mp[cc] != state[i]) {
ok = false;
}
}
if (ok) {
int rm = __builtin_popcount(mask);
res = min(res, rm);
}
}
return res;
}
int cat(int v) {
v--;
state[v] = CAT;
print();
return solve();
}
int dog(int v) {
v--;
state[v] = DOG;
print();
return solve();
}
int neighbor(int v) {
v--;
state[v] = NONE;
print();
return solve();
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
16 ms |
23808 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
16 ms |
23808 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
16 ms |
23808 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
