oj.uz

Submission #539311

# Submission time Handle Problem Language Result Execution time Memory
539311 2022-03-18T16:47:33 Z LucaDantas Cats or Dogs (JOI18_catdog) C++17
0 / 100
 1 ms 332 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 1 ms 332 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 1 ms 332 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 62.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 1 ms 332 KB Output isn't correct
3 Halted 0 ms 0 KB -