Submission #916673

#	Time	Username	Problem	Language	Result	Execution time	Memory
916673		manizare	Cats or Dogs (JOI18_catdog)	C++14	100 / 100	213 ms	73016 KiB

catdog

#include<bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")


#define pb push_back
#define F first
#define S second 
#define all(a) a.begin(),a.end()
#define pii pair <int,int>
#define ll long long
#define sz(v) (int)v.size()
#define rep(i , a , b) for(int i=a;i <= (b);i++)
#define per(i , a , b) for(int i=a;i >= (b);i--)
#define deb(x) cerr<<#x << " : " << x << "\n"; 

using namespace std ;   
const int maxn = 4e5 + 10 ,  mod = 1e9 + 7 , inf =1e9  ;
int n , c[maxn] , par[maxn] , d[maxn] ,cnt = 2 , s[maxn][2] , mark[maxn];
vector <int> G[maxn] ;

struct node{
    int a[2][2] ;
};

node operator+(node a, node b){
    node res ;
    rep(i,0,1)rep(j,0,1)res.a[i][j] = inf ;
    rep(i,0,1)
    rep(j,0,1)
    rep(k,0,1)
    rep(z,0,1)
    res.a[i][j] = min(res.a[i][j] , a.a[i][k] + b.a[z][j] + (k!=z)) ;
    return res; 
}

struct segtree{
    int id ; 
    vector <int> az ; 
    vector <node> seg;
    void UPD(int x ,int p ,int l  , int r ){
        int mid = (l+r)/2, pl=p<<1 , pr =p<<1|1 ;
        if(x > r || x < l)return ;
        if(l==r){
            seg[p].a[0][1] = seg[p].a[1][0] = seg[p].a[0][0] = seg[p].a[1][1] = inf ;
            if(mark[az[x]] == 0 || mark[az[x]] == 1)seg[p].a[0][0] = s[az[x]][0] ;
            if(mark[az[x]] == 0 || mark[az[x]] == 2)seg[p].a[1][1] = s[az[x]][1] ;
            return ; 
        }
        UPD(x,pl,l,mid);
        UPD(x,pr,mid+1,r); 
        seg[p] = seg[pl] + seg[pr] ;
    }
    void upd(int x){
        UPD(x,1 ,0 ,sz(az)-1) ;
    }
    void bui(){
        rep(i , 0 , 4*sz(az)+2){
            node res ;
            seg.pb(res) ;
        }
        rep(i , 0 , sz(az)-1){
            upd(i);
        }
    }

};
segtree h[maxn] ;int   sb[maxn] ; 

void d1(int v, int p=0){
    sb[v] = 1; 
    for(int u : G[v]){
        if(u == p)continue ;
        d1(u , v); 
        sb[v] += sb[u] ;
    }
}
void d2(int v , int p =0){
    vector <pii> vec ;
    for(int u : G[v]){
        if(u == p)continue ;
        vec.pb({sb[u] , u}) ;
    }
    sort(all(vec)) ;
    per(i , sz(vec)-1 , 0){
        int u = vec[i].S ;
        if(i == sz(vec)-1){
            par[u] = par[v] ;
            c[u]=c[v] ;
            h[c[u]].az.pb(u) ;
            d[u] = d[v] + 1 ;
            d2(u , v);
        }else{
            par[u] = v ; 
            c[u] = cnt ;
            h[cnt].az.pb(u) ;
            cnt++;
            d[u] =0 ;
            d2(u , v) ;
        }
    }
    if(sz(vec)==0){
        h[c[v]].bui() ;
    }
}

void ch(int v){
    if(c[v]==1){
        h[c[v]].upd(d[v]);
        return ;
    }
    rep(i , 0 , 1)
s[par[v]][i]-=min(min(h[c[v]].seg[1].a[i][0],h[c[v]].seg[1].a[i][1]),min(h[c[v]].seg[1].a[!i][0],h[c[v]].seg[1].a[!i][1])+1) ;
    h[c[v]].upd(d[v]); 
    rep(i , 0 , 1)
s[par[v]][i]+=min(min(h[c[v]].seg[1].a[i][0],h[c[v]].seg[1].a[i][1]),min(h[c[v]].seg[1].a[!i][0],h[c[v]].seg[1].a[!i][1])+1) ;
    ch(par[v]) ;
}

void initialize(int N , vector <int> A , vector <int> B){
    n = N ;
    rep(i , 0 , n-2){
        G[A[i]].pb(B[i]);
        G[B[i]].pb(A[i]);
    }
    d1(1) ;
    par[1] = 1;
    h[1].az.pb(1) ;
    c[1] = 1;
    d2(1); 
}
int ans(){
    int f = inf ;
    rep(i , 0 , 1){
        rep(j , 0 ,1){
            f =min(f , h[1].seg[1].a[i][j]) ;
        }
    }
    return f ;
}
int neighbor(int v){
    mark[v] = 0 ;
    ch(v) ;
    return ans() ;
}
int cat(int v){
    mark[v] =1 ;
    ch(v) ;
    return ans() ;
}
int dog(int v){
    mark[v]= 2 ;
    ch(v);
    return ans() ;
}
/*
signed main(){
    ios::sync_with_stdio(0) ;cin.tie(0);
    int n , q;
    cin >> n >> q;
    vector <int> a , b ;
    rep(i , 1, n-1){
        int v,  u;
        cin >> v >> u ;
        a.pb(v);
        b.pb(u) ;
    }
    initialize(n , a, b);
    while(q--){
        int t  , v ;
        cin >> t >> v;
        if(t==0){
            cout << neighbor(v)  << "\n" ;
        }else if(t==1){
            cout << cat(v) << "\n" ;
        }else{
            cout << dog(v) << "\n" ;
        }
    }
}
*/

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