Submission #477738

#	Time	Username	Problem	Language	Result	Execution time	Memory
477738		nicolaalexandra	Cats or Dogs (JOI18_catdog)	C++14	100 / 100	250 ms	43052 KiB

catdog

#include <bits/stdc++.h>
#include "catdog.h"
#define DIM 100010
#define INF 1000000000
using namespace std;

vector <int> L[DIM],a,b;
int v[DIM];
int n,i,q,tip,x,nr_chains;

vector <int> chains[DIM];
int whatChain[DIM],positionInChain[DIM],chainFatherNode[DIM],s[DIM];

struct segment_tree{
    long long dp[2][2];
};

vector <segment_tree> aint[DIM];

void dfs (int nod, int tata){

    s[nod] = 1;
    int ok = 0, maxi = 0, heavy_son = 0;

    for (auto vecin : L[nod])
        if (vecin != tata){
            ok = 1;
            dfs (vecin,nod);
            s[nod] += s[vecin];
            if (s[vecin] > maxi)
                maxi = s[vecin], heavy_son = vecin;
        }

    if (!ok){
        nr_chains++;
        chains[nr_chains].push_back(0);
        chains[nr_chains].push_back(nod);
        positionInChain[nod] = 1;
        whatChain[nod] = nr_chains;
    } else {

        chains[whatChain[heavy_son]].push_back(nod);
        whatChain[nod] = whatChain[heavy_son];
        positionInChain[nod] = chains[whatChain[heavy_son]].size()-1;

        for (auto vecin : L[nod]){
            if (vecin != tata && vecin != heavy_son)
                chainFatherNode[whatChain[vecin]] = nod;
        }
    }
}

void update_nod (int chain, int nod){
    int fiu_st = nod<<1, fiu_dr = (nod<<1)|1;

    for (int i=0;i<=1;i++)
        for (int j=0;j<=1;j++){

            long long mini = 1LL * INF * INF;
            for (int i2=0;i2<=1;i2++)
                for (int j2=0;j2<=1;j2++)
                    mini = min (mini,aint[chain][fiu_st].dp[i][i2] + aint[chain][fiu_dr].dp[j2][j] + (i2 != j2));

            aint[chain][nod].dp[i][j] = mini;
        }

}

void build (int chain, int nod, int st, int dr){
    if (st == dr){
        aint[chain][nod].dp[0][0] = aint[chain][nod].dp[1][1] = 0;
        aint[chain][nod].dp[0][1] = aint[chain][nod].dp[1][0] = INF;
        return;
    }
    int mid = (st+dr)>>1;
    build (chain,nod<<1,st,mid);
    build (chain,(nod<<1)|1,mid+1,dr);

    update_nod (chain,nod);
}

void update_aint (int chain, int nod, int st, int dr, int poz, long long val, long long val2){
    if (st == dr){
        aint[chain][nod].dp[0][0] += val;
        aint[chain][nod].dp[1][1] += val2;

        return;
    }
    int mid = (st+dr)>>1;
    if (poz <= mid)
        update_aint(chain,nod<<1,st,mid,poz,val,val2);
    else update_aint(chain,(nod<<1)|1,mid+1,dr,poz,val,val2);

    update_nod(chain,nod);
}


int query (){

    long long mini = 1LL * INF * INF;
    for (int i=0;i<=1;i++)
        for (int j=0;j<=1;j++)
            mini = min (mini,aint[ whatChain[1] ][1].dp[i][j]);

    return mini;
}

void initialize(int _n, vector<int> A, vector<int> B) {
    n = _n;
    for (int i=0;i<n-1;i++){
        L[A[i]].push_back(B[i]);
        L[B[i]].push_back(A[i]);
    }

    dfs (1,0);

    for (int i=1;i<=nr_chains;i++){
        aint[i].resize(chains[i].size()*4);
        //for (int j=0;j<=chains[i].size()*4;j++)
          //  aint[i].push_back();
        build (i,1,1,chains[i].size()-1);
    }

}


void update (int x, long long val, long long val2){

    int chain = whatChain[x];

    long long old_val0 = min (aint[chain][1].dp[0][0],aint[chain][1].dp[1][0]);
    long long old_val1 = min (aint[chain][1].dp[0][1],aint[chain][1].dp[1][1]);

    update_aint(chain,1,1,chains[chain].size()-1,positionInChain[x],val,val2);


    long long new_val0 = min (aint[chain][1].dp[0][0],aint[chain][1].dp[1][0]);
    long long new_val1 = min (aint[chain][1].dp[0][1],aint[chain][1].dp[1][1]);

    int new_x = chainFatherNode[chain];

    if (new_x)
        update (new_x, min(new_val0,new_val1+1) - min(old_val0,old_val1+1), min(new_val1,new_val0+1) - min(old_val1,old_val0+1));

}


int cat(int x) {
    v[x] = 1;
    update (x,0,INF);
    return query();
}

int dog(int x) {
    v[x] = 2;
    update (x,INF,0);

    return query();
}

int neighbor(int x) {
    if (v[x] == 1)
        update (x,0,-INF);
    if (v[x] == 2)
        update (x,-INF,0);

    v[x] = 0;

    return query();
}

/*
int main (){

    ifstream cin ("date.in");
    ofstream cout ("date.out");


    cin>>n;
    for (i=0;i<n-1;i++){
        int x,y;
        cin>>x>>y;
        a.push_back(x);
        b.push_back(y);
        //cin>>a[i]>>b[i];
    }

    initialize(n,a,b);

    cin>>q;
    for (;q--;){
        cin>>tip>>x;
        if (tip == 1)
            cout<<cat(x)<<"\n";
        else {
            if (tip == 2)
                cout<<dog(x)<<"\n";
            else cout<<neighbor(x)<<"\n";
        }
    }



    return 0;
}
*/

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