Submission #1122136

#	Time	Username	Problem	Language	Result	Execution time	Memory
1122136		imarn	Cats or Dogs (JOI18_catdog)	C++14	100 / 100	538 ms	33660 KiB

catdog

#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define plx pair<ll,int>
#define f first
#define s second
#define pb push_back
#define all(x) x.begin(),x.end()
#define szz(r) (ll)r.size()
#define vi vector<int>
#define vvi vector<vi>
#define pp pair<ll,int>
#define ub(x,i) upper_bound(all(x),i)-x.begin()
using namespace std;
const int mxn=1e5+5;
vector<int>g[mxn];
int sz[mxn],id[mxn],head[mxn],pr[mxn],cu=0,lst[mxn],mode[mxn]{0};
struct node{
    ll aa,ab,ba,bb;
    node operator+(node b){
        node rs;
        if(aa==-1)return b;
        if(b.aa==-1)return (rs={aa,ab,ba,bb});
        rs.aa=min({aa+b.aa,aa+b.ba+1,ab+b.aa+1,ab+b.ba});
        rs.ab=min({aa+b.ab,aa+b.bb+1,ab+b.ab+1,ab+b.bb});
        rs.ba=min({ba+b.aa,ba+b.ba+1,bb+b.ba,bb+b.aa+1});
        rs.bb=min({ba+b.ab,ba+b.bb+1,bb+b.bb,bb+b.ab+1});
        return rs;
    }
}t[4*mxn],sum[mxn];
void print(node x){
    cout<<x.aa<<' '<<x.ab<<' '<<x.ba<<' '<<x.bb<<'\n';
}
void build(int i,int l,int r){
    if(l==r){
        t[i]={0,(ll)1e9,(ll)1e9,0},sum[l]={0,(ll)1e9,(ll)1e9,0};
        return;
    }
    int m=(l+r)>>1;
    build(2*i,l,m);build(2*i+1,m+1,r);
    t[i]=t[2*i]+t[2*i+1];
}
void uni(int i,int l){
    if(mode[l]==0){
        t[i].aa=sum[l].aa;
        t[i].bb=sum[l].bb;
    }
    if(mode[l]==1){
        t[i].aa+=sum[l].aa;
        t[i].bb=1e9;
    }
    if(mode[l]==2){
        t[i].bb+=sum[l].bb;
        t[i].aa=1e9;
    }
}
void update(int i,int l,int r,int idx,int v){
    if(r<idx||l>idx)return;
    if(l==r){
        if(v==1){
            t[i]={0,(ll)1e9,(ll)1e9,(ll)1e9};
            uni(i,l);
            return;
        }
        else if(v==2){
            t[i]={(ll)1e9,(ll)1e9,(ll)1e9,0};
            uni(i,l);
            return;
        }
        else if(v==0){
            t[i]={0,(ll)1e9,(ll)1e9,0};
            uni(i,l);
            return;
        }
        else {
            if(mode[l]==0)t[i]={0,(ll)1e9,(ll)1e9,0};
            else if(mode[l]==1)t[i]={0,(ll)1e9,(ll)1e9,(ll)1e9};
            else if(mode[l]==2)t[i]={(ll)1e9,(ll)1e9,(ll)1e9,0};
            uni(i,l);
            return;
        }
    }int m=(l+r)>>1;
    update(2*i,l,m,idx,v);update(2*i+1,m+1,r,idx,v);
    t[i]=t[2*i]+t[2*i+1];
}
node qr(int i,int l,int r,int tl,int tr){
    if(r<tl||l>tr)return {-1,-1,-1,-1};
    if(r<=tr&&l>=tl){
        return t[i];
    }
    int m=(l+r)>>1;
    return qr(2*i,l,m,tl,tr)+qr(2*i+1,m+1,r,tl,tr);
}
void dfssz(int u,int p){
    sz[u]=1;pr[u]=p;
    for(auto v:g[u]){
        if(v==p)continue;
        dfssz(v,u);sz[u]+=sz[v];
    }
}
void hld(int u,int p,int tp){
    head[u]=tp;id[u]=++cu;lst[tp]=id[u];
    int hv=-1;
    for(auto v:g[u]){
        if(v==p)continue;
        if(hv==-1||sz[hv]<sz[v])hv=v;
    }if(hv==-1)return;
    hld(hv,u,tp);
    for(auto v:g[u]){
        if(v==hv||v==p)continue;
        hld(v,u,v);
    }
}int n;
void initialize(int N, std::vector<int> A, std::vector<int> B){
    n=N;
    for(int i=0;i<N-1;i++){
        g[A[i]].pb(B[i]);g[B[i]].pb(A[i]);
    }dfssz(1,-1);hld(1,1,1);
    build(1,1,n);
}
int cat(int v){
    int x=v;
    while(x!=-1){
        node sp=qr(1,1,n,id[head[x]],lst[head[x]]);
        if(pr[head[x]]!=-1){
            int idx=id[pr[head[x]]];
            sum[idx].aa -= min({sp.aa,sp.ab,sp.ba+1,sp.bb+1});
            sum[idx].bb -= min({sp.bb,sp.ba,sp.aa+1,sp.ab+1});
        }if(x==v)mode[id[x]]=1,update(1,1,n,id[x],1);
        else update(1,1,n,id[x],4);
        sp=qr(1,1,n,id[head[x]],lst[head[x]]);
        if(pr[head[x]]!=-1){
            int idx=id[pr[head[x]]];
            sum[idx].aa += min({sp.aa,sp.ab,sp.ba+1,sp.bb+1});
            sum[idx].bb += min({sp.bb,sp.ba,sp.aa+1,sp.ab+1});
        }x=pr[head[x]];
    }
    node rs=qr(1,1,n,id[1],lst[1]);
    return min({rs.aa,rs.ab,rs.ba,rs.bb});
}

