QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#884453 | #4408. 燃烧的呐球 | TrueFalse | 0 | 955ms | 458536kb | C++14 | 9.8kb | 2025-02-06 08:27:02 | 2025-02-06 08:27:03 |
Judging History
answer
/**
* @author TrueFalse
* @details cnm 神经斯木题目!!
*/
#include <bits/stdc++.h>
using namespace std;
using ci = const int;
using u32 = uint32_t;
using i64 = int64_t;
using u64 = uint64_t;
template <class T>
inline void Max(T &x, const T &y) noexcept {
if (x < y) x = y;
}
template <class T>
inline void Min(T &x, const T &y) noexcept {
if (y < x) x = y;
}
const int inf = 0x3f3f3f3f;
const int bf_sz = 20 << 24;
char Buf[bf_sz], *bf = Buf + bf_sz;
void Buf_clear() {
memset(bf, 0x00, Buf + bf_sz - bf);
bf = Buf + bf_sz;
}
struct Point {
int x, y;
};
// min with position
struct Minp {
int v, p;
Minp(int _v = inf, int _p = 0) : v(_v), p(_p) {}
bool operator<(const Minp &x) const { return v < x.v; }
void operator+=(int _v) { v += _v; }
Minp operator+(int _v) {
*this += _v;
return *this;
}
};
// minp and second-minp
struct Msp {
using cm = const Msp;
Minp mn, se;
Msp() : mn(), se() {}
Msp(const Minp &_1, const Minp &_2) : mn(_1), se(_2) {}
void operator+=(const Minp &v) {
if (v.p == mn.p) {
Min(mn.v, v.v);
return;
}
if (v.p == se.p) {
Min(se.v, v.v);
if (se < mn) swap(mn, se);
return;
}
if (mn.v > v.v)
se = mn, mn = v;
else
se = min(se, v);
}
void operator+=(cm &v) {
*this += v.mn;
*this += v.se;
}
void operator+=(int v) {
mn += v;
se += v;
}
Msp operator+(int v) {
*this += v;
return *this;
}
Msp operator+(cm &v) {
*this += v;
return *this;
}
};
const int N = 1e6 + 5;
const int M = 1e5 + 5;
int n, m, fa[N], col[M];
int siz[N];
int dfn[N], rnk[N], tcnt;
int sxy[M]; // siz[a[i].x] + siz[a[i].y]
Point a[M];
Msp con[M];
vector<int> e[N];
vector<int> vx[N], vy[N];
i64 ans;
#define Range(u) dfn[u], dfn[u] + siz[u] - 1
void dfs(int u) {
rnk[dfn[u] = ++tcnt] = u;
siz[u] = 1;
for (ci &v : e[u]) {
dfs(v);
siz[u] += siz[v];
}
}
int fd(int x) { return col[x] == x ? x : col[x] = fd(col[x]); }
void mg(int x, int y, int v) {
x = fd(x), y = fd(y);
if (x != y) col[x] = y, ans += v;
}
bool is_merged() {
int tot = 0;
for (int i = 1; i <= n; ++i) col[i] = fd(i), tot += col[i] == i;
return tot == 1;
}
// double unlimited
namespace Case1 {
void solve() {
Msp nw;
for (int i = 1; i <= m; ++i) nw += Minp(sxy[i], col[i]);
for (int i = 1; i <= m; ++i) con[i] += nw + sxy[i];
}
} // namespace Case1
// one is unlimited and another is child
namespace Case2 {
// recognise x or y as the parent
Msp mnx[N], mny[N];
void dfs1(int u) {
for (ci &v : e[u]) {
dfs1(v);
mnx[u] += mnx[v];
mny[u] += mny[v];
}
}
void solve() {
for (int i = 1; i <= n; ++i) mnx[i] = mny[i] = Msp();
for (int i = 1; i <= m; ++i) {
mnx[a[i].x] += Minp(siz[a[i].y] - siz[a[i].x], col[i]);
mny[a[i].y] += Minp(siz[a[i].x] - siz[a[i].y], col[i]);
}
dfs1(1);
for (int i = 1; i <= m; ++i) {
con[i] += mnx[a[i].x] + sxy[i];
con[i] += mny[a[i].y] + sxy[i];
}
}
} // namespace Case2
// one is unlimited and another is parent
namespace Case3 {
// recognise x or y as the child
Msp mnx[N], mny[N];
void dfs1(int u) {
for (ci &v : e[u]) {
mnx[v] += mnx[u];
mny[v] += mny[u];
dfs1(v);
}
}
void solve() {
for (int i = 1; i <= n; ++i) mnx[i] = mny[i] = Msp();
for (int i = 1; i <= m; ++i) {
mnx[a[i].x] += Minp(sxy[i], col[i]);
mny[a[i].y] += Minp(sxy[i], col[i]);
}
dfs1(1);
for (int i = 1, v; i <= m; ++i) {
v = siz[a[i].y] - siz[a[i].x];
con[i] += mnx[a[i].x] + v;
con[i] += mny[a[i].y] + -v;
}
}
} // namespace Case3
// double parent-child
namespace Case4 {
// double children
namespace Case4_1 {
struct Segment {
Msp v;
Segment *ch[2];
Segment() : v() { ch[0] = ch[1] = nullptr; }
void *operator new(size_t sz) { return bf -= sz; }
} *rt[N];
void add(Segment *&p, int l, int r, ci &x, const Minp &y) {
if (!p) p = new Segment();
p->v += y;
if (l == r) return;
int mid = (l + r) >> 1;
if (x <= mid)
add(p->ch[0], l, mid, x, y);
else
add(p->ch[1], mid + 1, r, x, y);
}
Msp ask(Segment *p, int l, int r, ci &al, ci &ar) {
if (!p) return Msp();
if (al <= l and ar >= r) return p->v;
int mid = (l + r) >> 1;
#define Al ask(p->ch[0], l, mid, al, ar)
#define Ar ask(p->ch[1], mid + 1, r, al, ar)
if (al > mid)
return Ar;
else if (ar <= mid)
return Al;
else
return Al + Ar;
#undef Al
#undef Ar
}
Segment *merge(Segment *p, Segment *q, int l, int r) {
if (!p) return q;
if (!q) return p;
p->v += q->v;
if (l == r) return p;
int mid = (l + r) >> 1;
p->ch[0] = merge(p->ch[0], q->ch[0], l, mid);
p->ch[1] = merge(p->ch[1], q->ch[1], mid + 1, r);
return p;
}
void clear() {
Buf_clear();
memset(rt, 0x00, sizeof rt);
}
void dfs1(int u) {
for (ci &v : e[u]) {
dfs1(v);
rt[u] = merge(rt[u], rt[v], 1, n);
}
for (int i : vx[u]) add(rt[u], 1, n, dfn[a[i].y], Minp(-sxy[i], col[i]));
for (int i : vx[u]) con[i] += ask(rt[u], 1, n, Range(a[i].y)) + sxy[i];
}
void solve() {
clear();
dfs1(1);
}
} // namespace Case4_1
// one is parent and another is child
namespace Case4_2 {
using pmi = pair<Msp, int>;
pmi sta[M << 5], *st = sta;
Msp tr[N << 2];
void change(int p, int l, int r, ci &x, const Minp &y) {
*st++ = {tr[p], p};
tr[p] += y;
if (l == r) return;
int mid = (l + r) >> 1;
if (x <= mid)
change(p << 1, l, mid, x, y);
else
change(p << 1 | 1, mid + 1, r, x, y);
}
Msp ask(int p, int l, int r, ci &al, ci &ar) {
if (al <= l and ar >= r) return tr[p];
int mid = (l + r) >> 1;
#define Al ask(p << 1, l, mid, al, ar)
#define Ar ask(p << 1 | 1, mid + 1, r, al, ar)
if (al > mid)
return Ar;
else if (ar <= mid)
return Al;
else
return Al + Ar;
#undef Al
#undef Ar
}
void dfs1(int u) {
const pmi *st_c = st;
for (int i : vx[u])
change(1, 1, n, dfn[a[i].y], Minp(siz[u] - siz[a[i].y], col[i]));
for (int i : vx[u])
con[i] += ask(1, 1, n, Range(a[i].y)) + (siz[a[i].y] - siz[u]);
for (ci &v : e[u]) dfs1(v);
while (st != st_c) --st, tr[st->second] = st->first;
}
void dfs2(int u) {
const pmi *st_c = st;
for (int i : vy[u])
change(1, 1, n, dfn[a[i].x], Minp(siz[u] - siz[a[i].x], col[i]));
for (int i : vy[u])
con[i] += ask(1, 1, n, Range(a[i].x)) + (siz[a[i].x] - siz[u]);
for (ci &v : e[u]) dfs2(v);
while (st != st_c) --st, tr[st->second] = st->first;
}
void solve() {
dfs1(1);
dfs2(1);
}
} // namespace Case4_2
// double parents
namespace Case4_3 {
using pmi = pair<Msp, int>;
int son[N], top[N];
inline void dfs7(int u) {
for (int v : e[u]) {
dfs7(v);
if (siz[v] > siz[son[u]]) son[u] = v;
}
}
inline void dfs8(int u, int rt) {
top[u] = rt;
if (son[u]) dfs8(son[u], rt);
for (int v : e[u])
if (v != son[u]) dfs8(v, v);
}
pmi stk1[M * 32], stk2[M];
int tp1, tp2;
struct BalanceTree {
int ls[N], rs[N], f[N];
Msp w[N], mx[N];
inline void build() {
for (int s = 1; s <= n; ++s)
if (top[s] == s) {
vector<int> sb;
for (int u = s; u; u = son[u]) sb.push_back(u);
function<int(int, int)> link = [&](int x, int y) {
if (x > y) return 0;
int all = 0, tsiz = 0;
for (int i = x; i <= y; ++i) all += siz[sb[i]] - siz[son[sb[i]]];
for (int i = x; i <= y; ++i) {
tsiz += siz[sb[i]] - siz[son[sb[i]]];
if (tsiz > all / 2) {
int p = sb[i];
ls[p] = link(x, i - 1), rs[p] = link(i + 1, y);
if (ls[p]) f[ls[p]] = p;
if (rs[p]) f[rs[p]] = p;
return p;
}
}
return -1;
};
f[link(0, sb.size() - 1)] = fa[s];
}
}
inline void upd(int x, Minp z) {
stk2[++tp2] = {w[x], x}, w[x] += z;
for (; x; x = f[x]) {
stk1[++tp1] = {w[x], x}, mx[x] += z;
if (x != ls[f[x]] && x != rs[f[x]]) break;
}
}
inline Msp qry(int x) {
Msp g = w[x] + mx[ls[x]];
for (; f[x]; x = f[x])
if (x != ls[f[x]]) g += w[f[x]] + mx[ls[f[x]]];
return g;
}
} T;
inline void init() { dfs7(1), dfs8(1, 1), T.build(); }
inline void dfs9(int u) {
int lst1 = tp1, lst2 = tp2;
for (int i : vx[u]) T.upd(a[i].y, Minp(sxy[i], col[i]));
for (int i : vx[u]) con[i] += T.qry(a[i].y) + -sxy[i];
for (int v : e[u]) dfs9(v);
while (tp1 > lst1) T.mx[stk1[tp1].second] = stk1[tp1].first, --tp1;
while (tp2 > lst2) T.w[stk2[tp2].second] = stk2[tp2].first, --tp2;
}
void solve() { dfs9(1); }
} // namespace Case4_3
} // namespace Case4
void boruvka() {
for (int i = 1; i <= m; ++i) con[i] = Msp();
Case1::solve();
Case2::solve();
Case3::solve();
Case4::Case4_1::solve();
Case4::Case4_2::solve();
Case4::Case4_3::solve();
for (int i = 1; i <= m; ++i) con[col[i]] += con[i];
Msp *j = con + 1;
for (int i = 1; i <= m; ++i, ++j) {
assert(j->mn.v >= 0);
if (i == col[i]) {
if (j->mn.p == i)
mg(i, j->se.p, j->se.v);
else
mg(i, j->mn.p, j->mn.v);
}
}
}
int main() {
#ifndef ONLINE_JUDGE
freopen(".in", "r", stdin);
freopen(".out", "w", stdout);
#endif
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> m;
for (int i = 2; i <= n; ++i) {
cin >> fa[i];
e[fa[i]].push_back(i);
}
for (int i = 1; i <= m; ++i) {
cin >> a[i].x >> a[i].y;
vx[a[i].x].push_back(i);
vy[a[i].y].push_back(i);
}
dfs(1);
for (int i = 1; i <= m; ++i) sxy[i] = siz[a[i].x] + siz[a[i].y];
iota(col + 1, col + 1 + m, 1);
int tot(0);
while (!is_merged()) boruvka();
cout << ans;
return 0;
}
Details
Subtask #1:
score: 0
Runtime Error
Test #1:
score: 0
Runtime Error
Subtask #2:
score: 0
Skipped
Dependency #1:
0%
Subtask #3:
score: 0
Skipped
Dependency #2:
0%
Subtask #4:
score: 0
Runtime Error
Test #16:
score: 0
Runtime Error
Subtask #5:
score: 0
Runtime Error
Test #21:
score: 0
Runtime Error
Subtask #6:
score: 0
Wrong Answer
Test #26:
score: 0
Wrong Answer
time: 955ms
memory: 458536kb
Subtask #7:
score: 0
Skipped
Dependency #1:
0%