# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
421681 |
2021-06-09T10:52:19 Z |
반딧불(#7622) |
Cats or Dogs (JOI18_catdog) |
C++17 |
|
3000 ms |
6920 KB |
#include "catdog.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int x;
int arr[100002];
vector<int> link[100002];
int DP[100002][3];
void calc(int x, int par = -1){
DP[x][0] = DP[x][1] = DP[x][2] = 0;
if(arr[x] == 1) DP[x][0] = DP[x][2] = 1e9;
if(arr[x] == 2) DP[x][0] = DP[x][1] = 1e9;
for(auto y: link[x]){
if(y==par) continue;
calc(y, x);
DP[x][0] += min({DP[y][0], DP[y][1]+1, DP[y][2]+1});
DP[x][1] += min({DP[y][0], DP[y][1] , DP[y][2]+1});
DP[x][2] += min({DP[y][0], DP[y][1]+1, DP[y][2]});
}
}
void initialize(int n, vector<int> A, vector<int> B){
for(int i=0; i<n-1; i++){
link[A[i]].push_back(B[i]);
link[B[i]].push_back(A[i]);
}
}
int cat(int v){
arr[v] = 1;
calc(1);
return min({DP[1][0], DP[1][1], DP[1][2]});
}
int dog(int v) {
arr[v] = 2;
calc(1);
return min({DP[1][0], DP[1][1], DP[1][2]});
}
int neighbor(int v){
arr[v] = 0;
calc(1);
return min({DP[1][0], DP[1][1], DP[1][2]});
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
2636 KB |
Output is correct |
2 |
Correct |
2 ms |
2636 KB |
Output is correct |
3 |
Correct |
2 ms |
2636 KB |
Output is correct |
4 |
Correct |
2 ms |
2636 KB |
Output is correct |
5 |
Correct |
2 ms |
2636 KB |
Output is correct |
6 |
Correct |
2 ms |
2636 KB |
Output is correct |
7 |
Correct |
3 ms |
2652 KB |
Output is correct |
8 |
Correct |
2 ms |
2636 KB |
Output is correct |
9 |
Correct |
2 ms |
2636 KB |
Output is correct |
10 |
Correct |
2 ms |
2636 KB |
Output is correct |
11 |
Correct |
2 ms |
2636 KB |
Output is correct |
12 |
Correct |
2 ms |
2656 KB |
Output is correct |
13 |
Correct |
2 ms |
2636 KB |
Output is correct |
14 |
Correct |
2 ms |
2636 KB |
Output is correct |
15 |
Correct |
2 ms |
2636 KB |
Output is correct |
16 |
Correct |
2 ms |
2636 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
2636 KB |
Output is correct |
2 |
Correct |
2 ms |
2636 KB |
Output is correct |
3 |
Correct |
2 ms |
2636 KB |
Output is correct |
4 |
Correct |
2 ms |
2636 KB |
Output is correct |
5 |
Correct |
2 ms |
2636 KB |
Output is correct |
6 |
Correct |
2 ms |
2636 KB |
Output is correct |
7 |
Correct |
3 ms |
2652 KB |
Output is correct |
8 |
Correct |
2 ms |
2636 KB |
Output is correct |
9 |
Correct |
2 ms |
2636 KB |
Output is correct |
10 |
Correct |
2 ms |
2636 KB |
Output is correct |
11 |
Correct |
2 ms |
2636 KB |
Output is correct |
12 |
Correct |
2 ms |
2656 KB |
Output is correct |
13 |
Correct |
2 ms |
2636 KB |
Output is correct |
14 |
Correct |
2 ms |
2636 KB |
Output is correct |
15 |
Correct |
2 ms |
2636 KB |
Output is correct |
16 |
Correct |
2 ms |
2636 KB |
Output is correct |
17 |
Correct |
12 ms |
2712 KB |
Output is correct |
18 |
Correct |
15 ms |
2728 KB |
Output is correct |
19 |
Correct |
10 ms |
2716 KB |
Output is correct |
20 |
Correct |
2 ms |
2636 KB |
Output is correct |
21 |
Correct |
4 ms |
2660 KB |
Output is correct |
22 |
Correct |
4 ms |
2636 KB |
Output is correct |
23 |
Correct |
20 ms |
2636 KB |
Output is correct |
24 |
Correct |
14 ms |
2716 KB |
Output is correct |
25 |
Correct |
7 ms |
2636 KB |
Output is correct |
26 |
Correct |
5 ms |
2636 KB |
Output is correct |
27 |
Correct |
4 ms |
2636 KB |
Output is correct |
28 |
Correct |
6 ms |
2636 KB |
Output is correct |
29 |
Correct |
18 ms |
2780 KB |
Output is correct |
30 |
Correct |
5 ms |
2636 KB |
Output is correct |
31 |
Correct |
3 ms |
2636 KB |
Output is correct |
32 |
Correct |
5 ms |
2636 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
2636 KB |
Output is correct |
2 |
Correct |
2 ms |
2636 KB |
Output is correct |
3 |
Correct |
2 ms |
2636 KB |
Output is correct |
4 |
Correct |
2 ms |
2636 KB |
Output is correct |
5 |
Correct |
2 ms |
2636 KB |
Output is correct |
6 |
Correct |
2 ms |
2636 KB |
Output is correct |
7 |
Correct |
3 ms |
2652 KB |
Output is correct |
8 |
Correct |
2 ms |
2636 KB |
Output is correct |
9 |
Correct |
2 ms |
2636 KB |
Output is correct |
10 |
Correct |
2 ms |
2636 KB |
Output is correct |
11 |
Correct |
2 ms |
2636 KB |
Output is correct |
12 |
Correct |
2 ms |
2656 KB |
Output is correct |
13 |
Correct |
2 ms |
2636 KB |
Output is correct |
14 |
Correct |
2 ms |
2636 KB |
Output is correct |
15 |
Correct |
2 ms |
2636 KB |
Output is correct |
16 |
Correct |
2 ms |
2636 KB |
Output is correct |
17 |
Correct |
12 ms |
2712 KB |
Output is correct |
18 |
Correct |
15 ms |
2728 KB |
Output is correct |
19 |
Correct |
10 ms |
2716 KB |
Output is correct |
20 |
Correct |
2 ms |
2636 KB |
Output is correct |
21 |
Correct |
4 ms |
2660 KB |
Output is correct |
22 |
Correct |
4 ms |
2636 KB |
Output is correct |
23 |
Correct |
20 ms |
2636 KB |
Output is correct |
24 |
Correct |
14 ms |
2716 KB |
Output is correct |
25 |
Correct |
7 ms |
2636 KB |
Output is correct |
26 |
Correct |
5 ms |
2636 KB |
Output is correct |
27 |
Correct |
4 ms |
2636 KB |
Output is correct |
28 |
Correct |
6 ms |
2636 KB |
Output is correct |
29 |
Correct |
18 ms |
2780 KB |
Output is correct |
30 |
Correct |
5 ms |
2636 KB |
Output is correct |
31 |
Correct |
3 ms |
2636 KB |
Output is correct |
32 |
Correct |
5 ms |
2636 KB |
Output is correct |
33 |
Execution timed out |
3057 ms |
6920 KB |
Time limit exceeded |
34 |
Halted |
0 ms |
0 KB |
- |