#include "catdog.h"
#include <bits/stdc++.h>
#define se second
#define fi first
#define pb push_back
using namespace std;
const int N = 1e5 + 3;
const int inf = 1 << 30;
int n, A[N], p[N], anc[N], d[N];
int dp[N][2];
vector<int> G[N];
struct CD{
void insert(int v, int cd){
}
void erase(int v){
}
} V[N];
void dfs(int v, int par){
for(auto i : G[v]){
if(i != par){
p[i] = v;
anc[i] = (G[v].size() - (v != 1) == 1) ? anc[v] : v;
d[i] = d[v] + 1;
dfs(i, v);
}
}
}
void initialize(int n, vector<int> A, vector<int> B) {
::n = n;
for(int i = 0; i < n - 1; i++){
G[A[i]].pb(B[i]);
G[B[i]].pb(A[i]);
}
dfs(1, -1);
map<int, vector<int>> PC;
for(int i = 1; i <= n; i++){
PC[anc[i]].push_back(i);
}
for(auto& i : PC){
sort(i.se.begin(), i.se.end(), [](int a, int b){
return d[a] < d[b];
});
}
}
void lift(int v){
while(v != 0){
for(auto i : G[v]){
dp[v][0] = dp[v][1] = 0;
if(i != p[v]){
dp[v][0] += min(dp[i][0], dp[i][1] + 1);
dp[v][1] += min(dp[i][1], dp[i][0] + 1);
}
}
if(A[v] == 1) dp[v][1] = inf;
else if(A[v] == 2) dp[v][0] = inf;
v = p[v];
}
}
int cat(int v) {
A[v] = 1;
V[anc[v]].insert(v, 1);
lift(v);
// cout << "c<<<" << endl;
// for(int i = 1; i <= n; i++){
// cout << dp[i][0] << ' ' << dp[i][1] << endl;
// }
return min(dp[1][0], dp[1][1]);
}
int dog(int v) {
A[v] = 2;
V[anc[v]].insert(v, 2);
lift(v);
// cout << "d<<<" << endl;
// for(int i = 1; i <= n; i++){
// cout << dp[i][0] << ' ' << dp[i][1] << endl;
// }
return min(dp[1][0], dp[1][1]);
}
int neighbor(int v) {
A[v] = 0;
V[anc[v]].erase(v);
lift(v);
// cout << "n<<<" << endl;
// for(int i = 1; i <= n; i++){
// cout << dp[i][0] << ' ' << dp[i][1] << endl;
// }
return min(dp[1][0], dp[1][1]);
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
2644 KB |
Output is correct |
2 |
Incorrect |
2 ms |
2644 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
2644 KB |
Output is correct |
2 |
Incorrect |
2 ms |
2644 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
2644 KB |
Output is correct |
2 |
Incorrect |
2 ms |
2644 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |