답안 #781378

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
781378	2023-07-13T04:58:10 Z	kshitij_sodani	Cats or Dogs (JOI18_catdog)	C++14	38 / 100	3000 ms	7132 KB

catdog

#include <bits/stdc++.h>
using namespace std;
#define a first
#define b second
#define pb push_back
typedef long long llo;
#define endl '\n'


#include "catdog.h"

int x;
vector<int> adj[100001];
int dp[100001][2];
int it[100001];
int n;
void initialize(int nn, std::vector<int> aa, std::vector<int> bb) {
	n=nn;
	for(int i=0;i<n-1;i++){
		adj[aa[i]-1].pb(bb[i]-1);
		adj[bb[i]-1].pb(aa[i]-1);
	}
	for(int i=0;i<n;i++){
		it[i]=0;
	}
}
void dfs(int no,int par=-1){
	dp[no][0]=0;
	dp[no][1]=0;
	if(it[no]==1){
		dp[no][1]=1e9;
	}
	else if(it[no]==2){
		dp[no][0]=1e9;
	}
	for(auto j:adj[no]){
		if(j!=par){
			dfs(j,no);
			dp[no][0]+=min(dp[j][0],dp[j][1]+1);
			dp[no][1]+=min(dp[j][1],dp[j][0]+1);
		}
	}
}

int cat(int i) {
	it[i-1]=1;
 
 	dfs(0);
 	
	return min(dp[0][0],dp[0][1]);
}

int dog(int i) {
	it[i-1]=2;
 	
 	dfs(0);
 

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

int neighbor(int i) {
	it[i-1]=0;

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

Subtask #1

8.0 / 8.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	2652 KB	Output is correct
2	Correct	1 ms	2660 KB	Output is correct
3	Correct	1 ms	2644 KB	Output is correct
4	Correct	1 ms	2652 KB	Output is correct
5	Correct	1 ms	2644 KB	Output is correct
6	Correct	2 ms	2644 KB	Output is correct
7	Correct	1 ms	2644 KB	Output is correct
8	Correct	1 ms	2644 KB	Output is correct
9	Correct	1 ms	2644 KB	Output is correct
10	Correct	1 ms	2644 KB	Output is correct
11	Correct	1 ms	2644 KB	Output is correct
12	Correct	2 ms	2644 KB	Output is correct
13	Correct	2 ms	2644 KB	Output is correct
14	Correct	2 ms	2772 KB	Output is correct
15	Correct	1 ms	2644 KB	Output is correct
16	Correct	1 ms	2644 KB	Output is correct

Subtask #2

30.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	2652 KB	Output is correct
2	Correct	1 ms	2660 KB	Output is correct
3	Correct	1 ms	2644 KB	Output is correct
4	Correct	1 ms	2652 KB	Output is correct
5	Correct	1 ms	2644 KB	Output is correct
6	Correct	2 ms	2644 KB	Output is correct
7	Correct	1 ms	2644 KB	Output is correct
8	Correct	1 ms	2644 KB	Output is correct
9	Correct	1 ms	2644 KB	Output is correct
10	Correct	1 ms	2644 KB	Output is correct
11	Correct	1 ms	2644 KB	Output is correct
12	Correct	2 ms	2644 KB	Output is correct
13	Correct	2 ms	2644 KB	Output is correct
14	Correct	2 ms	2772 KB	Output is correct
15	Correct	1 ms	2644 KB	Output is correct
16	Correct	1 ms	2644 KB	Output is correct
17	Correct	6 ms	2644 KB	Output is correct
18	Correct	7 ms	2644 KB	Output is correct
19	Correct	4 ms	2644 KB	Output is correct
20	Correct	2 ms	2652 KB	Output is correct
21	Correct	2 ms	2652 KB	Output is correct
22	Correct	3 ms	2656 KB	Output is correct
23	Correct	8 ms	2644 KB	Output is correct
24	Correct	7 ms	2608 KB	Output is correct
25	Correct	4 ms	2660 KB	Output is correct
26	Correct	2 ms	2644 KB	Output is correct
27	Correct	3 ms	2644 KB	Output is correct
28	Correct	4 ms	2664 KB	Output is correct
29	Correct	11 ms	2780 KB	Output is correct
30	Correct	2 ms	2644 KB	Output is correct
31	Correct	2 ms	2644 KB	Output is correct
32	Correct	3 ms	2644 KB	Output is correct

Subtask #3

0 / 62.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	2652 KB	Output is correct
2	Correct	1 ms	2660 KB	Output is correct
3	Correct	1 ms	2644 KB	Output is correct
4	Correct	1 ms	2652 KB	Output is correct
5	Correct	1 ms	2644 KB	Output is correct
6	Correct	2 ms	2644 KB	Output is correct
7	Correct	1 ms	2644 KB	Output is correct
8	Correct	1 ms	2644 KB	Output is correct
9	Correct	1 ms	2644 KB	Output is correct
10	Correct	1 ms	2644 KB	Output is correct
11	Correct	1 ms	2644 KB	Output is correct
12	Correct	2 ms	2644 KB	Output is correct
13	Correct	2 ms	2644 KB	Output is correct
14	Correct	2 ms	2772 KB	Output is correct
15	Correct	1 ms	2644 KB	Output is correct
16	Correct	1 ms	2644 KB	Output is correct
17	Correct	6 ms	2644 KB	Output is correct
18	Correct	7 ms	2644 KB	Output is correct
19	Correct	4 ms	2644 KB	Output is correct
20	Correct	2 ms	2652 KB	Output is correct
21	Correct	2 ms	2652 KB	Output is correct
22	Correct	3 ms	2656 KB	Output is correct
23	Correct	8 ms	2644 KB	Output is correct
24	Correct	7 ms	2608 KB	Output is correct
25	Correct	4 ms	2660 KB	Output is correct
26	Correct	2 ms	2644 KB	Output is correct
27	Correct	3 ms	2644 KB	Output is correct
28	Correct	4 ms	2664 KB	Output is correct
29	Correct	11 ms	2780 KB	Output is correct
30	Correct	2 ms	2644 KB	Output is correct
31	Correct	2 ms	2644 KB	Output is correct
32	Correct	3 ms	2644 KB	Output is correct
33	Execution timed out	3054 ms	7132 KB	Time limit exceeded
34	Halted	0 ms	0 KB	-