제출 #1282973

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1282973		daotuankhoi	Cats or Dogs (JOI18_catdog)	C++20	38 / 100	3093 ms	5660 KiB

catdog

#include <bits/stdc++.h>

using namespace std;

#define ll long long


const int MAXN = 1e5 + 5;

vector<int> g[MAXN];

const int INF = 1e9;

int n;
ll dp[MAXN][2], val[MAXN];

void dfs(int u, int p) {
//    cerr << u << '\n';
    dp[u][0] = dp[u][1] = 0;
    if (val[u] != 0) dp[u][val[u] - 1] = INF;
    for (int v : g[u]) {
        if (v != p) {
            dfs(v, u);
            if (dp[u][0] < INF) {
                dp[u][0] += min(dp[v][1] + 1, dp[v][0]);
            }
            if (dp[u][1] < INF) {
                dp[u][1] += min(dp[v][0] + 1, dp[v][1]);
            }
        }
    }
}

void initialize(int N, vector<int> A, vector<int> B) {
    for (int i = 0; i < N - 1; i++) {
        g[A[i]].emplace_back(B[i]);
        g[B[i]].emplace_back(A[i]);
//        cerr << A[i] << ' ' << B[i] << '\n';
    }
}

int cat(int v) {
    val[v] = 2;
    dfs(1, 1);
    return (min(dp[1][0], dp[1][1]) < INF ? min(dp[1][0], dp[1][1]) : -1);
}

int dog(int v) {
    val[v] = 1;
    dfs(1, 1);
    return (min(dp[1][0], dp[1][1]) < INF ? min(dp[1][0], dp[1][1]) : -1);
}

int neighbor(int v) {
    val[v] = 0;
    dfs(1, 1);
    return (min(dp[1][0], dp[1][1]) < INF ? min(dp[1][0], dp[1][1]) : -1);
}

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