oj.uz

Submission #70809

# Submission time Handle Problem Language Result Execution time Memory
70809 2018-08-23T13:20:17 Z dnass Cats or Dogs (JOI18_catdog) C++17
0 / 100
 5 ms 3192 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 3192 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 3192 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 62.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 3192 KB Output isn't correct
2 Halted 0 ms 0 KB -