제출 #1272495

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

catdog

#include <bits/stdc++.h>
using namespace std;

const int INF = 1e9;

int N, Q;
vector<int> adj[100005];
int parent[100005];
int type_pet[100005]; // 0 = none, 1 = cat, 2 = dog
int dp[100005][2];

void predfs(int node, int par) {
    parent[node] = par;
    for (int x : adj[node]) if (x != par) {
        predfs(x, node);
    }
}

void dfs(int node, int par) {
    dp[node][0] = dp[node][1] = 0;
    for (int x : adj[node]) if (x != par) {
        dfs(x, node);
        dp[node][0] += min(dp[x][0], dp[x][1] + 1);
        dp[node][1] += min(dp[x][1], dp[x][0] + 1);
    }
    if (type_pet[node] == 1) dp[node][1] = INF;
    if (type_pet[node] == 2) dp[node][0] = INF;
}

void recalc_up(int node) {
    while (node) {
        dp[node][0] = dp[node][1] = 0;
        for (int x : adj[node]) if (x != parent[node]) {
            dp[node][0] += min(dp[x][0], dp[x][1] + 1);
            dp[node][1] += min(dp[x][1], dp[x][0] + 1);
        }
        if (type_pet[node] == 1) dp[node][1] = INF;
        if (type_pet[node] == 2) dp[node][0] = INF;
        node = parent[node];
    }
}

void initialize(int n, vector<int> A, vector<int> B) {
    N = n;
    for (int i = 0; i < N - 1; i++) {
        int u = A[i], v = B[i];
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    predfs(1, 0);
    dfs(1, 0);
}

int cat(int v) {
    type_pet[v] = 1;
    recalc_up(v);
    return min(dp[1][0], dp[1][1]);
}

int dog(int v) {
    type_pet[v] = 2;
    recalc_up(v);
    return min(dp[1][0], dp[1][1]);
}

int neighbor(int v) {
    type_pet[v] = 0;
    recalc_up(v);
    return min(dp[1][0], dp[1][1]);
}

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