Submission #539311

#	Time	Username	Problem	Language	Result	Execution time	Memory
539311		LucaDantas	Cats or Dogs (JOI18_catdog)	C++17	0 / 100	1 ms	332 KiB

catdog

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

constexpr int maxn = 1e3+10;

vector<int> g[maxn];
int cor[maxn], ans;

void dfs(int u, int c, int p = 0) {
	// fprintf(stderr, "u %d %d %d\n", u, c, p);
	for(int v : g[u]) if(v != p) {
		if(cor[v] && cor[v] != c) ++ans;
		dfs(v, cor[v] ? cor[v] : c, u);
	}
}

int n;

void initialize(int N, std::vector<int> A, std::vector<int> B) {
	n = N;
	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) {
	cor[v] = 1;
	ans = 0;
	dfs(v, 1);
	return ans;
}

int dog(int v) {
	cor[v] = -1;
	ans = 0;
	dfs(v, -1);
	return ans;
}

int neighbor(int v) {
	cor[v] = 0;
	ans = 0;
	for(int i = 1; i <= n; i++)
		if(cor[i]) { dfs(i, cor[i]); break; }
	return ans;
}

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