oj.uz

Submission #647907

# Submission time Handle Problem Language Result Execution time Memory
647907 2022-10-04T12:51:35 Z khshg Cats or Dogs (JOI18_catdog) C++14
38 / 100
 3000 ms 6044 KB 
#include<bits/stdc++.h>

using namespace std;

const int maxn = 100010, INF = 1e9;
int n;
vector<vector<int>> adj(maxn);
array<int, 2> dp[maxn];

void initialize(int _N, vector<int> A, vector<int> B) {
	n = _N;
	for(int i = 0; i < n - 1; ++i) {
		--A[i];
		--B[i];
		adj[A[i]].push_back(B[i]);
		adj[B[i]].push_back(A[i]);
	}
}

bool oc[maxn][2];

void dfs(int s, int p) {
	dp[s][0] = dp[s][1] = 0;
	for(int& u : adj[s]) {
		if(u != p) {
			dfs(u, s);
			dp[s][0] += min(dp[u][0], dp[u][1] + 1);
			dp[s][1] += min(dp[u][1], dp[u][0] + 1);
		}
	}
	if(oc[s][0])
		dp[s][0] = INF;
	if(oc[s][1])
		dp[s][1] = INF;
}

int cat(int v) {
	--v;
	oc[v][1] = true;
	dfs(0, -1);
	return min(dp[0][0], dp[0][1]);
}

int dog(int v) {
	--v;
	oc[v][0] = true;
	dfs(0, -1);
	return min(dp[0][0], dp[0][1]);
}

int neighbor(int v) {
	--v;
	oc[v][0] = oc[v][1] = false;
	dfs(0, -1);
	return min(dp[0][0], dp[0][1]);
}
/*
int readInt(){
	int i;
	if(scanf("%d",&i)!=1){
		fprintf(stderr,"Error while reading input\n");
		exit(1);
	}
	return i;
}
 
int main(){
	int N=readInt();
	
	std::vector<int> A(N-1),B(N-1);
	for(int i=0;i<N-1;i++)
	{
		A[i]=readInt();
		B[i]=readInt();
	}
	int Q;
	assert(scanf("%d",&Q)==1);
	std::vector <int> T(Q),V(Q);
	for(int i=0;i<Q;i++)
	{
		T[i]=readInt();
		V[i]=readInt();
	}
	
	initialize(N,A,B);
	
	std::vector<int> res(Q);
	for(int j=0;j<Q;j++)
	{
		if(T[j]==1) res[j]=cat(V[j]);
		else if(T[j]==2) res[j]=dog(V[j]);
		else res[j]=neighbor(V[j]);
	}
	for(int j=0;j<Q;j++)
		printf("%d\n",res[j]);
	return 0;
}*/

Subtask #1
8.0 / 8.0

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

Subtask #2
30.0 / 30.0

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

Subtask #3
0 / 62.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 1 ms 2644 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 2 ms 2644 KB Output is correct
8 Correct 1 ms 2644 KB Output is correct
9 Correct 2 ms 2644 KB Output is correct
10 Correct 3 ms 2644 KB Output is correct
11 Correct 2 ms 2644 KB Output is correct
12 Correct 1 ms 2644 KB Output is correct
13 Correct 2 ms 2644 KB Output is correct
14 Correct 2 ms 2644 KB Output is correct
15 Correct 2 ms 2644 KB Output is correct
16 Correct 2 ms 2644 KB Output is correct
17 Correct 10 ms 2644 KB Output is correct
18 Correct 12 ms 2644 KB Output is correct
19 Correct 6 ms 2644 KB Output is correct
20 Correct 2 ms 2644 KB Output is correct
21 Correct 2 ms 2644 KB Output is correct
22 Correct 3 ms 2644 KB Output is correct
23 Correct 14 ms 2644 KB Output is correct
24 Correct 10 ms 2712 KB Output is correct
25 Correct 6 ms 2644 KB Output is correct
26 Correct 3 ms 2644 KB Output is correct
27 Correct 3 ms 2644 KB Output is correct
28 Correct 4 ms 2644 KB Output is correct
29 Correct 17 ms 2772 KB Output is correct
30 Correct 3 ms 2644 KB Output is correct
31 Correct 2 ms 2644 KB Output is correct
32 Correct 4 ms 2692 KB Output is correct
33 Execution timed out 3058 ms 6044 KB Time limit exceeded
34 Halted 0 ms 0 KB -