Submission #887972

#	Time	Username	Problem	Language	Result	Execution time	Memory
887972		amirhoseinfar1385	Cats or Dogs (JOI18_catdog)	C++17	100 / 100	611 ms	35044 KiB

catdog

#include "catdog.h"
#include<bits/stdc++.h>
using namespace std;
const int maxn=100000+10;
vector<int>adj[maxn];
int timea=0,val[maxn],kaf=(1<<17),n,inf=1e6+5,sz[maxn],part[maxn],parh[maxn],akh[maxn];
pair<int,int>stf[maxn];
set<int>allr[maxn],allb[maxn];
int mainres=0;

struct node{
    int res[2][2],ted;
    node(){
        res[0][1]=res[1][0]=0;
        res[0][0]=res[1][1]=0;
        ted=0;
    }
}fn;
struct segment{
    node seg[(1<<18)];

    node merge(node a,node b){
        if(a.ted==0){
            return b;
        }
        if(b.ted==0){
            return a;
        }
        node ret;
        ret.res[0][0]=ret.res[1][0]=ret.res[1][1]=ret.res[0][1]=inf;
        ret.ted=a.ted+b.ted;
        for(int i=0;i<2;i++){
            for(int j=0;j<2;j++){
                for(int ii=0;ii<2;ii++){
                    for(int jj=0;jj<2;jj++){
                        ret.res[i][j]=min(ret.res[i][j],a.res[i][ii]+b.res[jj][j]+(ii!=jj));
                    }
                }
            }
        }
        return ret;
    }
    segment(){
        for(int i=(1<<18)-1;i>=0;i--){
            if(i>=kaf){
                seg[i].res[0][1]=seg[i].res[1][0]=inf;
                seg[i].ted=1;
                seg[i].res[0][0]=seg[i].res[1][1]=0;
            }
            else{
                seg[i]=merge(seg[(i<<1)],seg[(i<<1)^1]);
            }
        }
    }
    void add(int i,int wr,int wb,int to){
        if(i==0){
            return ;
        }
        if(i>=kaf){
           // //cout<<i<<" "<<i-kaf<<" "<<wr<<" "<<wb<<" "<<to<<"\n";
            seg[i].ted=1;
            if(to==0){
                seg[i].res[0][0]=seg[i].res[1][1]=seg[i].res[1][0]=seg[i].res[0][1]=inf;
                seg[i].res[0][0]=wr;
                seg[i].res[1][1]=wb;
                return add((i>>1),wr,wb,to);
            }
            if(to==1){
                seg[i].res[0][0]=seg[i].res[1][1]=seg[i].res[1][0]=seg[i].res[0][1]=inf;
                seg[i].res[1][1]=wb;
                return add((i>>1),wr,wb,to);
            }
            seg[i].res[0][0]=seg[i].res[1][1]=seg[i].res[1][0]=seg[i].res[0][1]=inf;
            seg[i].res[0][0]=wr;
            return add((i>>1),wr,wb,to);
        }
        seg[i]=merge(seg[(i<<1)],seg[(i<<1)^1]);
        return add((i>>1),wr,wb,to);
    }
    node pors(int i,int l,int r,int tl,int tr){
        if(l>r||l>tr||r<tl||tl>tr){
            return fn;
        }
        if(l>=tl&&r<=tr){
            return seg[i];
        }
        int m=(l+r)>>1;
        return merge(pors((i<<1),l,m,tl,tr),pors((i<<1)^1,m+1,r,tl,tr));
    }
}seg;

bool cmp(int a,int b){
    return sz[a]>sz[b];
}

void pre(int u,int par=0){
    sz[u]=1;
    part[u]=par;
    for(auto x:adj[u]){
        if(x==par){
            continue;
        }
        pre(x,u);
        sz[u]+=sz[x];
    }
    sort(adj[u].begin(),adj[u].end());
    if(u!=1){
        adj[u].erase(lower_bound(adj[u].begin(),adj[u].end(),par));
    }
    sort(adj[u].begin(),adj[u].end(),cmp);
}

void makehld(int u=1,int par=1){
   // //cout<<u<<" salam "<<par<<endl;
    parh[u]=par;
    timea++;
    stf[u].first=timea;
    akh[par]=u;
    if((int)adj[u].size()>0){
        makehld(adj[u][0],par);
        for(int i=1;i<(int)adj[u].size();i++){
            makehld(adj[u][i],adj[u][i]);
        }
    }
    stf[u].second=timea;
}

void upd(int u){
    //cout<<u<<" haha "<<" "<<allr[u].size()<<" "<<allb[u].size()<<endl;
    node av=seg.pors(1,0,kaf-1,stf[parh[u]].first,stf[akh[parh[u]]].first);
    int z=min(min(av.res[0][0],av.res[0][1]),min(av.res[1][0],av.res[1][1]));
    mainres-=z;
    if(parh[u]!=1){
        if((av.res[0][0]==z||av.res[0][1]==z)&&(av.res[1][0]==z||av.res[1][1]==z)){
            //hehe
        }
        else if(av.res[0][0]==z||av.res[0][1]==z){
            allb[part[parh[u]]].erase(parh[u]);
        }
        else{
            allr[part[parh[u]]].erase(parh[u]);
        }
    }
    seg.add(stf[u].first+kaf,(int)allr[u].size(),(int)allb[u].size(),val[u]);
    av=seg.pors(1,0,kaf-1,stf[parh[u]].first,stf[akh[parh[u]]].first);
    z=min(min(av.res[0][0],av.res[0][1]),min(av.res[1][0],av.res[1][1]));    
    mainres+=z;
    if(parh[u]!=1){
        if((av.res[0][0]==z||av.res[0][1]==z)&&(av.res[1][0]==z||av.res[1][1]==z)){
            //hehe
        }
        else if(av.res[0][0]==z||av.res[0][1]==z){
            allb[part[parh[u]]].insert(parh[u]);
        }
        else{
            allr[part[parh[u]]].insert(parh[u]);
        }
        return upd(part[parh[u]]);
    }
}

void initialize(int N, std::vector<int> A, std::vector<int> B) {
    n=N;
    for(int i=0;i<n-1;i++){
        adj[A[i]].push_back(B[i]);
        adj[B[i]].push_back(A[i]);
    }
    pre(1);
    makehld();
}
 
int cat(int v) {
    val[v]=1;
    upd(v);
   if(mainres<0||mainres>=inf){
        assert(0);
    }
    return mainres;
}
 
int dog(int v){
    val[v]=2;
    upd(v);
    if(mainres<0||mainres>=inf){
        assert(0);
    }
    return mainres;
}
 
int neighbor(int v) {
    val[v]=0;
    upd(v);
    if(mainres<0||mainres>=inf){
        assert(0);
    }
    return mainres;
}

• Subtask 1: 8 / 8
• Subtask 2: 30 / 30
• Subtask 3: 62 / 62