Submission #197052

#	Time	Username	Problem	Language	Result	Execution time	Memory
197052		iefnah06	Cats or Dogs (JOI18_catdog)	C++11	38 / 100	3005 ms	7192 KiB

catdog

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

const int INF = 1e9;
 
const int MAXN = 1.1e5;
int N;
vector<int> adj[MAXN];
 
int A[MAXN];
 
void initialize(int n, std::vector<int> a, std::vector<int> b) {
	N = n;
	for (int i = 0; i < N-1; i++) {
		adj[a[i]].push_back(b[i]);
		adj[b[i]].push_back(a[i]);
	}
	for (int i = 1; i <= N; i++) {
		A[i] = 2;
	}
}
 
int query();
 
int cat(int v) {
	A[v] = 0;
	return query();
}
 
int dog(int v) {
	A[v] = 1;
	return query();
}
 
int neighbor(int v) {
	A[v] = 2;
	return query();
}

array<int, 2> dfs(int cur, int prv) {
	array<int, 2> best = {0,0};
	for (int nxt : adj[cur]) {
		if (nxt == prv) continue;
		auto nbest = dfs(nxt, cur);
		best[0] += min(nbest[0], nbest[1]+1);
		best[1] += min(nbest[1], nbest[0]+1);
	}
	if (A[cur] == 0) {
		best[0] = INF;
	} else if (A[cur] == 1) {
		best[1] = INF;
	}
	return best;
}
 
int query() {
	auto res = dfs(1, 0);
	return min(res[0], res[1]);
}

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