제출 #1212134

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

catdog

#include<bits/stdc++.h>
#include "catdog.h"
using namespace std;
#define in array<int, 2>
#define pb push_back
#define pob pop_back
#define fast() ios_base::sync_with_stdio(false); cin.tie(NULL)

const int MX = 1e3+2;
const int INF = 1e8;

vector<int> adj[MX];

vector<int> col;

int dp[3][MX];

void dfs(int u, int p)
{
	dp[1][u] = (col[u] == 2)? INF : 0;
	dp[2][u] = (col[u] == 1)? INF : 0;	
	int N = 0;
	for(int v: adj[u])
	{
		if(v == p)
			continue;
		dfs(v, u);
		dp[1][u] += min(dp[2][v]+1, dp[1][v]);
		dp[2][u] += min(dp[1][v]+1, dp[2][v]);
	}
	return;
}

void initialize(int n, vector<int> a, vector<int> b)
{
	for(int i = 0; i < n-1; i++)
	{
		adj[a[i]].pb(b[i]);
		adj[b[i]].pb(a[i]);
	}
	col.assign(n+1, 0);
	return;
}

int solve()
{
	dfs(1, 0);
	return min(dp[1][1], dp[2][1]);
}

int cat(int v)
{
	col[v] = 1;
	return solve();
}

int dog(int v)
{
	col[v] = 2;
	return solve();
}

int neighbor(int v)
{
	col[v] = 0;
	return solve();
}

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