#include "catdog.h"
#include <bits/stdc++.h>
#define se second
#define fi first
#define pb push_back
#define mp make_pair
using namespace std;
typedef pair<int, int> pii;
const int N = 1e5 + 3;
const int inf = 1 << 30;
int n, A[N], p[N], des[N], d[N], psg[N];
int v[N][2], dp[N][2];
vector<int> G[N], H[N];
int dif(pii a, pii b){
if(a.se == 0 || b.se == 0) return 0;
return a.se != b.se;
}
struct CD{
set<pair<int, int>> s; int ans = 0, top = 0, bot = 0, bp = inf;
void insert(int v, int cd){
auto ptr = s.lower_bound({v, cd});
pii m1 = ptr != s.begin() ? *prev(ptr) : mp(0, 0);
pii p1 = ptr != s.end() ? *ptr : mp(0, 0);
ans += dif({v, cd}, m1) + dif({v, cd}, p1) - dif(m1, p1);
s.insert({v, cd});
top = s.empty() ? 0 : (s.begin())->se;
bot = s.empty() ? 0 : (--s.end())->se;
bp = s.empty() ? inf : (--s.end())->fi;
}
void erase(int v){
auto ptr = s.lower_bound({v, -1});
pii m1 = ptr != s.begin() ? *prev(ptr) : mp(0, 0);
pii p1 = ptr != s.end() && next(ptr) != s.end() ? *next(ptr) : mp(0, 0);
ans += dif(m1, p1) - dif(*ptr, m1) - dif(*ptr, p1);
s.erase(ptr);
top = s.empty() ? 0 : (s.begin())->se;
bot = s.empty() ? 0 : (--s.end())->se;
bp = s.empty() ? inf : (--s.end())->fi;
}
} V[N];
void dfs(int v, int par){
des[v] = v;
for(auto i : G[v]){
if(i != par){
p[i] = v;
d[i] = d[v] + 1;
dfs(i, v);
des[v] = (G[v].size() - (v != 1) == 1) ? des[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[des[i]].push_back(i);
}
// for(int i = 1; i <= n; i++){
// cout << des[i] << ' ';
// }
// cout << endl;
for(auto& i : PC){
sort(i.se.begin(), i.se.end(), [](int a, int b){
return d[a] < d[b];
});
}
vector<int> sg;
for(auto i : PC){
sg.pb(i.se[0]);
}
for(auto i : sg){
H[p[i]].pb(des[i]);
psg[des[i]] = p[i];
}
}
void lift(int v){
while(true){
dp[v][0] = dp[v][1] = V[v].ans;
for(auto i : H[v]){
dp[v][0] += min(dp[i][0], dp[i][1] + 1);
dp[v][1] += min(dp[i][1], dp[i][0] + 1);
}
if(V[v].bp == d[v]){
if(V[v].bot == 1) dp[v][1] = inf;
else if(V[v].bot == 2) dp[v][0] = inf;
}else{
if(V[v].bot == 1) dp[v][1]++;
else if(V[v].bot == 2) dp[v][0]++;
}
if(V[v].top + V[v].bot == 3) swap(dp[v][0], dp[v][1]);
if(V[v].top == 1) dp[v][1] = inf;
else if(V[v].top == 2) dp[v][0] = inf;
if(v == 0) return;
v = psg[v];
}
}
int sol(){
return min(dp[0][0], dp[0][1]);
}
void out(char c){
// cout << c << "<<<" << endl;
// for(int i = 0; i <= n; i++){
// cout << dp[i][0] << ' ' << dp[i][1] << endl;
// }
}
int cat(int v) {
A[v] = 1;
V[des[v]].insert(d[v], 1);
lift(des[v]);
out('c');
return sol();
}
int dog(int v) {
A[v] = 2;
V[des[v]].insert(d[v], 2);
lift(des[v]);
out('d');
return sol();
}
int neighbor(int v) {
A[v] = 0;
V[des[v]].erase(d[v]);
lift(des[v]);
out('n');
return sol();
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
11220 KB |
Output is correct |
| 2 |
Incorrect |
6 ms |
11220 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
11220 KB |
Output is correct |
| 2 |
Incorrect |
6 ms |
11220 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
11220 KB |
Output is correct |
| 2 |
Incorrect |
6 ms |
11220 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
