#include "catdog.h"
#include<bits/stdc++.h>
#define MAX_N 200005
#define MAX_M 100005
#define pb push_back
#define mp make_pair
#define all(V) (V).begin(),(V).end()
#define reset(V) (V).clear();(V).resize(0);
#define sq(x) ((x)*(x))
#define abs(x) ((x)>0?(x):(-(x)))
#define fi first
#define se second
#define LL_inf (1LL<<60)
#define full_inf 0x7fffffff
#define half_inf 0x3fffffff
#define inf 1000005
#define MOD 1000000007LL
#define cpx_mod(x) (((LD)(((LL)x.real())%MOD)),((LD)(((LL)x.imag())%MOD)))
using namespace std;
typedef long long LL;
typedef long double LD;
typedef pair<int,int> pii;
typedef pair<LL,LL> pil;
typedef pair<LL,string> pls;
typedef complex<LD> Complex;
typedef long double LD;
int x;
struct node{
int cost[4];
}tree[4*MAX_N];
int n,m;
int num[MAX_N],sta[MAX_N],cnt[MAX_N],pa[MAX_N],C[MAX_N],D[MAX_N];
bool vis[MAX_N];
vector<int> E[MAX_N],lst[MAX_N];
void make_HLD(int x){
cnt[x]=1;
if(x!=1 && E[x].size()==1){
E[x][0]=0;
lst[m].pb(x);
num[x]=m++;
return;
}
int mi=0;
for(int &y:E[x]){
if(cnt[y]){y=0;continue;}
make_HLD(y);pa[y]=x;
cnt[x]+=cnt[y];
if(cnt[y]>cnt[mi]) mi=y;
}
num[x]=num[mi];
lst[num[x]].pb(x);
}
void init1(int x){for(int i=0;i<4;i++) tree[x].cost[i]=(i%3?1:0)*inf;}
void initialize(int N, std::vector<int> A, std::vector<int> B) {
cnt[0]=-1;
n=N;
for(int i=0;i<n-1;i++){
E[A[i]].pb(B[i]);
E[B[i]].pb(A[i]);
}
make_HLD(1);
int x=n;
for(int i=0;i<m;i++){
for(int j:lst[i]){cnt[j]=x--;}
}
for(int i=1;i<=4*n;i++) init1(i);
}
node merge(node x,node y){
node p;
for(int i=0;i<4;i++) p.cost[i]=inf;
for(int i=0;i<4;i++){
for(int j=0;j<4;j++) p.cost[(i/2)*2+j%2]=min(p.cost[(i/2)*2+j%2],x.cost[i]+y.cost[j]+((i%2)^(j/2)));
}
return p;
}
void udt_tree(int x,int l,int r,int p,node v){
if(p<l || r<p) return;
if(l==r){
tree[x]=v;
return;
}
int mid=(l+r)>>1;
udt_tree(2*x,l,mid,p,v);
udt_tree(2*x+1,mid+1,r,p,v);
tree[x]=merge(tree[2*x],tree[2*x+1]);
}
node get_cost(int x,int l,int r,int s,int e){
if(e<l || s>r) return {0,inf,inf,0};
if(s<=l && r<=e) return tree[x];
int mid=(l+r)>>1;
return merge(get_cost(2*x,l,mid,s,e),get_cost(2*x+1,mid+1,r,s,e));
}
void update(int x,int cat,int dog){
if(!x) return;
int p=lst[num[x]].back();
node q=get_cost(1,1,n,cnt[lst[num[x]].back()],cnt[lst[num[x]][0]]);
C[pa[p]]-=min(min(q.cost[0],q.cost[1]),min(q.cost[2],q.cost[3])+1);
D[pa[p]]-=min(min(q.cost[2],q.cost[3]),min(q.cost[0],q.cost[1])+1);
udt_tree(1,1,n,cnt[x],{cat,inf,inf,dog});
q=get_cost(1,1,n,cnt[lst[num[x]].back()],cnt[lst[num[x]][0]]);
C[pa[p]]+=min(min(q.cost[0],q.cost[1]),min(q.cost[2],q.cost[3])+1);
D[pa[p]]+=min(min(q.cost[2],q.cost[3]),min(q.cost[0],q.cost[1])+1);
cat=(sta[pa[p]]==2)?inf:D[pa[p]];
dog=(sta[pa[p]]==1)?inf:C[pa[p]];
update(pa[p],cat,dog);
return;
}
int get_min(){
node p=get_cost(1,1,n,cnt[1],cnt[lst[num[1]][0]]);
return min({p.cost[0],p.cost[1],p.cost[2],p.cost[3]});
}
int cat(int v){
sta[v]=1;
update(v,C[v],inf);
return get_min();
}
int dog(int v){
sta[v]=2;
update(v,inf,D[v]);
return get_min();
}
int neighbor(int v){
sta[v]=0;
update(v,C[v],D[v]);
return get_min();
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
9728 KB |
Output is correct |
| 2 |
Incorrect |
11 ms |
9728 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
9728 KB |
Output is correct |
| 2 |
Incorrect |
11 ms |
9728 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
9728 KB |
Output is correct |
| 2 |
Incorrect |
11 ms |
9728 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
