Submission #160262

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

catdog

#include "catdog.h"

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

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 nxtbest = dfs(nxt, cur);
		for (int i = 0; i < 2; i++) best[i] += nxtbest[i];
	}
	if (A[cur] == 2) {
		for (int i = 0; i < 2; i++) best[i] = min(best[i], 1 + best[1-i]);
	} else {
		best[1-A[cur]] = 1 + best[A[cur]];
	}
	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