답안 #503363

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
503363	2022-01-07T17:45:44 Z	amunduzbaev	Cats or Dogs (JOI18_catdog)	C++14	38 / 100	26 ms	4272 KB

catdog

#include "catdog.h"
#include "bits/stdc++.h"
using namespace std;
#ifndef EVAL
#include "grader.cpp"
#endif

const int N = 1e3 + 5;
vector<int> edges[N];
int a[N], dp[N][2];

int dfs(int u, int p = -1){
	dp[u][0] = dp[u][1] = 0;
	for(auto x : edges[u]){
		if(x == p) continue;
		dfs(x, u);
		dp[u][0] += min(dp[x][0], dp[x][1] + 1);
		dp[u][1] += min(dp[x][0] + 1, dp[x][1]);
	}
	
	if(a[u] == 1) dp[u][1] = 1e9;
	if(a[u] == 2) dp[u][0] = 1e9;
	return min(dp[u][0], dp[u][1]);
}

void initialize(int n, vector<int> a, vector<int> b) {
	for(int i=0;i<(int)a.size();i++){
		edges[a[i]].push_back(b[i]);
		edges[b[i]].push_back(a[i]);
	}
}

int cat(int v) {
	a[v] = 1;
	return dfs(1);
}

int dog(int v) {
	a[v] = 2;
	return dfs(1);
}

int neighbor(int v) {
	a[v] = 0;
	return dfs(1);
}

Subtask #1

8.0 / 8.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	204 KB	Output is correct
2	Correct	1 ms	296 KB	Output is correct
3	Correct	0 ms	204 KB	Output is correct
4	Correct	0 ms	204 KB	Output is correct
5	Correct	0 ms	204 KB	Output is correct
6	Correct	1 ms	204 KB	Output is correct
7	Correct	1 ms	204 KB	Output is correct
8	Correct	1 ms	216 KB	Output is correct
9	Correct	0 ms	204 KB	Output is correct
10	Correct	0 ms	204 KB	Output is correct
11	Correct	0 ms	204 KB	Output is correct
12	Correct	0 ms	316 KB	Output is correct
13	Correct	0 ms	204 KB	Output is correct
14	Correct	0 ms	204 KB	Output is correct
15	Correct	0 ms	204 KB	Output is correct
16	Correct	0 ms	332 KB	Output is correct

Subtask #2

30.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	204 KB	Output is correct
2	Correct	1 ms	296 KB	Output is correct
3	Correct	0 ms	204 KB	Output is correct
4	Correct	0 ms	204 KB	Output is correct
5	Correct	0 ms	204 KB	Output is correct
6	Correct	1 ms	204 KB	Output is correct
7	Correct	1 ms	204 KB	Output is correct
8	Correct	1 ms	216 KB	Output is correct
9	Correct	0 ms	204 KB	Output is correct
10	Correct	0 ms	204 KB	Output is correct
11	Correct	0 ms	204 KB	Output is correct
12	Correct	0 ms	316 KB	Output is correct
13	Correct	0 ms	204 KB	Output is correct
14	Correct	0 ms	204 KB	Output is correct
15	Correct	0 ms	204 KB	Output is correct
16	Correct	0 ms	332 KB	Output is correct
17	Correct	8 ms	380 KB	Output is correct
18	Correct	10 ms	332 KB	Output is correct
19	Correct	7 ms	332 KB	Output is correct
20	Correct	1 ms	332 KB	Output is correct
21	Correct	2 ms	332 KB	Output is correct
22	Correct	2 ms	324 KB	Output is correct
23	Correct	13 ms	388 KB	Output is correct
24	Correct	9 ms	332 KB	Output is correct
25	Correct	4 ms	332 KB	Output is correct
26	Correct	2 ms	332 KB	Output is correct
27	Correct	1 ms	312 KB	Output is correct
28	Correct	3 ms	332 KB	Output is correct
29	Correct	14 ms	332 KB	Output is correct
30	Correct	3 ms	332 KB	Output is correct
31	Correct	2 ms	324 KB	Output is correct
32	Correct	3 ms	324 KB	Output is correct

Subtask #3

0 / 62.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	204 KB	Output is correct
2	Correct	1 ms	296 KB	Output is correct
3	Correct	0 ms	204 KB	Output is correct
4	Correct	0 ms	204 KB	Output is correct
5	Correct	0 ms	204 KB	Output is correct
6	Correct	1 ms	204 KB	Output is correct
7	Correct	1 ms	204 KB	Output is correct
8	Correct	1 ms	216 KB	Output is correct
9	Correct	0 ms	204 KB	Output is correct
10	Correct	0 ms	204 KB	Output is correct
11	Correct	0 ms	204 KB	Output is correct
12	Correct	0 ms	316 KB	Output is correct
13	Correct	0 ms	204 KB	Output is correct
14	Correct	0 ms	204 KB	Output is correct
15	Correct	0 ms	204 KB	Output is correct
16	Correct	0 ms	332 KB	Output is correct
17	Correct	8 ms	380 KB	Output is correct
18	Correct	10 ms	332 KB	Output is correct
19	Correct	7 ms	332 KB	Output is correct
20	Correct	1 ms	332 KB	Output is correct
21	Correct	2 ms	332 KB	Output is correct
22	Correct	2 ms	324 KB	Output is correct
23	Correct	13 ms	388 KB	Output is correct
24	Correct	9 ms	332 KB	Output is correct
25	Correct	4 ms	332 KB	Output is correct
26	Correct	2 ms	332 KB	Output is correct
27	Correct	1 ms	312 KB	Output is correct
28	Correct	3 ms	332 KB	Output is correct
29	Correct	14 ms	332 KB	Output is correct
30	Correct	3 ms	332 KB	Output is correct
31	Correct	2 ms	324 KB	Output is correct
32	Correct	3 ms	324 KB	Output is correct
33	Runtime error	26 ms	4272 KB	Execution killed with signal 11
34	Halted	0 ms	0 KB	-