oj.uz

Submission #79674

# Submission time Handle Problem Language Result Execution time Memory
79674 2018-10-15T11:30:11 Z Mahdi_Jfri Cats or Dogs (JOI18_catdog) C++14
38 / 100
 38 ms 4892 KB 
#include "catdog.h"
#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define pb push_back

const int maxn = 1e3 + 20;

int n , dp[maxn][2] , state[maxn];

vector<int> adj[maxn];

void initialize(int N, std::vector<int> A, std::vector<int> B)
{
	n = N;

	for(int i = 0; i < n - 1; i++)
	{
		int a = A[i] , b = B[i];
		a-- , b--;

		adj[a].pb(b);
		adj[b].pb(a);
	}

	fill(state , state + n , 2);
}

void dfs(int v , int p = -1)
{
	if(state[v] != 2)
		dp[v][!state[v]] = n;

	for(auto u : adj[v])
		if(u != p)
		{
			dfs(u , v);

			for(int i = 0; i < 2; i++)
				dp[v][i] += min(dp[u][!i] + 1 , dp[u][i]);
		}
}

int solve()
{
	memset(dp , 0 , sizeof dp);
	dfs(0);

	return min(dp[0][0] , dp[0][1]);
}

int cat(int v)
{
	v--;
	state[v] = 0;
	
	return solve();
}

int dog(int v)
{
	v--;
	state[v] = 1;

	return solve();
}

int neighbor(int v)
{
	v--;
	state[v] = 2;

	return solve();
}

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 500 KB Output is correct
3 Correct 2 ms 500 KB Output is correct
4 Correct 2 ms 500 KB Output is correct
5 Correct 3 ms 504 KB Output is correct
6 Correct 2 ms 504 KB Output is correct
7 Correct 2 ms 504 KB Output is correct
8 Correct 2 ms 548 KB Output is correct
9 Correct 2 ms 576 KB Output is correct
10 Correct 2 ms 704 KB Output is correct
11 Correct 2 ms 704 KB Output is correct
12 Correct 2 ms 704 KB Output is correct
13 Correct 2 ms 704 KB Output is correct
14 Correct 2 ms 704 KB Output is correct
15 Correct 3 ms 704 KB Output is correct
16 Correct 2 ms 704 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 500 KB Output is correct
3 Correct 2 ms 500 KB Output is correct
4 Correct 2 ms 500 KB Output is correct
5 Correct 3 ms 504 KB Output is correct
6 Correct 2 ms 504 KB Output is correct
7 Correct 2 ms 504 KB Output is correct
8 Correct 2 ms 548 KB Output is correct
9 Correct 2 ms 576 KB Output is correct
10 Correct 2 ms 704 KB Output is correct
11 Correct 2 ms 704 KB Output is correct
12 Correct 2 ms 704 KB Output is correct
13 Correct 2 ms 704 KB Output is correct
14 Correct 2 ms 704 KB Output is correct
15 Correct 3 ms 704 KB Output is correct
16 Correct 2 ms 704 KB Output is correct
17 Correct 11 ms 704 KB Output is correct
18 Correct 12 ms 704 KB Output is correct
19 Correct 8 ms 764 KB Output is correct
20 Correct 2 ms 764 KB Output is correct
21 Correct 4 ms 812 KB Output is correct
22 Correct 4 ms 812 KB Output is correct
23 Correct 14 ms 812 KB Output is correct
24 Correct 11 ms 812 KB Output is correct
25 Correct 6 ms 812 KB Output is correct
26 Correct 5 ms 812 KB Output is correct
27 Correct 5 ms 812 KB Output is correct
28 Correct 5 ms 936 KB Output is correct
29 Correct 17 ms 976 KB Output is correct
30 Correct 4 ms 976 KB Output is correct
31 Correct 3 ms 976 KB Output is correct
32 Correct 4 ms 976 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 500 KB Output is correct
3 Correct 2 ms 500 KB Output is correct
4 Correct 2 ms 500 KB Output is correct
5 Correct 3 ms 504 KB Output is correct
6 Correct 2 ms 504 KB Output is correct
7 Correct 2 ms 504 KB Output is correct
8 Correct 2 ms 548 KB Output is correct
9 Correct 2 ms 576 KB Output is correct
10 Correct 2 ms 704 KB Output is correct
11 Correct 2 ms 704 KB Output is correct
12 Correct 2 ms 704 KB Output is correct
13 Correct 2 ms 704 KB Output is correct
14 Correct 2 ms 704 KB Output is correct
15 Correct 3 ms 704 KB Output is correct
16 Correct 2 ms 704 KB Output is correct
17 Correct 11 ms 704 KB Output is correct
18 Correct 12 ms 704 KB Output is correct
19 Correct 8 ms 764 KB Output is correct
20 Correct 2 ms 764 KB Output is correct
21 Correct 4 ms 812 KB Output is correct
22 Correct 4 ms 812 KB Output is correct
23 Correct 14 ms 812 KB Output is correct
24 Correct 11 ms 812 KB Output is correct
25 Correct 6 ms 812 KB Output is correct
26 Correct 5 ms 812 KB Output is correct
27 Correct 5 ms 812 KB Output is correct
28 Correct 5 ms 936 KB Output is correct
29 Correct 17 ms 976 KB Output is correct
30 Correct 4 ms 976 KB Output is correct
31 Correct 3 ms 976 KB Output is correct
32 Correct 4 ms 976 KB Output is correct
33 Runtime error 38 ms 4892 KB Execution killed with signal 11 (could be triggered by violating memory limits)
34 Halted 0 ms 0 KB -