제출 #1156900

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

catdog

#include "catdog.h"
#include<bits/stdc++.h>
using namespace std;
#define pb push_back


int n;
vector<int> q[200100];
int dp[200100][3];
int a[200100];

void dfs(int v, int p){
    dp[v][1] = dp[v][2] = 0;
    if(a[v] == 2) dp[v][1] = 1e9;
    if(a[v] == 1) dp[v][2] = 1e9; 
    for(int to: q[v]){
        if(to == p) continue;
        dfs(to, v);
        dp[v][1] += min(dp[to][1], dp[to][2] + 1);
        dp[v][2] += min(dp[to][1] + 1, dp[to][2]);
    }
}

void initialize(int N, vector<int> A, vector<int> B) {
    n = N;
    for(int i=0; i<A.size(); i++){
        int l = A[i];
        int r = B[i];
        q[l].pb(r);
        q[r].pb(l);
    }
}

int cat(int v) {
    a[v] = 1;
    dfs(1, 0);
    return min(dp[1][1], dp[1][2]);
}

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

int neighbor(int v) {
    a[v] = 0;
    dfs(1, 0);
    return min(dp[1][1], dp[1][2]);
}

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