Submission #198631

#	Time	Username	Problem	Language	Result	Execution time	Memory
198631		str0ct	Cats or Dogs (JOI18_catdog)	C++14	100 / 100	1198 ms	146040 KiB

catdog

#include "catdog.h"
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const ll INF=INT_MAX/3;
ll mmax=101010;
ll N,Q;
ll catdog[101010];
vector <ll> graph[101010];
priority_queue <pair<ll,ll> > pq[101010];
ll num[101010];
ll group[101010];
ll go[101010];
ll cnt,gnn,gtt;
struct node{
    ll val[2][2];
    void init(){
        val[0][0]=val[1][1]=0;
        val[0][1]=val[1][0]=INF;
    }
    void update(node a,node b){
        for(ll i=0;i<2;i++)fill(val[i],val[i]+2,INF);
        //puts("filled");
        for(ll i=0;i<2;i++)for(ll j=0;j<2;j++)
            for(ll x=0;x<2;x++)for(ll y=0;y<2;y++)//fuuuujkkkkk;
                val[i][y]=min(val[i][y],a.val[i][j]+b.val[x][y]+(j^x));
        //puts("hmmteresting");
        //puts("fucking bald arn...");
    }
};
struct SEG{
     vector <node> tree;
     ll sz;
     void trit(ll l,ll r,ll m){
         //printf("%lld %lld %lld\n",l,r,m);
        if(l==r){
            tree[m].init();
            return;
        }
        ll mid=(l+r)/2;
        trit(l,mid,m*2);
        trit(mid+1,r,m*2+1);
        tree[m].update(tree[m*2],tree[m*2+1]);
        //printf("updated\n");
     }
     void init(ll n){
         sz=n;
         tree.resize(n*4);
         if(sz)trit(1,sz,1);
     }
     void update(ll x,ll l,ll r,ll m,ll a,ll b){
        if(x<l||x>r)return;
        if(l==r){
            tree[m].val[0][0]+=a;
            tree[m].val[1][1]+=b;
            return;
        }
        ll mid=(l+r)/2;
        update(x,l,mid,m*2,a,b);
        update(x,mid+1,r,m*2+1,a,b);
        tree[m].update(tree[m*2],tree[m*2+1]);
     }
     pair<ll,ll> getf(){
        ll a=min(tree[1].val[0][0],tree[1].val[0][1]);
        ll b=min(tree[1].val[1][0],tree[1].val[1][1]);
        return {min(a,b+1),min(a+1,b)};
     }
};
SEG HLD[101010];
ll dfs1(ll now,ll par){
    //printf("%lld\n",now);
    for(auto i:graph[now])if(i!=par){
        num[now]+=dfs1(i,now);
        pq[now].push({num[i],i});
    }
    return ++num[now];
}
void dfs2(ll now,ll par){
    if(!gnn){
        gnn=++gtt;
        go[gnn]=par;
    }
    group[now]=gnn;
    num[now]=++cnt;
    while(!pq[now].empty()){
        dfs2(pq[now].top().second,now);
        pq[now].top();
        pq[now].pop();
    }
    HLD[gnn].init(cnt);
    gnn=0;cnt=0;
    //printf("%lld\n",now);
}
void initialize(int n,vector<int> A,vector<int> B) {
    N=n;
    for(int i=0;i<A.size();i++)graph[A[i]].push_back(B[i]);
    for(int i=0;i<A.size();i++)graph[B[i]].push_back(A[i]);
    dfs1(1,0);
    dfs2(1,0);
}
void hldupdate(ll now,ll a,ll b){
    while(now){
        //printf("%lld\n",now);
        pair<ll,ll> p=HLD[group[now]].getf();
        HLD[group[now]].update(num[now],1,HLD[group[now]].sz,1,a,b);
        pair<ll,ll> q=HLD[group[now]].getf();
        a=q.first-p.first;
        b=q.second-p.second;
        now=go[group[now]];
    }
}
int cat(int v){
	hldupdate(v,mmax,0);
	catdog[v]=1;
	return min(HLD[1].getf().first,HLD[1].getf().second);
}
int dog(int v){
	hldupdate(v,0,mmax);
	catdog[v]=2;	
	return min(HLD[1].getf().first,HLD[1].getf().second);
}
int neighbor(int v){
    if(catdog[v]==1)hldupdate(v,-mmax,0);  
	else hldupdate(v,0,-mmax);
	catdog[v]=0;
	return min(HLD[1].getf().first,HLD[1].getf().second);
}

Compilation message (stderr)

catdog.cpp: In function 'void initialize(int, std::vector<int>, std::vector<int>)':
catdog.cpp:96:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<A.size();i++)graph[A[i]].push_back(B[i]);
                 ~^~~~~~~~~
catdog.cpp:97:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<A.size();i++)graph[B[i]].push_back(A[i]);
                 ~^~~~~~~~~

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