#include "catdog.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> ii;
typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<ll> vll;
#define REP(a,b,c) for(int a=int(b); a<int(c); a++)
#define REV(a,b,c) for(int a=int(c-1); a>=int(b); a--)
#define RE(a,b) REP(a,0,b)
#define RE1(a,b) REP(a,1,b+1)
#define FOR(a,b) for(auto& a : b)
#define pb push_back
#define all(a) a.begin(),a.end()
#define fi first
#define se second
const int INF = 1e9;
const int MX = 5e5;
const int N = 1<<20;
const int MOD = 1e9+7;
int n;
int a[MX];
// tree stuff
vi adj[MX], chl[MX];
int sz[MX], par[MX], dep[MX];
void dfs(int u, int p) {
sz[u] = 1;
par[u] = p;
dep[u] = dep[p]+1;
FOR(v,adj[u]) {
if(v == p) continue;
dfs(v,u);
sz[u] += sz[v];
}
}
void initialize(int N, std::vector<int> A, std::vector<int> B) {
n = N;
RE(i,n-1) {
adj[A[i]].pb(B[i]);
adj[B[i]].pb(A[i]);
}
dfs(1,1);
}
// dp
int dp[MX][2];
void dfsDP(int u) {
FOR(v,chl[u]) dfsDP(v);
RE(i,2) {
dp[u][i] = 0;
FOR(v,chl[u])
dp[u][i] += min(dp[v][i], dp[v][!i]+1);
if(i == a[u]-1) dp[u][i] = INF;
}
}
int solve() {
dfsDP(1);
return min(dp[1][0], dp[1][1]);
}
int cat(int v) {
a[v] = 1;
return solve();
}
int dog(int v) {
a[v] = 2;
return solve();
}
int neighbor(int v) {
a[v] = 0;
return solve();
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
17 ms |
23820 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
17 ms |
23820 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
17 ms |
23820 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