int dog(int v) {
    int x=v;
    while(x!=-1){
        node sp=qr(1,1,n,id[head[x]],lst[head[x]]);
        if(pr[head[x]]!=-1){
            int idx=id[pr[head[x]]];
            sum[idx].aa -= min({sp.aa,sp.ab,sp.ba+1,sp.bb+1});
            sum[idx].bb -= min({sp.bb,sp.ba,sp.aa+1,sp.ab+1});
        }if(x==v)mode[id[x]]=2,update(1,1,n,id[x],2);
        else update(1,1,n,id[x],4);
        sp=qr(1,1,n,id[head[x]],lst[head[x]]);
        if(pr[head[x]]!=-1){
            int idx=id[pr[head[x]]];
            sum[idx].aa += min({sp.aa,sp.ab,sp.ba+1,sp.bb+1});
            sum[idx].bb += min({sp.bb,sp.ba,sp.aa+1,sp.ab+1});
        }x=pr[head[x]];
    }
    node rs=qr(1,1,n,id[1],lst[1]);
    return min({rs.aa,rs.ab,rs.ba,rs.bb});
}
int neighbor(int v) {
    int x=v;
    while(x!=-1){
        node sp=qr(1,1,n,id[head[x]],lst[head[x]]);
        if(pr[head[x]]!=-1){
            int idx=id[pr[head[x]]];
            sum[idx].aa -= min({sp.aa,sp.ab,sp.ba+1,sp.bb+1});
            sum[idx].bb -= min({sp.bb,sp.ba,sp.aa+1,sp.ab+1});
        }if(x==v)mode[id[x]]=0,update(1,1,n,id[x],0);
        else update(1,1,n,id[x],4);
        sp=qr(1,1,n,id[head[x]],lst[head[x]]);
        if(pr[head[x]]!=-1){
            int idx=id[pr[head[x]]];
            sum[idx].aa += min({sp.aa,sp.ab,sp.ba+1,sp.bb+1});
            sum[idx].bb += min({sp.bb,sp.ba,sp.aa+1,sp.ab+1});
        }x=pr[head[x]];
    }
    node rs=qr(1,1,n,id[1],lst[1]);
    return min({rs.aa,rs.ab,rs.ba,rs.bb});
}
/*int main(){
    initialize(10,{1,1,1,1,1,1,1,1,1},{2,3,4,5,6,7,8,9,10});
    cout<<cat(6)<<'\n';
    cout<<dog(5)<<'\n';
}*/

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