#include "catdog.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 5;
int n;
vector<int> adj[maxn];
int A[maxn];
int sz[maxn];
int par[maxn];
void dfs_sz(int cur, int prv) {
if (prv) adj[cur].erase(find(adj[cur].begin(), adj[cur].end(), prv));
sz[cur] = 1;
par[cur] = prv;
for (int nxt : adj[cur]) {
dfs_sz(nxt, cur);
sz[cur] += sz[nxt];
}
nth_element(adj[cur].begin(), adj[cur].begin(), adj[cur].end(), [&](int i, int j) {
return sz[i] > sz[j];
});
}
int hvypar[maxn];
int num[maxn];
int pos[maxn];
void dfs_hld(int cur, int top) {
hvypar[cur] = top;
pos[cur] = num[top];
num[top]++;
bool isfrst = true;
for (int nxt : adj[cur]) {
dfs_hld(nxt, (isfrst ? top : nxt));
isfrst = false;
}
}
struct mat {
int a00, a01, a10, a11;
friend mat operator * (const mat& a, const mat& b) {
mat r;
r.a00 = min(a.a00 + b.a00, a.a01 + b.a01);
r.a01 = min(a.a00 + b.a01, a.a01 + b.a11);
r.a10 = min(a.a10 + b.a00, a.a11 + b.a10);
r.a11 = min(a.a10 + b.a01, a.a11 + b.a11);
return r;
}
};
struct segtree {
int s;
vector<mat> cost;
segtree() {}
segtree(int n) {
for (s = 1; s < n; s *= 2) {}
cost = vector<mat>(2 * s);
for (int i = 0; i < 2 * s; i++) cost[i].a01 = cost[i].a10 = 1;
}
void upd(int i, int& v0, int& v1) {
i += s;
cost[i].a00 += v0;
cost[i].a01 += v0;
cost[i].a10 += v1;
cost[i].a11 += v1;
for (i /= 2; i; i /= 2) cost[i] = cost[2 * i] * cost[2 * i + 1];
}
void eval(int& a0, int& a1) {
a0 = min(cost[1].a00, cost[1].a01);
a1 = min(cost[1].a10, cost[1].a11);
}
} seg[maxn];
void initialize(int k, vector<int> a, vector<int> b) {
n = k;
for (int i = 0; i < n - 1; i++) {
adj[a[i]].push_back(b[i]);
adj[b[i]].push_back(a[i]);
}
for (int i = 1; i <= n; i++) A[i] = 0;
dfs_sz(1, 0);
dfs_hld(1, 1);
for (int i = 1; i <= n; i++) {
assert((pos[i] == 0) == (hvypar[i] == i));
if (hvypar[i] == i) seg[i] = segtree(num[i]);
}
}
void upd(int cur, int v0, int v1) {
while (cur) {
int top = hvypar[cur];
int cur0, cur1, nxt0, nxt1;
seg[top].eval(cur0, cur1);
seg[top].upd(pos[cur], v0, v1);
seg[top].eval(nxt0, nxt1);
v0 = min(nxt0, nxt1 + 1) - min(cur0, cur1 + 1);
v1 = min(nxt0 + 1, nxt1) - min(cur0 + 1, cur1);
cur = par[top];
}
}
int qry() {
int a0, a1;
seg[1].eval(a0, a1);
return min(a0, a1);
}
int cat(int v) {
A[v] = 1;
upd(v, 0, n);
return qry();
}
int dog(int v) {
A[v] = 2;
upd(v, n, 0);
return qry();
}
int neighbor(int v) {
if (A[v] == 1) upd(v, 0, -n);
else if (A[v] == 2) upd(v, -n, 0);
else assert(false);
A[v] = 0;
return qry();
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
5716 KB |
Output is correct |
| 2 |
Correct |
4 ms |
5716 KB |
Output is correct |
| 3 |
Incorrect |
3 ms |
5792 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
5716 KB |
Output is correct |
| 2 |
Correct |
4 ms |
5716 KB |
Output is correct |
| 3 |
Incorrect |
3 ms |
5792 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
5716 KB |
Output is correct |
| 2 |
Correct |
4 ms |
5716 KB |
Output is correct |
| 3 |
Incorrect |
3 ms |
5792 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
