Submission #711524

#	Time	Username	Problem	Language	Result	Execution time	Memory
711524		Cyanmond	Cats or Dogs (JOI18_catdog)	C++17	0 / 100	1 ms	340 KiB

catdog

#include "catdog.h"
#include <bits/stdc++.h>

constexpr int inf = 1 << 30;

int N;
std::vector<int> A, B;
std::vector<std::vector<int>> Tree;
std::vector<int> status;
void initialize(int n, std::vector<int> a, std::vector<int> b) {
    N = n;
    A = a;
    B = b;
    Tree.resize(N);
    for (int i = 0; i < N - 1; ++i) {
        --A[i]; --B[i];
        Tree[A[i]].push_back(B[i]);
        Tree[B[i]].push_back(A[i]);
    }
    status.resize(N);
}

int calc() {
    std::vector<std::array<int, 3>> dp(N);
    for (auto &ar : dp) std::fill(ar.begin(), ar.end(), inf);
    auto dfs = [&](auto &&self, const int v, const int p) -> void {
        dp[v][0] = dp[v][1] = dp[v][2] = 0;
        for (const int t : Tree[v]) {
            if (t == p) continue;
            self(self, t, v);
            dp[v][0] = std::min({dp[v][0] + dp[t][0], dp[v][0] + dp[t][1] + 1, dp[v][0] + dp[t][2] + 1});
            dp[v][1] = std::min({dp[v][1] + dp[t][0], dp[v][1] + dp[t][1], dp[v][1] + dp[t][2] + 1});
            dp[v][2] = std::min({dp[v][2] + dp[t][0], dp[v][2] + dp[t][1] + 1, dp[v][2] + dp[t][2]});
        }
        if (status[v] == 1) {
            ++dp[v][0];
            ++dp[v][2];
        }
        if (status[v] == 2) {
            ++dp[v][0];
            ++dp[v][1];
        }
    };
    dfs(dfs, 0, -1);
    return *std::min_element(dp[0].begin(), dp[0].end());
}

int cat(int v) {
    --v;
    status[v] = 1;
    return calc();
}

int dog(int v) {
    --v;
    status[v] = 2;
    return calc();
}

int neighbor(int v) {
    --v;
    status[v] = 0;
    return calc();
}

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