#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];
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--;}//printf("%d : %d\n",j,x+1);}
}
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));
}
node get_v(int x){
int c=0,d=0;
for(int y:E[x]){
if(!y || pa[y]==x) continue;
node p=get_cost(1,1,n,cnt[y],cnt[lst[num[y]][0]]);
p.cost[0]=min(p.cost[0],p.cost[1]);
p.cost[1]=min(p.cost[2],p.cost[3]);
c+=min(p.cost[0],p.cost[1]+1);
d+=min(p.cost[0]+1,p.cost[1]);
}
if(sta[x]==1) d=inf;
if(sta[x]==2) c=inf;
return {c,inf,inf,d};
}
void update(int x){
if(!x) return;
node p=get_v(x);
udt_tree(1,1,n,cnt[x],p);
update(pa[lst[num[x]].back()]);
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);
return get_min();
}
int dog(int v){
sta[v]=2;
update(v);
return get_min();
}
int neighbor(int v){
sta[v]=0;
update(v);
return get_min();
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
9728 KB |
Output is correct |
| 2 |
Incorrect |
12 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 |
12 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 |
12 ms |
9728 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
