| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 680638 | nutella | Cats or Dogs (JOI18_catdog) | C++17 | 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 <bits/stdc++.h>
#include "catdog.h"
using namespace std;
int n;
constexpr int N = 100001;
vector<int> g[N];
int head[N], sz[N], parent[N], tin[N], T = 0, hld_sz[N], type[N];
int ans = 0;
array<int, 3> sum[N];
void dfs_init(int v) {
auto it = find(g[v].begin(), g[v].end(), parent[v]);
if (it != g[v].end()) {
g[v].erase(it);
}
sz[v] = 1;
for (int &to: g[v]) {
parent[to] = v;
dfs_init(to);
sz[v] += sz[to];
if (sz[to] > sz[g[v][0]]) {
swap(to, g[v][0]);
}
}
}
void dfs_hld(int v) {
if (head[v] == 0) {
head[v] = v;
}
hld_sz[head[v]] += 1;
tin[v] = T++;
for (int &to: g[v]) {
if (to == g[v][0]) {
head[to] = head[v];
}
dfs_hld(to);
}
}
struct Info {
int dp[4]{};
Info() = default;
Info(int d[4]) {
memcpy(dp, d, sizeof(dp));
}
};
Info operator+(Info &a, Info &b) {
Info res;
memset(res.dp, 0x3f, sizeof(res.dp));
for (int i = 0; i < 4; ++i) {
for (int j = 0; j < 4; ++j) {
res.dp[]
}
}
}
struct SegmentTree {
vector<Info> t;
int n{};
void init(int m) {
n = 1 << (__lg(m) + bool(m & (m - 1)));
t.assign(2 * n, {});
}
void modify(int i, Info x) {
for (t[i += n] = x; i >>= 1;) {
t[i] = t[i << 1] + t[i << 1 | 1];
}
}
array<int, 3> ans() {
array<int, 3> ans{};
for (int i = 0; i < 3; ++i) {
ans[i] = min({t[1].dp[i][0], t[1].dp[i][1], t[1].dp[i][2], t[1].dq[i]});
}
int mn = min({ans[0], ans[1], ans[2]});
for (int i = 0; i < 3; ++i) {
ans[i] = min(ans[i], mn + 1);
}
return ans;
}
int best() {
int ans = numeric_limits<int>::max();
for (int i = 0; i < 3; ++i) {
ans = min({ans, t[1].dp[i][0], t[1].dp[i][1], t[1].dp[i][2], t[1].dq[i]});
}
return ans;
}
};
SegmentTree t[N];
void update(int v) {
while (true) {
int p = head[v];
if (p != 1) {
auto kek = t[p].ans();
for (int i = 0; i < 3; ++i) {
sum[parent[p]][i] -= kek[i];
}
}
array<int, 3> now{};
if (type[v] == 2) {
now = sum[v];
} else {
now[0] = now[1] = now[2] = 0x3f3f3f3f;
now[type[v]] = sum[v][type[v]];
}
t[head[v]].modify(tin[v] - tin[head[v]], now);
if (p != 1) {
auto kek = t[p].ans();
for (int i = 0; i < 3; ++i) {
sum[parent[p]][i] += kek[i];
}
v = parent[p];
} else {
break;
}
}
}
void initialize(int N, std::vector<int> A, std::vector<int> B) {
n = N;
for (int i = 0; i < n - 1; ++i) {
g[A[i]].push_back(B[i]);
g[B[i]].push_back(A[i]);
}
dfs_init(1);
dfs_hld(1);
for (int i = 1; i <= n; ++i) {
if (head[i] == i) {
t[i].init(hld_sz[i]);
}
}
}
int cat(int v) {
type[v] = 0;
update(v);
return t[1].best();
}
int dog(int v) {
type[v] = 1;
update(v);
return t[1].best();
}
int neighbor(int v) {
type[v] = 2;
update(v);
return t[1].best();
}