Submission #1287478

#	Time	Username	Problem	Language	Result	Execution time	Memory
1287478		am_aadvik	Cats or Dogs (JOI18_catdog)	C++20	38 / 100	3094 ms	7024 KiB

catdog

#define _CRT_SECURE_NO_WARNINGS
#include <vector>
#include<iostream>
#include<cstring>
const int inf = 1e9;
using namespace std;
#define SUBMIT 1
void initialize(int N, std::vector<int> A, std::vector<int> B);
int cat(int v);
int dog(int v);
int neighbor(int v);

#ifndef SUBMIT
#include <cstdio>
#include <cassert>
#include <vector>
#include <stdlib.h>

int readInt() {
	int i;
	if (scanf("%d", &i) != 1) {
		fprintf(stderr, "Error while reading input\n");
		exit(1);
	}
	return i;
}

int main() {
	int N = readInt();

	std::vector<int> A(N - 1), B(N - 1);
	for (int i = 0; i < N - 1; i++)
	{
		A[i] = readInt();
		B[i] = readInt();
	}
	int Q;
	assert(scanf("%d", &Q) == 1);
	std::vector <int> T(Q), V(Q);
	for (int i = 0; i < Q; i++)
	{
		T[i] = readInt();
		V[i] = readInt();
	}

	initialize(N, A, B);

	std::vector<int> res(Q);
	for (int j = 0; j < Q; j++)
	{
		if (T[j] == 1) res[j] = cat(V[j]);
		else if (T[j] == 2) res[j] = dog(V[j]);
		else res[j] = neighbor(V[j]);
	}
	for (int j = 0; j < Q; j++)
		printf("%d\n", res[j]);
	return 0;
}

#endif

vector<int> g[200005];
int dp[200005][3], cur[200005];
int n;
int dfs(int node, int par, int b) {
	if (dp[node][b] != -1) return dp[node][b];
	int op1 = inf, op2 = 0, op3 = 0;
	if (b != 0) op1 = dfs(node, par, 0) + 1;
	if ((cur[node] == b) || (cur[node] == 0) || (b == 0)) {
		for (auto& x : g[node])
			if (x != par)
				op2 += dfs(x, node, 1),
				op3 += dfs(x, node, 2);
	}
	else op2 = op3 = inf;
	if ((b == 1) || (cur[node] == 1)) op3 = inf;
	if ((b == 2) || (cur[node] == 2)) op2 = inf;
	return dp[node][b] = min(op1, min(op2, op3));
}
void initialize(int N, vector<int> a, vector<int> b) {
	n = N, memset(dp, -1, sizeof(dp));
	for (int i = 0; i < (n - 1); ++i)
		g[a[i]].push_back(b[i]),
		g[b[i]].push_back(a[i]);
}
int cat(int v) {
	memset(dp, -1, sizeof(dp));
	cur[v] = 1;
	return dfs(1, 0, 0);
}
int dog(int v) {
	memset(dp, -1, sizeof(dp));
	cur[v] = 2;
	return dfs(1, 0, 0);
}
int neighbor(int v) {
	memset(dp, -1, sizeof(dp));
	cur[v] = 0;
	return dfs(1, 0, 0);
}

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