#include <bits/stdc++.h>
#define FAST ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);cerr.tie(0)
#define mp make_pair
#define xx first
#define yy second
#define pb push_back
#define pf push_front
#define popb pop_back
#define popf pop_front
#define all(x) x.begin(),x.end()
#define ff(i,a,b) for (int i = a; i < b; i++)
#define fff(i,a,b) for (int i = a; i <= b; i++)
#define bff(i,a,b) for (int i = b-1; i >= a; i--)
#define bfff(i,a,b) for (int i = b; i >= a; i--)
using namespace std;
long double typedef ld;
unsigned int typedef ui;
long long int typedef li;
pair<int,int> typedef pii;
pair<li,li> typedef pli;
pair<ld,ld> typedef pld;
vector<vector<int>> typedef graph;
unsigned long long int typedef ull;
//const int mod = 998244353;
const int mod = 1000000007;
//Note to self: Check for overflow
#include "catdog.h"
int n;
int kolko=0; //kolko ukupno ukljucenih; ako nije niko ukljucen treba vratiti 0...
graph g(100005);
li dp[100005][3]; //closed, open cat, open dog
int ko[100005]; //0 = niko, 1 = cat, 2 = dog
void dfs(int p, int q)
{
dp[p][1]=0,dp[p][2]=0;
for (auto it : g[p]) if (it!=q)
{
dfs(it,p);
dp[p][1]+=min(dp[it][0],dp[it][1]);
dp[p][2]+=min(dp[it][0],dp[it][2]);
}
if (ko[p]==1) dp[p][2]=mod;
if (ko[p]==2) dp[p][1]=mod;
dp[p][0]=min(dp[p][1],dp[p][2])+1;
}
int solve()
{
if (kolko==0) return 0;
return dfs(1,0),dp[1][0];
}
void initialize(int N, vector<int> A, vector<int> B)
{
n=N;
ff(i,0,n-1) g[A[i]].pb(B[i]),g[B[i]].pb(A[i]);
}
int cat(int v)
{
kolko++,ko[v]=1;
return solve();
}
int dog(int v)
{
kolko++,ko[v]=2;
return solve();
}
int neighbor(int v)
{
kolko--,ko[v]=0;
return solve();
}
/*
6
1 2
1 3
1 4
4 5
4 6
4
1 5
2 6
2 3
1 2
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
2644 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
2644 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
2644 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
