Submission #904680

#	Time	Username	Problem	Language	Result	Execution time	Memory
904680		bachhoangxuan	Cats or Dogs (JOI18_catdog)	C++17	100 / 100	190 ms	28504 KiB

catdog

#include "catdog.h"
#include<bits/stdc++.h>
using namespace std;
const int inf=2e5;
const int maxn = 1e5+5;
#define pii pair<int,int>
#define fi first
#define se second

struct node{
    int x[2][2];
    node(int a=0,int b=0){
        x[0][0]=a;
        x[1][1]=b;
        x[0][1]=x[1][0]=inf;
    }
    friend node operator+(node a,node b){
        node res(inf,inf);
        for(int i=0;i<=1;i++) for(int j=0;j<=1;j++) for(int p=0;p<=1;p++) for(int q=0;q<=1;q++) res.x[i][j]=min(res.x[i][j],a.x[i][p]+b.x[q][j]+(p^q));
        return res;
    }
};
struct Segtree{
    vector<node> tree;
    void build(int l,int r,int id){
        if(l==r) return;
        int mid=(l+r)>>1;
        build(l,mid,id<<1);build(mid+1,r,id<<1|1);
        tree[id]=tree[id<<1]+tree[id<<1|1];
    }
    void build(int n){
        tree.assign(4*n,node());
        build(1,n,1);
    }
    void update(int l,int r,int id,int p,int va,int vb){
        if(l==r){
            tree[id].x[0][0]+=va;
            tree[id].x[1][1]+=vb;
            return;
        }
        int mid=(l+r)>>1;
        if(p<=mid) update(l,mid,id<<1,p,va,vb);
        else update(mid+1,r,id<<1|1,p,va,vb);
        tree[id]=tree[id<<1]+tree[id<<1|1];
    }
    pii get(){
        int a=min(tree[1].x[0][0],tree[1].x[0][1]),b=min(tree[1].x[1][0],tree[1].x[1][1]);
        return {min(a,b+1),min(b,a+1)};
    }
}ST[maxn];

int n;
vector<int> edge[maxn];

int child[maxn],son[maxn];
void pre_dfs(int u,int p){
    child[u]=1;
    for(int v:edge[u]){
        if(v==p) continue;
        pre_dfs(v,u);
        child[u]+=child[v];
        if(child[v]>child[son[u]]) son[u]=v;
    }
}

int head[maxn],par[maxn],L[maxn],cnt[maxn],pos;

void dfs(int u,int p,int t){
    if(t) head[u]=head[p];
    else head[u]=u;
    L[u]=++pos;
    par[u]=p;
    cnt[head[u]]++;
    if(son[u]) dfs(son[u],u,1);
    for(int v:edge[u]) if(v!=p && v!=son[u]) dfs(v,u,0);
}

void initialize(int N, std::vector<int> A, std::vector<int> B) {
    n=N;
    for(int i=0;i<n-1;i++){
        edge[A[i]].push_back(B[i]);
        edge[B[i]].push_back(A[i]);
    }
    pre_dfs(1,0);
    dfs(1,0,0);
    for(int i=1;i<=n;i++) if(cnt[i]) ST[i].build(cnt[i]);
}

void update(int v,int va,int vb){
    while(v){
        int u=head[v];
        pii x=ST[u].get();
        ST[u].update(1,cnt[u],1,L[v]-L[u]+1,va,vb);
        pii y=ST[u].get();
        va=y.fi-x.fi;
        vb=y.se-x.se;
        v=par[u];
    }
}

int state[maxn];

int cat(int v) {
    state[v]=1;
    update(v,inf,0);
    auto res = ST[1].get();
    return min(res.fi,res.se);
}

int dog(int v) {
    state[v]=2;
    update(v,0,inf);
    auto res = ST[1].get();
    return min(res.fi,res.se);
}

int neighbor(int v) {
    update(v,-(state[v]==1)*inf,-(state[v]==2)*inf);
    state[v]=0;
    auto res = ST[1].get();
    return min(res.fi,res.se);
}

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