oj.uz

Submission #363248

# Submission time Handle Problem Language Result Execution time Memory
363248 2021-02-05T11:36:52 Z teewar Cats or Dogs (JOI18_catdog) C++14
0 / 100
 1 ms 364 KB 
#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][2] += 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.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 364 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 364 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 62.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 364 KB Output isn't correct
2 Halted 0 ms 0 KB -