#include<bits/stdc++.h>
#include "catdog.h"
using namespace std;
const int N=1<<17;
using val=array<array<int,2>,2>;
val t[2*N];
int par[N];
int cur[N];
#define chmi(x,y) if(x>y)x=y
#define chma(x,y) if(x<y)x=y
const int oo=100001;
int invind[N];
val gett(int x){
if(x<N)
return t[x];
val ans;
int u=invind[x-N];
for(int i=0;i<2;++i)
for(int j=0;j<2;++j)
if(i==j&&((i+1)&cur[u]))
ans[i][j]=t[x][i][j];
else
ans[i][j]=oo;
return ans;
}
val merge(val a,val b){
val ans;
for(int st=0;st<2;++st)
for(int en=0;en<2;++en){
ans[st][en]=oo;
for(int le=0;le<2;++le)
for(int ri=0;ri<2;++ri){
chmi(ans[st][en],a[st][le]+b[ri][en]+(le!=ri));
}
}
return ans;
}
void upd1(int x){
// if(x==(N+2)/2);
// cerr<<"lul "<<gett(x<<1)[0][0]<<' '<<gett(x<<1^1)[0][0]<<'\n';
t[x]=merge(gett(x<<1),gett(x<<1^1));
}
void upd(int x){
x+=N;
while(x>1)
upd1(x>>1),x>>=1;
}
val neut={0,oo,oo,0};
val get(int l,int r){
l+=N;
r+=N;
val ansle=neut,ansri=neut;
while(l<r){
if(l&1)
ansle=merge(ansle,gett(l++));
if(r&1)
ansri=merge(gett(--r),ansri);
l/=2,r/=2;
}
return merge(ansle,ansri);
}
vector<int> ch[N];
int ind[N];
int sz[N];
int top[N];
int listok[N];
/*
val vals[4];
void init_vals(){
vals[1]={{0,oo},{oo,oo}};
vals[2]={{oo,oo},{oo,0}};
vals[3]={{0,oo},{oo,0}};
}
bool trash=(init_vals(),true);
*/
void update_c(int x,int coef){
while(true){
upd(ind[x]);
x=top[x];
if(x==0)break;
val kek=get(ind[x],ind[listok[x]]+1);
x=par[x];
int y=ind[x]+N;
int k0=min(kek[0][0],kek[0][1]),k1=min(kek[1][0],kek[1][1]);
t[y][0][0]+=coef*(min(k0,k1+1));
t[y][1][1]+=coef*(min(k1,k0+1));
}
}
void update(int x,int nw){
update_c(x,-1);
cur[x]=nw;
update_c(x,1);
}
vector<int>g[N];
void d1(int u,int p=-1){
par[u]=p;
sz[u]=1;
for(int v:g[u]){
if(v==p)continue;
ch[u].push_back(v);
d1(v,u);
sz[u]+=sz[v];
if(sz[v]>sz[ch[u][0]])
swap(ch[u].back(),ch[u][0]);
}
if(ch[u].size())listok[u]=listok[ch[u][0]];
else listok[u]=u;
}
int tot=0;
void d2(int u){
ind[u]=tot++;
invind[ind[u]]=u;
for(int v:ch[u]){
if(v==ch[u][0])
top[v]=top[u];
else
top[v]=v;
d2(v);
}
}
void d3(int u){
cur[u]=3;
update_c(u,1);
for(int v:ch[u])d3(v);
}
int n;
void initialize(int N1, std::vector<int> A, std::vector<int> B) {
n=N1;
for(int i=0;i<n-1;++i)
g[A[i]-1].push_back(B[i]-1),g[B[i]-1].push_back(A[i]-1);
d1(0);
d2(0);
d3(0);
}
int get(){
val mem=get(ind[0],ind[listok[0]]+1);
int ans=oo;
for(int i=0;i<2;++i)
for(int j=0;j<2;++j)
ans=min(ans,mem[i][j]);
return ans;
}
int cat(int v) {
update(v-1,1);
/*
auto mem=gett((2+N)/2);
auto mem=merge(gett(2+N),gett(3+N));
cerr<<mem[0][0]<<' '<<mem[1][1]<<'\n';
upd(2);
mem=gett((2+N)/2);
cerr<<mem[0][0]<<' '<<mem[1][1]<<'\n';
for(int i=0;i<n;++i)
cerr<<gett((i+N)/1)[0][0]<<' '<<gett((i+N)/1)[1][1]<<'\n';
cerr<<'\n';
// exit(0);
for(int i=0;i<n;++i)
cerr<<gett((i+N)/1)[0][0]<<' '<<gett((i+N)/1)[1][1]<<'\n';
cerr<<'\n';
*/
return get();
}
int dog(int v) {
update(v-1,2);
//for(int i=0;i<n;++i)
//cerr<<gett((i+N)/1)[0][0]<<' '<<gett((i+N)/1)[1][1]<<'\n';
//cerr<<'\n';
return get();
}
int neighbor(int v) {
update(v-1,3);
return get();
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
6528 KB |
Output is correct |
| 2 |
Incorrect |
7 ms |
6528 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
6528 KB |
Output is correct |
| 2 |
Incorrect |
7 ms |
6528 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
6528 KB |
Output is correct |
| 2 |
Incorrect |
7 ms |
6528 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
