#include <bits/stdc++.h>
#include "catdog.h"
using namespace std;
typedef long long ll;
typedef vector<int>vi;
#define pb push_back
#define sz(v) (int)v.size()
#define all(x) begin(x),end(x)
#define FOR(i,a,b) for(int i=a; i<b; i++)
#define ROF(i,a,b) for(int i=b-1; i>=a; i--)
//--------------------------------------------//
void ckmin(int &x, int y){x=min(x,y);}
const int INF=1e8;
const int MX=1000+10;
int N;
vi adj[MX];
vi cat_here(MX,0),dog_here(MX,0);
void initialize(int N, vi A, vi B) {
::N=N;
FOR(i,0,N-1){
int u=A[i],v=B[i];
adj[u].pb(v);
adj[v].pb(u);
}
}
int memo[MX][2][2];
int solve(int u, int p, int c, int d){
int &ind=memo[u][c][d];
if(ind!=-1) return ind;
if(!c && cat_here[u]) return INF;
if(!d && dog_here[u]) return INF;
int ans=0;
for(int v: adj[u]) if(v!=p){
if(solve(v,u,0,0)>N){
if(c+d>0){
ans+=min(solve(v,u,0,1)+c,solve(v,u,1,0)+d);
if(ans>INF) ans=INF;
}
else ans=INF;
}
}
return ind=ans;
}
int get(){
memset(memo,-1,sizeof(memo));
int ans=solve(1,1,0,0);
//cout << ans << endl;
ckmin(ans,solve(1,1,1,0));
//cout << ans << endl;
ckmin(ans,solve(1,1,0,1));
//cout << ans << endl;
//cout << endl;
return ans;
}
int cat(int v){
cat_here[v]=1;
return get();
}
int dog(int v){
dog_here[v]=1;
return get();
}
int neighbor(int v){
dog_here[v]=0;
cat_here[v]=0;
return get();
}
/*
5
1 2
2 3
2 4
4 5
5
1 3
2 5
1 2
2 1
3 2
*/
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
1 ms |
332 KB |
Output is correct |
4 |
Correct |
1 ms |
332 KB |
Output is correct |
5 |
Correct |
1 ms |
332 KB |
Output is correct |
6 |
Correct |
1 ms |
332 KB |
Output is correct |
7 |
Correct |
1 ms |
332 KB |
Output is correct |
8 |
Correct |
1 ms |
332 KB |
Output is correct |
9 |
Correct |
1 ms |
332 KB |
Output is correct |
10 |
Correct |
1 ms |
332 KB |
Output is correct |
11 |
Correct |
1 ms |
332 KB |
Output is correct |
12 |
Correct |
1 ms |
332 KB |
Output is correct |
13 |
Correct |
1 ms |
332 KB |
Output is correct |
14 |
Correct |
1 ms |
332 KB |
Output is correct |
15 |
Correct |
1 ms |
332 KB |
Output is correct |
16 |
Correct |
1 ms |
332 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
1 ms |
332 KB |
Output is correct |
4 |
Correct |
1 ms |
332 KB |
Output is correct |
5 |
Correct |
1 ms |
332 KB |
Output is correct |
6 |
Correct |
1 ms |
332 KB |
Output is correct |
7 |
Correct |
1 ms |
332 KB |
Output is correct |
8 |
Correct |
1 ms |
332 KB |
Output is correct |
9 |
Correct |
1 ms |
332 KB |
Output is correct |
10 |
Correct |
1 ms |
332 KB |
Output is correct |
11 |
Correct |
1 ms |
332 KB |
Output is correct |
12 |
Correct |
1 ms |
332 KB |
Output is correct |
13 |
Correct |
1 ms |
332 KB |
Output is correct |
14 |
Correct |
1 ms |
332 KB |
Output is correct |
15 |
Correct |
1 ms |
332 KB |
Output is correct |
16 |
Correct |
1 ms |
332 KB |
Output is correct |
17 |
Correct |
26 ms |
372 KB |
Output is correct |
18 |
Correct |
30 ms |
332 KB |
Output is correct |
19 |
Correct |
15 ms |
332 KB |
Output is correct |
20 |
Correct |
1 ms |
332 KB |
Output is correct |
21 |
Correct |
5 ms |
460 KB |
Output is correct |
22 |
Correct |
6 ms |
340 KB |
Output is correct |
23 |
Correct |
37 ms |
332 KB |
Output is correct |
24 |
Correct |
30 ms |
372 KB |
Output is correct |
25 |
Correct |
16 ms |
372 KB |
Output is correct |
26 |
Correct |
6 ms |
332 KB |
Output is correct |
27 |
Correct |
5 ms |
332 KB |
Output is correct |
28 |
Correct |
9 ms |
440 KB |
Output is correct |
29 |
Correct |
44 ms |
460 KB |
Output is correct |
30 |
Correct |
5 ms |
332 KB |
Output is correct |
31 |
Correct |
3 ms |
332 KB |
Output is correct |
32 |
Correct |
8 ms |
376 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
1 ms |
332 KB |
Output is correct |
4 |
Correct |
1 ms |
332 KB |
Output is correct |
5 |
Correct |
1 ms |
332 KB |
Output is correct |
6 |
Correct |
1 ms |
332 KB |
Output is correct |
7 |
Correct |
1 ms |
332 KB |
Output is correct |
8 |
Correct |
1 ms |
332 KB |
Output is correct |
9 |
Correct |
1 ms |
332 KB |
Output is correct |
10 |
Correct |
1 ms |
332 KB |
Output is correct |
11 |
Correct |
1 ms |
332 KB |
Output is correct |
12 |
Correct |
1 ms |
332 KB |
Output is correct |
13 |
Correct |
1 ms |
332 KB |
Output is correct |
14 |
Correct |
1 ms |
332 KB |
Output is correct |
15 |
Correct |
1 ms |
332 KB |
Output is correct |
16 |
Correct |
1 ms |
332 KB |
Output is correct |
17 |
Correct |
26 ms |
372 KB |
Output is correct |
18 |
Correct |
30 ms |
332 KB |
Output is correct |
19 |
Correct |
15 ms |
332 KB |
Output is correct |
20 |
Correct |
1 ms |
332 KB |
Output is correct |
21 |
Correct |
5 ms |
460 KB |
Output is correct |
22 |
Correct |
6 ms |
340 KB |
Output is correct |
23 |
Correct |
37 ms |
332 KB |
Output is correct |
24 |
Correct |
30 ms |
372 KB |
Output is correct |
25 |
Correct |
16 ms |
372 KB |
Output is correct |
26 |
Correct |
6 ms |
332 KB |
Output is correct |
27 |
Correct |
5 ms |
332 KB |
Output is correct |
28 |
Correct |
9 ms |
440 KB |
Output is correct |
29 |
Correct |
44 ms |
460 KB |
Output is correct |
30 |
Correct |
5 ms |
332 KB |
Output is correct |
31 |
Correct |
3 ms |
332 KB |
Output is correct |
32 |
Correct |
8 ms |
376 KB |
Output is correct |
33 |
Runtime error |
29 ms |
4324 KB |
Execution killed with signal 11 |
34 |
Halted |
0 ms |
0 KB |
- |