제출 #1141093

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1141093		Noproblem29	Cats or Dogs (JOI18_catdog)	C++20	0 / 100	1 ms	2624 KiB

catdog

#include "catdog.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e5 + 5;
int n;
vector<int> g[N];
int dp[N][3];
int c[N];
void initialize(int _n, vector<int> a, vector<int> b){
    n = _n;
    for (int i = 1; i < n; i++){
        g[a[i]].push_back(b[i]);
        g[b[i]].push_back(a[i]);
    }
}
void dfs(int x, int p){
    dp[x][1]=0;
    dp[x][2]=0;
    for(auto i:g[x]){
        if(i!=p){
            dfs(i,x);
            dp[x][1]+=min(dp[i][1],dp[i][2]+1);
            dp[x][2]+=min(dp[i][2],dp[i][1]+1);
        }
    }
    if(c[x]==1)dp[x][2]=1e9;
    if(c[x]==2)dp[x][1]=1e9;

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

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

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

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