#include "catdog.h"
using namespace std;
const int N = 100005;
const int INF = 1e9;
int n;
int scores[2][N];
int curl[2][N];
struct SegmentTree{
int ans[2][2];
SegmentTree(){
for(int i =0; i< 2; i++){
for(int j = 0; j < 2; j++)
ans[i][j] = INF;
}
}
};
SegmentTree NIL;
SegmentTree join(SegmentTree a, SegmentTree b){
SegmentTree rsp;
for(int i = 0; i <= 1; i++){
for(int j = 0; j <= 1; j++){
for(int midl = 0; midl <=1 ;midl++){
for(int midr = 0; midr <=1; midr++){
rsp.ans[i][j] = min(rsp.ans[i][j], a.ans[i][midl] + b.ans[midr][j] + (midl!=midr));
}
}
}
}
return rsp;
}
SegmentTree build(int nod, int animal){
SegmentTree rsp;
for(int i =0; i <= 1; i++){
if(animal == i || animal == 2)
rsp.ans[i][i] = 0;
rsp.ans[i][i] += scores[i][nod];
}
return rsp;
}
SegmentTree aint[4*N];
int getminscore(SegmentTree chain, int pet){
int ans = INF;
for(int i = 0; i <= 1; i++){
ans = min(ans, chain.ans[pet][i]);
ans = min(ans, chain.ans[pet^1][i] + 1);
}
return ans;
}
void update(int nod, int l, int r, int upoz, int utype){
if(l > upoz || r < upoz)
return;
if(l == r){
aint[nod] = build(upoz, utype);
return;
}
int mid = (l + r)/2;
update(2*nod, l, mid, upoz, utype);
update(2*nod + 1, mid +1, r, upoz, utype);
aint[nod] = join(aint[2*nod], aint[2*nod + 1]);
}
SegmentTree query(int nod, int l, int r, int ql, int qr){
if(qr < l || ql > r)
return NIL;
if(ql <= l && r <= qr)
return aint[nod];
int mid = (l + r)/2;
SegmentTree rsp;
rsp = join(query(2*nod, l, mid, ql, qr), query(2*nod + 1, mid + 1, r, ql, qr));
return rsp;
}
vector<int> gr[N];
int par[N];
int sz[N];
int id[N];
int head[N];
int tp[N];
void dfs_init(int nod, int dad){
par[nod] = dad;
sz[nod] = 1;
for(auto x:gr[nod]){
if(x == dad)
continue;
dfs_init(x, nod);
sz[nod] += sz[x];
}
}
void dfs_heavy(int nod, int dad,int &idd, int chead){
head[nod] = chead;
id[nod] = idd++;
int mson = -1;
for(auto x:gr[nod]){
if(x == dad)
continue;
if(mson == -1 || sz[x] > sz[mson])
mson = x;
}
if(mson == -1)
return;
dfs_heavy(mson, nod, idd, chead);
for(auto x:gr[nod]){
if(x == dad || x == mson)
continue;
dfs_heavy(x, nod, idd, x);
}
}
SegmentTree update_heavy(int nod, int type){
tp[nod] = type;
int hd = head[nod];
update(1, 1, n, id[nod], type);
SegmentTree chain = query(1, 1, n, id[hd], id[nod]);
if(hd == 1)
return chain;
for(int i = 0; i<=1; i++){
scores[i][id[par[hd]]] -= curl[i][id[hd]];
curl[i][id[hd]] = getminscore(chain, i);
scores[i][id[par[hd]]] += curl[i][id[hd]];
}
return update_heavy(par[hd], tp[par[hd]]);
}
void build_aint(int nod, int l, int r){
if(l == r){
aint[nod] = build(nod, tp[l]);
return;
}
int mid = (l + r)/2;
build_aint(2*nod, l, mid);
build_aint(2*nod + 1, mid + 1, r);
aint[nod] = join(aint[2*nod], aint[2*nod + 1]);
}
void initialize(int N, std::vector<int> A, std::vector<int> B){
NIL = build(0, 2);
n = N;
for(int i = 0; i < N - 1; i++){
gr[A[i]].push_back(B[i]);
gr[B[i]].push_back(A[i]);
}
for(int i = 1; i<=n; i++)
tp[i] = 2;
build_aint(1, 1, n);
dfs_init(1, 0);
int cnt = 1;
dfs_heavy(1, 0, cnt, 1);
};
int cat(int v){
SegmentTree rsp = update_heavy(v, 0);
return min(getminscore(rsp, 0), getminscore(rsp, 1));
}
int dog(int v){
SegmentTree rsp = update_heavy(v, 1);
return min(getminscore(rsp, 0), getminscore(rsp, 1));
}
int neighbor(int v){
SegmentTree rsp = update_heavy(v, 2);
return min(getminscore(rsp, 0), getminscore(rsp, 1));
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
8908 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
8908 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
8908 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
