oj.uz

Submission #711524

# Submission time Handle Problem Language Result Execution time Memory
711524 2023-03-17T07:39:56 Z Cyanmond Cats or Dogs (JOI18_catdog) C++17
0 / 100
 1 ms 340 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Incorrect 1 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Incorrect 1 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 62.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Incorrect 1 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -