Submission #389640

#	Time	Username	Problem	Language	Result	Execution time	Memory
389640		maximath_1	Cats or Dogs (JOI18_catdog)	C++11	38 / 100	36 ms	4264 KiB

catdog

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

const int MX = 1005;

int ada[MX], dp[MX][2];
vector<int> adj[MX];

void dfs(int nw, int bf){
	dp[nw][0] = dp[nw][1] = 0;
	for(int nx : adj[nw]) if(nx != bf){
		dfs(nx, nw);
		dp[nw][0] += min(dp[nx][0], dp[nx][1] + 1);
		dp[nw][1] += min(dp[nx][1], dp[nx][0] + 1);
	}

	if(ada[nw] != -1)
		dp[nw][1 - ada[nw]] = MX * MX;
}

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

	for(int i = 1; i <= N; i ++)
		ada[i] = -1;
}

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

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

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

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