oj.uz

Submission #79667

# Submission time Handle Problem Language Result Execution time Memory
79667 2018-10-15T11:21:39 Z Mahdi_Jfri Cats or Dogs (JOI18_catdog) C++14
8 / 100
 10 ms 1184 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; 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 3 ms 504 KB Output is correct
2 Correct 2 ms 696 KB Output is correct
3 Correct 2 ms 744 KB Output is correct
4 Correct 2 ms 744 KB Output is correct
5 Correct 2 ms 936 KB Output is correct
6 Correct 2 ms 936 KB Output is correct
7 Correct 2 ms 936 KB Output is correct
8 Correct 3 ms 936 KB Output is correct
9 Correct 3 ms 936 KB Output is correct
10 Correct 2 ms 936 KB Output is correct
11 Correct 2 ms 936 KB Output is correct
12 Correct 2 ms 940 KB Output is correct
13 Correct 2 ms 940 KB Output is correct
14 Correct 2 ms 1016 KB Output is correct
15 Correct 2 ms 1016 KB Output is correct
16 Correct 2 ms 1016 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 504 KB Output is correct
2 Correct 2 ms 696 KB Output is correct
3 Correct 2 ms 744 KB Output is correct
4 Correct 2 ms 744 KB Output is correct
5 Correct 2 ms 936 KB Output is correct
6 Correct 2 ms 936 KB Output is correct
7 Correct 2 ms 936 KB Output is correct
8 Correct 3 ms 936 KB Output is correct
9 Correct 3 ms 936 KB Output is correct
10 Correct 2 ms 936 KB Output is correct
11 Correct 2 ms 936 KB Output is correct
12 Correct 2 ms 940 KB Output is correct
13 Correct 2 ms 940 KB Output is correct
14 Correct 2 ms 1016 KB Output is correct
15 Correct 2 ms 1016 KB Output is correct
16 Correct 2 ms 1016 KB Output is correct
17 Correct 10 ms 1016 KB Output is correct
18 Runtime error 3 ms 1184 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Halted 0 ms 0 KB -

Subtask #3
0 / 62.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 504 KB Output is correct
2 Correct 2 ms 696 KB Output is correct
3 Correct 2 ms 744 KB Output is correct
4 Correct 2 ms 744 KB Output is correct
5 Correct 2 ms 936 KB Output is correct
6 Correct 2 ms 936 KB Output is correct
7 Correct 2 ms 936 KB Output is correct
8 Correct 3 ms 936 KB Output is correct
9 Correct 3 ms 936 KB Output is correct
10 Correct 2 ms 936 KB Output is correct
11 Correct 2 ms 936 KB Output is correct
12 Correct 2 ms 940 KB Output is correct
13 Correct 2 ms 940 KB Output is correct
14 Correct 2 ms 1016 KB Output is correct
15 Correct 2 ms 1016 KB Output is correct
16 Correct 2 ms 1016 KB Output is correct
17 Correct 10 ms 1016 KB Output is correct
18 Runtime error 3 ms 1184 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Halted 0 ms 0 KB -