QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#884085 | #4408. 燃烧的呐球 | TrueFalse | 0 | 77ms | 257204kb | C++14 | 7.9kb | 2025-02-05 21:15:45 | 2025-02-05 21:15:46 |
Judging History
answer
/**
* @author TrueFalse
* @details 抽象的闭环传递
*/
#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 = 1 << 30;
const int bf_sz = 10 << 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[N]; // 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;
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]);
}
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; }
void pushup() { v = ch[0]->v + ch[1]->v; }
} *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, dfn[a[i].y], dfn[a[i].y] + siz[a[i].y] - 1) + 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 << 1];
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) {
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, dfn[a[i].y], dfn[a[i].y] + siz[a[i].y] - 1) +
(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) {
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, dfn[a[i].x], dfn[a[i].x] + siz[a[i].x] - 1) +
(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 {
void solve() {}
} // 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)
if (i != col[i]) con[col[i]] += con[i];
Msp *j = con + 1;
for (int i = 1; i <= m; ++i, ++j) {
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;
}
详细
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 35ms
memory: 249816kb
Subtask #2:
score: 0
Skipped
Dependency #1:
0%
Subtask #3:
score: 0
Skipped
Dependency #2:
0%
Subtask #4:
score: 0
Wrong Answer
Test #16:
score: 0
Wrong Answer
time: 77ms
memory: 257204kb
Subtask #5:
score: 0
Runtime Error
Test #21:
score: 0
Runtime Error
Subtask #6:
score: 0
Runtime Error
Test #26:
score: 0
Runtime Error
Subtask #7:
score: 0
Skipped
Dependency #1:
0%