Submission #126576

#	Time	Username	Problem	Language	Result	Execution time	Memory
126576		E869120	Cats or Dogs (JOI18_catdog)	C++14	38 / 100	67 ms	3448 KiB

catdog

#include "catdog.h"
#include <vector>
#include <algorithm>
using namespace std;

int N, E[5009], dp[5009][2]; bool used[5009];
vector<int> X[5009];

void initialize(int NN, vector<int> A, vector<int> B) {
	N = NN; for (int i = 1; i <= N; i++) E[i] = 2;
	for (int i = 0; i < A.size(); i++) {
		X[A[i]].push_back(B[i]);
		X[B[i]].push_back(A[i]);
	}
}

void dfs(int pos) {
	used[pos] = true;
	vector<int>G;
	for (int i = 0; i < X[pos].size(); i++) {
		if (used[X[pos][i]] == true) continue;
		G.push_back(X[pos][i]);
		dfs(X[pos][i]);
	}

	// 1. 猫を飼う場合
	for (int pos2 : G) {
		dp[pos][0] += min(dp[pos2][0], dp[pos2][1] + 1);
	}

	// 2. 犬を飼う場合
	for (int pos2 : G) {
		dp[pos][1] += min(dp[pos2][1], dp[pos2][0] + 1);
	}
	
	if (E[pos] == 0) dp[pos][1] = (1 << 30);
	if (E[pos] == 1) dp[pos][0] = (1 << 30);
}

int solve() {
	for (int i = 1; i <= N; i++) { dp[i][0] = 0; dp[i][1] = 0; used[i] = false; }
	dfs(1);
	return min(dp[1][0], dp[1][1]);
}

int cat(int v) {
	E[v] = 0;
	return solve();
}

int dog(int v) {
	E[v] = 1;
	return solve();
}

int neighbor(int v) {
	E[v] = 2;
	return solve();
}

Compilation message (stderr)

catdog.cpp: In function 'void initialize(int, std::vector<int>, std::vector<int>)':
catdog.cpp:11:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < A.size(); i++) {
                  ~~^~~~~~~~~~
catdog.cpp: In function 'void dfs(int)':
catdog.cpp:20:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < X[pos].size(); i++) {
                  ~~^~~~~~~~~~~~~~~

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