Submission #1014461

#	Time	Username	Problem	Language	Result	Execution time	Memory
1014461		vjudge1	Cats or Dogs (JOI18_catdog)	C++17	100 / 100	439 ms	25856 KiB

catdog

#include "catdog.h"
#define M 100100
#include<bits/stdc++.h>
using namespace std;
int type[M],sz[M],id[M],top[M],out[M],hev[M],CC,par[M],osc[M],BG=1e9;
struct dpstruct{
    int cc,cd,dc,dd;
    dpstruct(){cc=dd=0,cd=dc=1;}
    dpstruct(int x){cc=dd=0,cd=dc=BG;}
    inline friend dpstruct operator +(dpstruct a,dpstruct b){
        dpstruct c;
        swap(a,b);
        c.cc=min({a.cc+b.cc,a.cd+b.dc,BG});
        c.cd=min({a.cc+b.cd,a.cd+b.dd,BG});
        c.dc=min({a.dd+b.dc,a.dc+b.cc,BG});
        c.dd=min({a.dd+b.dd,a.dc+b.cd,BG});
        return c;
    }
    inline void sub(dpstruct x){
        int dog=min(x.cd,x.dd);
        int cat=min(x.cc,x.dc);
        dog=min(dog,cat+1);
        cat=min(cat,dog+1);
        cc-=cat;
        cd-=dog;
        dc-=cat;
        dd-=dog;
    }
    inline void add(dpstruct x){
        int dog=min(x.cd,x.dd);
        int cat=min(x.cc,x.dc);
        dog=min(dog,cat+1);
        cat=min(cat,dog+1);
        cc+=cat;
        cd+=dog;
        dc+=cat;
        dd+=dog;
    }
    inline int an(){return min({cc,cd,dc,dd});}
} T[1<<18],fl[M];
vector<int>adj[M];
dpstruct query(int i,int l,int r,int ll,int rr){
    if(ll>r|l>rr)return dpstruct(0);
    if(ll<=l&&r<=rr)return T[i];
    return query(i*2,l,l+r>>1,ll,rr)+
        query(i*2+1,l+r+2>>1,r,ll,rr);
}
void upd(int i,int l,int r,int p,dpstruct x){
    if(l==r)return void(T[i]=x);
    if(p<=l+r>>1)upd(i*2,l,l+r>>1,p,x);
    else upd(i*2+1,l+r+2>>1,r,p,x);
    T[i]=T[i*2]+T[i*2+1];
}
void dfs1(int n){
    sz[n]=1;
    for(auto i:adj[n]) if(i-par[n])
        par[i]=n,dfs1(i),sz[n]+=sz[i],
        hev[n]=(sz[hev[n]]<sz[i]?i:hev[n]);
}
void dfs2(int n){
    osc[id[n]=++CC]=n;
    top[n]=(n-hev[par[n]]?n:top[par[n]]);
    out[top[n]]=CC;
    if(hev[n])dfs2(hev[n]);
    for(auto i:adj[n])  
        if(i-par[n]&&i-hev[n])
            dfs2(i);
}
void initialize(int N, std::vector<int> A, std::vector<int> B) {
    for(int i=0;i<N-1;i++)
        adj[A[i]].push_back(B[i]),
        adj[B[i]].push_back(A[i]);
    dfs1(1);
    dfs2(1);
}
dpstruct gedan(int chain){
    return query(1,1,CC,id[top[chain]],out[top[chain]]);    
}
dpstruct idk(int t,dpstruct x){
    if(t>1)x.cc=x.dc=BG;
    else if(t)x.cd=x.dd=BG;
    return x;
}
void redo(int n){
    if(!n)return;
    fl[par[top[n]]].sub(gedan(n));
    upd(1,1,CC,id[n],idk(type[n],fl[n]));
    fl[par[top[n]]].add(gedan(n));
    return redo(par[top[n]]);
}
int cat(int v) {
    type[v]=1;
    redo(v);
    return gedan(1).an();
}

int dog(int v) {
    type[v]=2;
    redo(v);
    return gedan(1).an();
}

int neighbor(int v) {
    type[v]=0;
    redo(v);
    return gedan(1).an();
}

Compilation message (stderr)

catdog.cpp: In function 'dpstruct query(int, int, int, int, int)':
catdog.cpp:43:10: warning: suggest parentheses around comparison in operand of '|' [-Wparentheses]
   43 |     if(ll>r|l>rr)return dpstruct(0);
      |        ~~^~
catdog.cpp:45:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   45 |     return query(i*2,l,l+r>>1,ll,rr)+
      |                        ~^~
catdog.cpp:46:24: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   46 |         query(i*2+1,l+r+2>>1,r,ll,rr);
      |                     ~~~^~
catdog.cpp: In function 'void upd(int, int, int, int, dpstruct)':
catdog.cpp:50:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   50 |     if(p<=l+r>>1)upd(i*2,l,l+r>>1,p,x);
      |           ~^~
catdog.cpp:50:29: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   50 |     if(p<=l+r>>1)upd(i*2,l,l+r>>1,p,x);
      |                            ~^~
catdog.cpp:51:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   51 |     else upd(i*2+1,l+r+2>>1,r,p,x);
      |                    ~~~^~

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