Submission #70809

#	Time	Username	Problem	Language	Result	Execution time	Memory
70809		dnass	Cats or Dogs (JOI18_catdog)	C++17	0 / 100	5 ms	3192 KiB

catdog

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

int n;
int tot;
vector<int> adj[100010];
int type[100010];
bool visited[100010];

void dfs(int node, int t, int prev){
	if(type[node]!=0) visited[node] = true;
	for(unsigned int i=0;i<adj[node].size();i++){
		int viz = adj[node][i];
		if(viz!=prev&&type[viz]!=((t%2)+1)){
			dfs(viz, t, node);
		}
	}
}

int find_components(){
	tot = 0;
	memset(visited, false, sizeof visited);
	for(int i=1;i<=n;i++){
		if(!visited[i]&&type[i]!=0){
			dfs(i, type[i], -1);
			tot++;
		}
	}
	return tot-1;
}

void initialize(int N, vector<int> A, 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]);
	}
	memset(type, 0, sizeof type);
}

int cat(int v) {
	type[v] = 1;
	return find_components();
}

int dog(int v) {
	type[v] = 2;
	return find_components();
}

int neighbor(int v) {
	type[v] = 0;
	return find_components();
}

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