oj.uz

Submission #133583

# Submission time Handle Problem Language Result Execution time Memory
133583 2019-07-21T05:39:09 Z ainta Cats or Dogs (JOI18_catdog) C++17
38 / 100
 35 ms 4472 KB 
#include "catdog.h"
#include<vector>
#include<algorithm>
using namespace std;

int w[1010], n, D[1010][3], par[1010];
vector<int>E[1010], Ch[1010];

void DFS(int a, int pp) {
	par[a] = pp;
	for (auto &x : E[a]) {
		if (x == pp)continue;
		DFS(x, a);
		Ch[a].push_back(x);
	}
}

void initialize(int N, std::vector<int> A, std::vector<int> B) {
	n = N;
	int i;
	for (i = 0; i < n - 1; i++) {
		E[A[i]].push_back(B[i]);
		E[B[i]].push_back(A[i]);
	}
	DFS(1, 0);
}


void UDT(int a) {
	if (w[a] == 0) {
		int s1 = 0, s2 = 0;
		for (auto &x : Ch[a]) {
			s1 += D[x][1];
			s2 += D[x][2];
		}
		D[a][1] = min(s1, s2 + 1);
		D[a][2] = min(s2, s1 + 1);
	}
	if (w[a] == 1) {
		int s = 0;
		for (auto &x : Ch[a]) {
			s += D[x][1];
		}
		D[a][1] = s;
		D[a][2] = s + 1;
	}
	if (w[a] == 2) {
		int s = 0;
		for (auto &x : Ch[a]) {
			s += D[x][2];
		}
		D[a][1] = s + 1;
		D[a][2] = s;
	}
}


int cat(int v) {
	w[v] = 1;
	while (v) {
		UDT(v);
		v = par[v];
	}
	return min(D[1][1], D[1][2]);
}

int dog(int v) {
	w[v] = 2;
	while (v) {
		UDT(v);
		v = par[v];
	}
	return min(D[1][1], D[1][2]);
}

int neighbor(int v) {
	w[v] = 0;
	while (v) {
		UDT(v);
		v = par[v];
	}
	return min(D[1][1], D[1][2]);
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 380 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 2 ms 376 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 380 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Correct 3 ms 376 KB Output is correct
18 Correct 3 ms 440 KB Output is correct
19 Correct 3 ms 504 KB Output is correct
20 Correct 2 ms 376 KB Output is correct
21 Correct 2 ms 376 KB Output is correct
22 Correct 2 ms 376 KB Output is correct
23 Correct 3 ms 376 KB Output is correct
24 Correct 3 ms 376 KB Output is correct
25 Correct 3 ms 376 KB Output is correct
26 Correct 2 ms 504 KB Output is correct
27 Correct 2 ms 504 KB Output is correct
28 Correct 3 ms 504 KB Output is correct
29 Correct 6 ms 504 KB Output is correct
30 Correct 2 ms 476 KB Output is correct
31 Correct 2 ms 376 KB Output is correct
32 Correct 2 ms 376 KB Output is correct

Subtask #3
0 / 62.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 380 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Correct 3 ms 376 KB Output is correct
18 Correct 3 ms 440 KB Output is correct
19 Correct 3 ms 504 KB Output is correct
20 Correct 2 ms 376 KB Output is correct
21 Correct 2 ms 376 KB Output is correct
22 Correct 2 ms 376 KB Output is correct
23 Correct 3 ms 376 KB Output is correct
24 Correct 3 ms 376 KB Output is correct
25 Correct 3 ms 376 KB Output is correct
26 Correct 2 ms 504 KB Output is correct
27 Correct 2 ms 504 KB Output is correct
28 Correct 3 ms 504 KB Output is correct
29 Correct 6 ms 504 KB Output is correct
30 Correct 2 ms 476 KB Output is correct
31 Correct 2 ms 376 KB Output is correct
32 Correct 2 ms 376 KB Output is correct
33 Runtime error 35 ms 4472 KB Execution killed with signal 11 (could be triggered by violating memory limits)
34 Halted 0 ms 0 KB -