Submission #778809

#	Time	Username	Problem	Language	Result	Execution time	Memory
778809		Ahmed57	Cats or Dogs (JOI18_catdog)	C++17	100 / 100	364 ms	26828 KiB

catdog

#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")

#include <bits/stdc++.h>
#include "catdog.h"
using namespace std;
vector<int> adj[200001];
int n;
int val[200001];
int sz[200001];
int P[200001];
int arr[200001];
int root[200001];
int down[200001];
void co(int i,int pr){
    sz[i] = 1;
    for(auto j:adj[i]){
        if(j==pr)continue;
        co(j,i);
        sz[i]+=sz[j];
    }
}
int no = 1;
void dfs(int i,int pr,int ro){
    val[i] = no++;
    root[i] = ro;
    down[ro] = i;
    P[i] = pr;
    int ma = -1 , su = 0;
    for(auto j:adj[i]){
        if(j==pr)continue;
        if(ma<sz[j]){
            ma = sz[j];
            su = j;
        }
    }
    if(ma!=-1)dfs(su,i,ro);
    for(auto j:adj[i]){
        if(j==pr||j==su)continue;
        dfs(j,i,j);
    }
}
struct node{
  int dp[2][2];
  node(){
    for(int i = 0;i<2;i++){
      for(int j = 0;j<2;j++){
        dp[i][j] = 1e5;
      }
    }
  }
}seg[400001];
node combine(node a,node b){
    node ans;
    for(int i = 0;i<2;i++){
      for(int j = 0;j<2;j++){
        for(int k = 0;k<2;k++){
          for(int l = 0;l<2;l++){
            ans.dp[i][j] = min(ans.dp[i][j],a.dp[i][k]+b.dp[l][j]+(k != l));
          }
        }
      }
    }
    return ans;
}
void build(int l,int r,int p){
    //cout<<l<<" "<<r<<" "<<p<<endl;
    if(l==r){
        seg[p].dp[0][0] = 0;
        seg[p].dp[1][1] = 0;
        seg[p].dp[0][1] = 1e5;
        seg[p].dp[1][0] = 1e5;
        return ;
    }
    int md = (l+r)/2;
    build(l,md,p*2);
    build(md+1,r,p*2+1);
    seg[p] = combine(seg[p*2],seg[p*2+1]);
}
void update(int l,int r,int p,int idx,pair<int,int> val){
    if(l==r){
        seg[p].dp[0][0] = val.first;
        seg[p].dp[1][1] = val.second;
        seg[p].dp[0][1] = 1e5;
        seg[p].dp[1][0] = 1e5;
        return ;
    }
    int md = (l+r)/2;
    if(idx<=md)update(l,md,p*2,idx,val);
    else update(md+1,r,p*2+1,idx,val);
    seg[p] = combine(seg[p*2],seg[p*2+1]);
}
node query(int l,int r,int p,int lq,int rq){
    //cout<<p<<" "<<l<<" "<<r<<endl;
    if(l>=lq&&r<=rq)return seg[p];
    int md = (l+r)/2;
    if(lq<=md&&rq>=md+1){
        return combine(query(l,md,p*2,lq,rq),query(md+1,r,p*2+1,lq,rq));
    }
    if(lq<=md){
        return query(l,md,p*2,lq,rq);
    }else return query(md+1,r,p*2+1,lq,rq);
}
int coll[100001];
int sum[100001][2];
int prv[100001][2];
node upd(int x){
    if(coll[x]==0)update(1, n,1, val[x], {sum[x][0], 1e5});
    if(coll[x]==1)update(1, n,1, val[x], {1e5, sum[x][1]});
    if(coll[x]==2)update(1, n,1, val[x], {sum[x][0], sum[x][1]});
    x = root[x];
    //cout<<x<<" "<<val[x]<<" "<<val[down[x]]<<"rng"<<endl;
    node ans = query(1,n,1,val[x],val[down[x]]);
    if(x==1){
        return ans;
    }
    for(int i = 0;i<2;i++){
        sum[P[x]][i] -= prv[x][i];
        int best = 1e5;
        for(int j = 0;j<2;j++){
            best = min(best,ans.dp[i][j]);
            best = min(best,ans.dp[i ^ 1][j] + 1);
        }
        prv[x][i] = best;
        sum[P[x]][i]+=prv[x][i];
    }
    return upd(P[x]);
}
void initialize(int N,vector<int>A,vector<int>B){
    n = N;
    coll[0] = 2;coll[N] = 2;
    for(int i = 0;i<N-1;i++){
        coll[i+1] = 2;
        adj[A[i]].push_back(B[i]);
        adj[B[i]].push_back(A[i]);
    }
    //cout<<"ff"<<endl;
    co(1,1);
    //cout<<"ff"<<endl;
    dfs(1,1,1);
    //cout<<"ff"<<endl;
    build(1,n,1);
    //cout<<"ff"<<endl;
}
int cat(int v){
    coll[v] = 0;
    //cout<<"ff"<<endl;
    node ans = upd(v);
    int best = 1e5;
    for(int i = 0;i<2;i++){
        for(int j = 0;j<2;j++){
            best = min(best,ans.dp[i][j]);
        }
    }
    return best;
}int dog(int v){
    coll[v] = 1;
    node ans = upd(v);
    int best = 1e5;
    for(int i = 0;i<2;i++){
        for(int j = 0;j<2;j++){
            best = min(best,ans.dp[i][j]);
        }
    }
    return best;
}int neighbor(int v){
    coll[v] = 2;
    node ans = upd(v);
    int best = 1e5;
    for(int i = 0;i<2;i++){
        for(int j = 0;j<2;j++){
            best = min(best,ans.dp[i][j]);
        }
    }
    return best;
}/*
int main(){
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int N = 5;
    vector<int> A = {1,2,2,4};
    vector<int> B = {2,3,4,5};
    initialize(N,A,B);
    cout<<"hh"<<endl;
    cout<<cat(3)<<"jjjjjjjjjjjj"<<endl;
    cout<<dog(5)<<"jjjjjjjjjjjj"<<endl;
    cout<<dog(1)<<"jjjjjjjjjjjj"<<endl;
    cout<<cat(2)<<"jjjjjjjjjjjj"<<endl;
    cout<<neighbor(2)<<"jjjjjjjjjjjj"<<endl;
}*/

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