| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1151962 | AgentPengin | Cats or Dogs (JOI18_catdog) | C++20 | 0 ms | 0 KiB |
/**
* author: AgentPengin ( Độc cô cầu bại )
* created: 23.12.2022 10:08:02
* too lazy to update time
**/
#include "catdog.h"
#include<bits/stdc++.h>
#define EL '\n'
#define fi first
#define se second
#define NAME "TASK"
#define ll long long
#define lcm(a,b) (a/gcd(a,b))*b
#define db(val) "["#val" = " << (val) << "] "
#define bend(v) (v).begin(),(v).end()
#define sz(v) (int)(v).size()
#define ex exit(0)
using namespace std;
const ll mod = 1e9 + 7;
const ll inf = 1e17;
const int MAXN = 1e5 + 5;
const int N = MAXN;
int n, sz[MAXN], c[MAXN];
vector<int> adj[MAXN];
int par[MAXN];
struct Node {
ll dp[2][2];
Node (int a = 0, int b = 0, int c = 0, int d = 0) {
dp[0][0] = a;
dp[0][1] = b;
dp[1][0] = c;
dp[1][1] = d;
}
};
Node operator + (const Node& x, const Node& y) {
Node res = Node(inf, inf, inf, inf);
for (int i = 0;i < 2;i++) {
for (int j = 0;j < 2;j++) {
for (int k = 0;k < 2;k++) {
for (int l = 0;l < 2;l++) {
res.dp[i][l] = min(res.dp[i][l], x.dp[i][j] + y.dp[k][l] + (j ^ k));
}
}
}
}
return res;
}
struct Segtree {
vector<Node> st;
int n;
void build(int id, int l,int r) {
if (l == r) {
st[id] = Node(0, inf, inf, 0);
return;
}
int mid = l + r >> 1ll;
build(id << 1, l, mid);
build(id << 1 | 1, mid + 1, r);
st[id] = st[id << 1] + st[id << 1 | 1];
}
void upd(int id, int l, int r, int pos, int val1, int val2) {
if (l == r) {
st[id].dp[0][0] += val1;
st[id].dp[1][1] += val2;
return;
}
int mid = l + r >> 1LL;
if (pos <= mid) {
upd(id << 1, l, mid, pos, val1, val2);
} else {
upd(id << 1 | 1,mid + 1, r, pos, val1, val2);
}
st[id] = st[id << 1] + st[id << 1 | 1];
}
void init(int sz) {
n = sz;
st.resize(n * 4);
build(1, 1, n);
}
pair<int,int> get() {
pair<int,int> res;
res.fi = min(st[1].dp[0][0], st[1].dp[0][1]);
res.se = min(st[1].dp[1][0], st[1].dp[1][1]);
return make_pair(min(res.fi, res.se + 1), min(res.fi + 1, res.se));
}
} seg[MAXN];
void dfs1(int u, int p) {
par[u] = p;
sz[u] = 1;
for (auto v : adj[u]) {
if (v != p) {
dfs1(v, u);
sz[u] += sz[v];
}
}
for (auto &v : adj[u]) {
if (v == p) {
swap(adj[u][sz(adj[u]) - 1],v);
adj[u].pop_back();
break;
}
}
sort(bend(adj[u]), [&](int x,int y){
return sz[x] > sz[y];
});
}
int tin = 0, head[MAXN], pos[MAXN];
void dfs2(int u, int p, int cur) {
par[u] = cur;
if (sz[cur] == 0) {
head[cur] = p;
}
pos[u] = ++sz[cur];
for (auto v : adj[u]) {
if (adj[u].front() == v) {
dfs2(v, u, cur);
} else {
dfs2(v, u, tin++);
}
}
}
void initialize(int _n, vector<int> a, vector<int> b) {
n = _n;
for (int i = 0;i < n - 1;i++) {
adj[a[i]].push_back(b[i]);
adj[b[i]].push_back(a[i]);
}
dfs1(1, 0);
memset(par, 0, sizeof par);
memset(sz, 0, sizeof sz);
dfs2(1, 0, tin++);
for (int i = 0;i < tin;i++) {
seg[i].init(sz[i]);
}
}
int upd(int u, int val1, int val2) {
while(u != 0) {
int cur = par[u];
auto [a0, a1] = seg[cur].get();
seg[cur].upd(1, 1, sz[cur], pos[u], val1, val2);
auto [b0, b1] = seg[cur].get();
val1 = b0 - a0;
val2 = b1 - a1;
u = head[cur];
}
auto [a, b] = seg[0].get();
return min(a, b);
}
int cat(int u) {
c[u] = 1;
int res = upd(u, N, 0);a
return res;
}
int dog(int u) {
c[u] = 2;
int res = upd(u, 0, N);
return res;
}
int neighbor(int u) {
int res = 0;
if (c[u] == 1) {
res = upd(u, -N, 0);
} else {
res = upd(u, 0, -N);
}
c[u] = 0;
return res;
}