Submission #363246

#	Time	Username	Problem	Language	Result	Execution time	Memory
363246		teewar	Cats or Dogs (JOI18_catdog)	C++14	0 / 100	1 ms	364 KiB

catdog

#include "catdog.h"
#include <algorithm>

using namespace std;

const int MAX = 1000;
const int INF = 1e9;

int d[MAX + 10][3];
vector<int> g[MAX + 10];
int best[MAX + 10];
int st[MAX + 10];



void dfs(int v, int p = -1) {
    d[v][st[v]] = 0;
    if(st[v] == 0) {
        d[v][1] = d[v][2] = 0;
    }
    for(auto to: g[v]) {
        if(p == to) {
            continue;
        }
        dfs(to, v);
        d[v][st[v]] += min({d[to][0], d[to][1] + 1, d[to][2] + 1, d[to][st[v]]});
        if(st[v] == 0) {
            d[v][1] += min({d[to][0], d[to][1] + 1, d[to][2] + 1, d[to][1]});
            d[v][1] += min({d[to][0], d[to][1] + 1, d[to][2] + 1, d[to][2]});
        }
    }
}


int ans() {
    for(int i = 0; i < MAX; ++i) {
        for(int j = 0; j < 3; ++j) {
            d[i][j] = INF;
        }
    }
    dfs(0);
    return min({d[0][0], d[0][1], d[0][2]});
}

void initialize(int n, vector<int> a, vector<int> b) {
    for(int i = 0; i < n - 1; ++i) {
        g[a[i] - 1].push_back(b[i] - 1);
    }
}

int cat(int v){
    --v;
    st[v] = 1;
    return ans();
}


int dog(int v) {
    --v;
    st[v] = 2;
    return ans();
}


int neighbor(int v) {
    --v;
    st[v] = 0;
    return ans();
}

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