| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 848004 | LeonaRaging | Cats or Dogs (JOI18_catdog) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "catdog.h"
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
const int maxn = 1e5 + 4;
const int INF = 1e9;
int n, sz[maxn], R[maxn], B[maxn], col[maxn], par[maxn];
int chain[maxn], head[maxn], from[maxn], to[maxn], tin[maxn];
vector<int> adj[maxn];
struct Node {
int a[2][2];
Node() {
for (int i = 0; i < 2; i++)
for (int j = 0; j < 2; j++)
a[i][j] = INF;
}
};
struct seg_tree {
vector<Node> t;
seg_tree() {
t.resize(4 * maxn);
}
Node merge(Node L, Node R) {
Node res;
for (int i = 0; i < 2; i++)
for (int j = 0; j < 2; j++)
for (int x = 0; x < 2; x++)
for (int y = 0; y < 2; y++)
res.a[i][j] = min(res.a[i][j], L.a[i][x] + R.a[y][j] + (x != y));
return res;
}
void update(int pos, int v = 1, int l = 1, int r = maxn - 1) {
if (l == r) {
if (l == 1) clog << col[l] << endl;
t[v].a[0][0] = (col[l] == 1 ? INF : R[l]);
t[v].a[1][1] = (col[l] == 0 ? INF : B[l]);
t[v].a[0][1] = t[v].a[1][0] = INF;
return;
}
int m = (l + r) / 2;
if (pos <= m) update(pos, 2 * v, l, m);
else update(pos, 2 * v + 1, m + 1, r);
t[v] = merge(t[2 * v], t[2 * v + 1]);
}
Node get(int l, int r, int v = 1, int tl = 1, int tr = maxn - 1) {
if (tl >= l && tr <= r) return t[v];
int m = (tl + tr) / 2;
if (r <= m) return get(l, r, 2 * v, tl, m);
else if (l > m) return get(l, r, 2 * v + 1, m + 1, tr);
else return merge(get(l, r, 2 * v, tl, m), get(l, r, 2 * v + 1, m + 1, tr));
}
} IT;
void dfs(int u, int p) {
sz[u] = 1;
for (int v : adj[u]) if (v != p) {
par[v] = u;
dfs(v, u);
sz[u] += sz[v];
}
}
void hld(int u) {
tin[u] = ++tin[0];
chain[u] = chain[0];
int mx = 0;
for (int v : adj[u])
if (v != par[u] && sz[v] > sz[mx])
mx = v;
if (mx) hld(mx);
for (int v : adj[u])
if (v != par[u] && v != mx) {
chain[0]++;
hld(v);
}
}
void update(int v) {
while (v) {
int u = par[head[chain[v]]];
Node cur = IT.get(from[chain[v]], to[chain[v]]);
if (col[u] != 1)
R[u] -= min({cur.a[0][0], cur.a[0][1], cur.a[1][0] + 1, cur.a[1][1] + 1});
if (col[u] != 0)
B[u] -= min({cur.a[0][0] + 1, cur.a[0][1] + 1, cur.a[1][0], cur.a[1][1]});
IT.update(v);
if (col[u] != 1)
R[u] -= min({cur.a[0][0], cur.a[0][1], cur.a[1][0] + 1, cur.a[1][1] + 1});
if (col[u] != 0)
B[u] -= min({cur.a[0][0] + 1, cur.a[0][1] + 1, cur.a[1][0], cur.a[1][1]});
v = u;
}
}
int get() {
Node cur = IT.get(from[0], to[0]);
int res = INF;
for (int i = 0; i < 2; i++)
for (int j = 0; j < 2; j++)
res = min(res, cur.a[i][j]);
return res;
}
void initialize(int N, int A[], int B[]) {
n = N;
for (int i = 0; i < n - 1; i++) {
adj[A[i]].pb(B[i]);
adj[B[i]].pb(A[i]);
}
dfs(1, 0);
hld(1);
for (int i = 0; i <= chain[0]; i++)
from[i] = INF;
for (int i = 1; i <= n; i++) {
from[chain[i]] = min(from[chain[i]], tin[i]);
to[chain[i]] = max(to[chain[i]], tin[i]);
col[i] = -1;
}
for (int i = 1; i <= n; i++)
IT.update(i);
}
int cat(int v) {
col[v] = 0;
update(v);
return get();
}
int dog(int v) {
col[v] = 1;
update(v);
return get();
}
int neighbor(int v) {
col[v] = -1;
update(v);
return get();
}
// int main()
// {
// ios::sync_with_stdio(0);
// cin.tie(0); cout.tie(0);
// if (fopen("Pets.INP", "r")) {
// freopen("Pets.INP", "r", stdin);
// freopen("Pets.OUT", "w", stdout);
// }
// cin >> n;
// for (int i = 1, u, v; i < n; i++) {
// cin >> u >> v;
// adj[u].pb(v);
// adj[v].pb(u);
// }
// dfs(1, 0);
// hld(1);
// for (int i = 0; i <= chain[0]; i++)
// from[i] = INF;
// for (int i = 1; i <= n; i++) {
// from[chain[i]] = min(from[chain[i]], tin[i]);
// to[chain[i]] = max(to[chain[i]], tin[i]);
// col[i] = -1;
// }
// for (int i = 1; i <= n; i++)
// IT.update(i);
// int q; cin >> q;
// while (q--) {
// int t, u; cin >> t >> u;
// if (t == 1) col[u] = 0;
// if (t == 2) col[u] = 1;
// if (t == 3) col[u] = -1;
// update(u);
// cout << get() << '\n';
// }
// }