Submission #477538

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

catdog

#include <bits/stdc++.h>
#include "catdog.h"
#define DIM 100010
#define INF 2000000000
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){

    for (auto vecin : L[nod])
        if (vecin != tata)
            dfs (vecin,nod);

    if (!v[nod])
        dp[nod][1] = dp[nod][2] = 0;
    else {
        if (v[nod] == 1)
            dp[nod][1] = 0, dp[nod][2] = INF;
        else
            dp[nod][1] = INF, dp[nod][2] = 0;
    }

    for (auto vecin : L[nod]){
        if (vecin == tata)
            continue;
        dp[nod][1] += min (dp[vecin][1],dp[vecin][2]+1);
        dp[nod][2] += min (dp[vecin][2],dp[vecin][1]+1);
    }

}


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

    memset (dp,0,sizeof dp);

    dfs (1,0);

    return 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][1],dp[1][2]);
}

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

    memset (dp,0,sizeof dp);

    dfs (1,0);

    return 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