Submission #477532

#	Time	Username	Problem	Language	Result	Execution time	Memory
477532		nicolaalexandra	Cats or Dogs (JOI18_catdog)	C++14	38 / 100	3078 ms	7972 KiB

catdog

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

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


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]);
    }
}

void dfs (int nod, int tata){

    int ok = 0;
    for (auto vecin : L[nod])
        if (vecin != tata){
            ok = 1;
            dfs (vecin,nod);
        }

    if (!ok){

        if (v[nod] == 1)
            dp[nod][0] = dp[nod][2] = 1;
        if (v[nod] == 2)
            dp[nod][0] = dp[nod][1] = 1;

    } else {


        if (!v[nod]){ /// nu am nimic in nod

            for (auto vecin : L[nod]){
                if (vecin == tata)
                    continue;

                dp[nod][0] += min(dp[vecin][0],min(dp[vecin][1]+1,dp[vecin][2]+1));

                dp[nod][1] += min (dp[vecin][1],min(dp[vecin][0],dp[vecin][2]+1));

                dp[nod][2] += min (dp[vecin][2],min(dp[vecin][0],dp[vecin][1]+1));

            }

        } else {
            if (v[nod] == 1){ /// cat

                dp[nod][0] = dp[nod][2] = 1;
                for (auto vecin : L[nod]){
                    if (vecin == tata)
                        continue;

                    int val = min (dp[vecin][0],min(dp[vecin][1],dp[vecin][2]+1));

                    dp[nod][0] += val;
                    dp[nod][1] += val;
                    dp[nod][2] += val;

                }


            } else { /// dog

                dp[nod][0] = dp[nod][1] = 1;
                for (auto vecin : L[nod]){
                    if (vecin == tata)
                        continue;

                    int val = min (dp[vecin][0],min(dp[vecin][2],dp[vecin][1]+1));

                    dp[nod][0] += val;
                    dp[nod][1] += val;
                    dp[nod][2] += val;
                }

            }

        }

    }

}


int cat(int x) {
    v[x] = 1;

    memset (dp,0,sizeof dp);


    dfs (1,0);

    return min (dp[1][0],min(dp[1][1],dp[1][2]));
}

int dog(int x) {
    v[x] = 2;

    memset (dp,0,sizeof dp);

    dfs (1,0);

    return min (dp[1][0],min(dp[1][1],dp[1][2]));
}

int neighbor(int x) {
    v[x] = 0;

    memset (dp,0,sizeof dp);

    dfs (1,0);

    return min (dp[1][0],min(dp[1][1],dp[1][2]));
}

/*
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: 0 / 62