QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#883813 | #4408. 燃烧的呐球 | TrueFalse | 40 | 8056ms | 811564kb | C++14 | 8.5kb | 2025-02-05 19:06:43 | 2025-02-05 19:06:43 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e6 + 5, MAXM = 1e5 + 5, inf = 1e9;
vector<int> G[MAXN], qx[MAXN], qy[MAXN];
int fa[MAXN], siz[MAXN], id[MAXN], dcnt, L[MAXN], R[MAXN];
int n, m, col[MAXN], X[MAXN], Y[MAXN];
vector<int> dfn, rdfn, eul;
long long ans = 0;
inline void dfs(int u) {
L[u] = id[u] = ++dcnt, siz[u] = 1;
dfn.push_back(u), eul.push_back(u);
for (int v : G[u]) dfs(v), siz[u] += siz[v];
R[u] = dcnt;
rdfn.push_back(u), eul.push_back(-u);
}
struct E {
int v, w;
E(int x = 0, int c = inf) : v(x), w(c) {}
inline friend bool operator==(E x, E y) { return x.v == y.v; }
inline friend bool operator<(E x, E y) { return x.w < y.w; }
};
struct I {
E mn1, mn2;
I(int x = 0, int c = inf) : mn1(x, c), mn2(0, inf) {}
inline I operator+=(I oth) {
if (oth.mn1 < mn1) swap(oth.mn1, mn1), swap(oth.mn2, mn2);
mn2 = min(mn2, oth.mn1 == mn1 ? oth.mn2 : oth.mn1);
return *this;
}
inline I operator+=(int oth) {
mn1.w += oth, mn2.w += oth;
return *this;
}
inline I operator+(I oth) const {
I tmp(*this);
return tmp += oth;
}
inline I operator+(int oth) const {
I tmp(*this);
return tmp += oth;
}
};
struct D {
int id;
I val;
D(int i = 0, I v = I()) : id(i), val(v) {}
};
I r[MAXN];
namespace Case1 { // out,out
inline void main() {
I now;
for (int i = 1; i <= m; ++i) now += I(col[i], siz[X[i]] + siz[Y[i]]);
for (int i = 1; i <= m; ++i) r[i] += now + (siz[X[i]] + siz[Y[i]]);
}
} // namespace Case1
namespace Case2 { // son,out
I minx[MAXN], miny[MAXN];
inline void main() {
for (int i = 1; i <= n; ++i) minx[i] = miny[i] = I();
for (int u : rdfn) {
for (int i : qx[u]) minx[u] += I(col[i], siz[Y[i]] - siz[X[i]]);
for (int i : qy[u]) miny[u] += I(col[i], siz[X[i]] - siz[Y[i]]);
for (int v : G[u]) minx[u] += minx[v], miny[u] += miny[v];
for (int i : qx[u]) r[i] += minx[u] + (siz[Y[i]] + siz[X[i]]);
for (int i : qy[u]) r[i] += miny[u] + (siz[X[i]] + siz[Y[i]]);
}
}
} // namespace Case2
namespace Case3 { // fa,out
inline void dfs2(int u, I minx) {
for (int i : qx[u]) minx += I(col[i], siz[X[i]] + siz[Y[i]]);
for (int i : qx[u]) r[i] += minx + (siz[Y[i]] - siz[X[i]]);
for (int v : G[u]) dfs2(v, minx);
}
inline void dfs3(int u, I miny) {
for (int i : qy[u]) miny += I(col[i], siz[Y[i]] + siz[X[i]]);
for (int i : qy[u]) r[i] += miny + (siz[X[i]] - siz[Y[i]]);
for (int v : G[u]) dfs3(v, miny);
}
inline void main() { dfs2(1, I()), dfs3(1, I()); }
} // namespace Case3
namespace Case4 { // son son
struct SegmentTree {
struct Node {
int ls, rs;
I min;
} tr[MAXM * 32];
int tot;
inline void init() { tot = 0; }
inline void ins(int u, I k, int l, int r, int &p) {
if (!p) tr[p = ++tot] = {0, 0, I()};
tr[p].min += k;
if (l == r) return;
int mid = (l + r) >> 1;
if (u <= mid)
ins(u, k, l, mid, tr[p].ls);
else
ins(u, k, mid + 1, r, tr[p].rs);
}
inline I qry(int ul, int ur, int l, int r, int p) {
if (!p || ul > ur) return I();
if (ul <= l && r <= ur) return tr[p].min;
int mid = (l + r) >> 1;
if (ur <= mid) return qry(ul, ur, l, mid, tr[p].ls);
if (mid < ul) return qry(ul, ur, mid + 1, r, tr[p].rs);
return qry(ul, ur, l, mid, tr[p].ls) + qry(ul, ur, mid + 1, r, tr[p].rs);
}
inline void merge(int l, int r, int q, int &p) {
if (!p || !q) return p += q, void();
tr[p].min += tr[q].min;
if (l == r) return;
int mid = (l + r) >> 1;
merge(l, mid, tr[q].ls, tr[p].ls), merge(mid + 1, r, tr[q].rs, tr[p].rs);
}
} T;
int rt[MAXN];
inline void dfs4(int u) {
for (int i : qx[u])
T.ins(id[Y[i]], I(col[i], -siz[X[i]] - siz[Y[i]]), 1, n, rt[u]);
for (int v : G[u]) dfs4(v), T.merge(1, n, rt[v], rt[u]);
for (int i : qx[u])
r[i] += T.qry(L[Y[i]], R[Y[i]], 1, n, rt[u]) + (siz[X[i]] + siz[Y[i]]);
}
inline void main() {
T.init();
for (int i = 1; i <= n; ++i) rt[i] = 0;
dfs4(1);
}
} // namespace Case4
namespace Case5 { // fa,son
D stk[MAXM * 32];
int tp;
struct SegmentTree {
static const int N = 1 << 20;
I tr[N << 1];
inline void upd(int x, I z) {
x += N, stk[++tp] = D(x, tr[x]), tr[x] += z;
for (x >>= 1; x; x >>= 1) stk[++tp] = D(x, tr[x]), tr[x] += z;
}
inline I qry(int l, int r) {
I g = I();
for (l += N - 1, r += N + 1; l ^ r ^ 1; l >>= 1, r >>= 1) {
if (!(l & 1)) g += tr[l ^ 1];
if (r & 1) g += tr[r ^ 1];
}
return g;
}
} T;
inline void dfs5(int u) {
int lst = tp;
for (int i : qx[u]) T.upd(id[Y[i]], I(col[i], siz[X[i]] - siz[Y[i]]));
for (int i : qx[u]) r[i] += T.qry(L[Y[i]], R[Y[i]]) + (siz[Y[i]] - siz[X[i]]);
for (int v : G[u]) dfs5(v);
while (tp > lst) T.tr[stk[tp].id] = stk[tp].val, --tp;
}
inline void dfs6(int u) {
int lst = tp;
for (int i : qy[u]) T.upd(id[X[i]], I(col[i], siz[Y[i]] - siz[X[i]]));
for (int i : qy[u]) r[i] += T.qry(L[X[i]], R[X[i]]) + (siz[X[i]] - siz[Y[i]]);
for (int v : G[u]) dfs6(v);
while (tp > lst) T.tr[stk[tp].id] = stk[tp].val, --tp;
}
inline void main() { dfs5(1), dfs6(1); }
} // namespace Case5
namespace Case6 { // fa,fa
int siz[MAXN], hson[MAXN], top[MAXN];
inline void dfs7(int u) {
siz[u] = 1;
for (int v : G[u]) {
dfs7(v), siz[u] += siz[v];
if (siz[v] > siz[hson[u]]) hson[u] = v;
}
}
inline void dfs8(int u, int rt) {
top[u] = rt;
if (hson[u]) dfs8(hson[u], rt);
for (int v : G[u])
if (v ^ hson[u]) dfs8(v, v);
}
D stk1[MAXM * 32], stk2[MAXM];
int tp1, tp2;
struct BalanceTree {
int ls[MAXN], rs[MAXN], f[MAXN];
I w[MAXN], mx[MAXN];
inline void build() {
for (int s = 1; s <= n; ++s)
if (top[s] == s) {
vector<int> ci;
for (int u = s; u; u = hson[u]) ci.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[ci[i]] - siz[hson[ci[i]]];
for (int i = x; i <= y; ++i) {
tsiz += siz[ci[i]] - siz[hson[ci[i]]];
if (tsiz > all / 2) {
int p = ci[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, ci.size() - 1)] = fa[s];
}
}
inline void upd(int x, I z) {
stk2[++tp2] = D(x, w[x]), w[x] += z;
for (; x; x = f[x]) {
stk1[++tp1] = D(x, mx[x]), mx[x] += z;
if (x != ls[f[x]] && x != rs[f[x]]) break;
}
}
inline I qry(int x) {
I 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 : qx[u]) T.upd(Y[i], I(col[i], siz[X[i]] + siz[Y[i]]));
for (int i : qx[u]) r[i] += T.qry(Y[i]) + (-siz[X[i]] - siz[Y[i]]);
for (int v : G[u]) dfs9(v);
while (tp1 > lst1) T.mx[stk1[tp1].id] = stk1[tp1].val, --tp1;
while (tp2 > lst2) T.w[stk2[tp2].id] = stk2[tp2].val, --tp2;
}
inline void main() { dfs9(1); }
} // namespace Case6
inline int find(int x) {
while (x ^ col[x]) x = col[x] = col[col[x]];
return x;
}
inline void boruvka() {
for (int i = 1; i <= m; ++i) r[i] = I();
Case1::main(), Case2::main();
// Case3::main();
Case4::main(), Case5::main(), Case6::main();
vector<array<int, 3>> cur;
for (int i = 1; i <= m; ++i)
if (i ^ col[i]) r[col[i]] += r[i];
for (int i = 1; i <= m; ++i)
if (i == col[i]) {
E e = (r[i].mn1.v == col[i]) ? r[i].mn2 : r[i].mn1;
cur.push_back({i, e.v, e.w});
}
for (auto i : cur)
if (find(i[0]) ^ find(i[1])) col[find(i[0])] = find(i[1]), ans += i[2];
}
inline bool judge() {
int cnt = 0;
for (int i = 1; i <= m; ++i) col[i] = find(i), cnt += (i == col[i]);
return cnt > 1;
}
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], G[fa[i]].push_back(i);
dfs(1);
Case6::init();
for (int i = 1; i <= m; ++i) {
cin >> X[i] >> Y[i];
col[i] = i;
qx[X[i]].push_back(i);
qy[Y[i]].push_back(i);
}
while (judge()) boruvka();
printf("%lld\n", ans);
return 0;
}
Details
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 42ms
memory: 391380kb
Subtask #2:
score: 0
Skipped
Dependency #1:
0%
Subtask #3:
score: 0
Skipped
Dependency #2:
0%
Subtask #4:
score: 20
Accepted
Test #16:
score: 20
Accepted
time: 230ms
memory: 395496kb
Test #17:
score: 20
Accepted
time: 256ms
memory: 397804kb
Test #18:
score: 20
Accepted
time: 150ms
memory: 394252kb
Test #19:
score: 20
Accepted
time: 186ms
memory: 394992kb
Test #20:
score: 20
Accepted
time: 189ms
memory: 394936kb
Subtask #5:
score: 10
Accepted
Test #21:
score: 10
Accepted
time: 7518ms
memory: 803832kb
Test #22:
score: 10
Accepted
time: 7672ms
memory: 803720kb
Test #23:
score: 10
Accepted
time: 7395ms
memory: 803816kb
Test #24:
score: 10
Accepted
time: 7725ms
memory: 802924kb
Test #25:
score: 10
Accepted
time: 8056ms
memory: 811564kb
Subtask #6:
score: 10
Accepted
Test #26:
score: 10
Accepted
time: 1162ms
memory: 465896kb
Test #27:
score: 10
Accepted
time: 1352ms
memory: 465444kb
Test #28:
score: 10
Accepted
time: 1153ms
memory: 465136kb
Test #29:
score: 10
Accepted
time: 1480ms
memory: 466164kb
Test #30:
score: 10
Accepted
time: 1262ms
memory: 465032kb
Subtask #7:
score: 0
Skipped
Dependency #1:
0%