#include "catdog.h"
#include <bits/stdc++.h>
#define eb emplace_back
#define INF (0x3f3f3f3f)
using namespace std;
const int MAXN = 100055;
static int _int[MAXN<<5], *_intp=_int;
inline int* newint(const unsigned int SZ) {
_intp += SZ;
return _intp - SZ;
}
struct HLD {
int *DCC, *DCD, *DDC, *DDD;
int *CC, *CD;
int n, MX, pc, pd;
void init(int _n) {
n = _n;
for(MX = 1; MX < n; MX <<= 1);
CC = newint(n);
CD = newint(n);
DCC = newint(MX<<1);
DCD = newint(MX<<1);
DDC = newint(MX<<1);
DDD = newint(MX<<1);
fill(DCD+MX, DCD+(MX<<1), INF);
fill(DDC+MX, DDC+(MX<<1), INF);
}
void upd(int i) {
DCC[i+MX] = CC[i];
DDD[i+MX] = CD[i];
for(i = (i+MX)>>1; i; i >>= 1) {
int l = i<<1, r = l|1;
DCC[i] = min({INF, DCC[l]+DCC[r], DCD[l]+DDC[r]
, DCC[l]+DDC[r]+1, DCD[l]+DCC[r]+1});
DDD[i] = min({INF, DDD[l]+DDD[r], DDC[l]+DCD[r]
, DDD[l]+DCD[r]+1, DDC[l]+DDD[r]+1});
DCD[i] = min({INF, DCC[l]+DCD[r], DCD[l]+DDD[r]
, DCC[l]+DDD[r]+1, DCD[l]+DCD[r]+1});
DDC[i] = min({INF, DDD[l]+DDC[r], DDC[l]+DCC[r]
, DDD[l]+DCC[r]+1, DDC[l]+DDC[r]+1});
}
}
int get() { return min({DCC[1], DCD[1], DDC[1], DDD[1]}); }
} hld[MAXN];
vector<int> G[MAXN];
int SC[MAXN], SD[MAXN];
int HI[MAXN], HJ[MAXN], HC[MAXN], HR[MAXN], Hn;
int prt[MAXN], dep[MAXN], cnt[MAXN];
bitset<MAXN> chk, isc;
int N, Q;
void g(int v) {
auto &V = hld[HI[v]];
int j = HJ[v];
V.CC[j] = SC[v];
V.CD[j] = SD[v];
if(chk[v]) (isc[v] ? V.CD[j] : V.CC[j]) = INF;
}
void f(int v) {
for(int p, j; v; v = p) {
g(v);
auto &V = hld[HI[v]];
j = HJ[v]; p = prt[HR[HI[v]]];
V.upd(j);
SC[p] -= min(V.pc, V.pd+1);
SD[p] -= min(V.pd, V.pc+1);
V.pc = min(V.DCC[1], V.DCD[1]);
V.pd = min(V.DDC[1], V.DDD[1]);
SC[p] += min(V.pc, V.pd+1);
SD[p] += min(V.pd, V.pc+1);
}
}
void hfs(int i) {
HC[HI[i]]++;
int hi = -1, hc = 0;
for(int v : G[i])
if(v != prt[i] && hc < cnt[v]) {
hi = v; hc = cnt[v];
}
if(!hc) return;
HI[hi] = HI[i];
HJ[hi] = HJ[i]+1;
for(int v : G[i]) if(v != prt[i]) {
if(v != hi) {
HI[v] = ++Hn;
HR[Hn] = v;
}
hfs(v);
}
}
void dfs(int i) {
cnt[i] = 1;
for(int v : G[i]) if(!dep[v]) {
dep[v] = dep[i] + 1;
prt[v] = i;
dfs(v);
cnt[i] += cnt[v];
}
}
void initialize(int N, std::vector<int> _A, std::vector<int> _B) {
::N = N;
for(int i = 1, a, b; i < N; i++) {
a = _A[i-1]; b = _B[i-1];
G[a].eb(b);
G[b].eb(a);
}
dep[1] = 1; dfs(1);
HI[1] = HR[1] = Hn = 1; hfs(1);
for(int i = 1; i <= Hn; i++) hld[i].init(HC[i]);
}
int cat(int v) {
chk[v] = isc[v] = true;
f(v);
return hld[1].get();
}
int dog(int v) {
chk[v] = true; isc[v] = false;
f(v);
return hld[1].get();
}
int neighbor(int v) {
chk[v] = isc[v] = false;
f(v);
return hld[1].get();
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
2688 KB |
Output is correct |
| 2 |
Correct |
4 ms |
2816 KB |
Output is correct |
| 3 |
Correct |
5 ms |
2688 KB |
Output is correct |
| 4 |
Correct |
4 ms |
2816 KB |
Output is correct |
| 5 |
Correct |
4 ms |
2688 KB |
Output is correct |
| 6 |
Incorrect |
4 ms |
2816 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
2688 KB |
Output is correct |
| 2 |
Correct |
4 ms |
2816 KB |
Output is correct |
| 3 |
Correct |
5 ms |
2688 KB |
Output is correct |
| 4 |
Correct |
4 ms |
2816 KB |
Output is correct |
| 5 |
Correct |
4 ms |
2688 KB |
Output is correct |
| 6 |
Incorrect |
4 ms |
2816 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
2688 KB |
Output is correct |
| 2 |
Correct |
4 ms |
2816 KB |
Output is correct |
| 3 |
Correct |
5 ms |
2688 KB |
Output is correct |
| 4 |
Correct |
4 ms |
2816 KB |
Output is correct |
| 5 |
Correct |
4 ms |
2688 KB |
Output is correct |
| 6 |
Incorrect |
4 ms |
2816 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
