QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#817152 | #4408. 燃烧的呐球 | hhoppitree | 100 ✓ | 7078ms | 871336kb | C++17 | 10.8kb | 2024-12-16 20:39:56 | 2024-12-16 20:39:56 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5, M = 1e5 + 5;
bool ST;
int n, m, fa[N], siz[N], dfn[N];
vector<int> G[N];
void preDfs(int x) {
dfn[x] = ++dfn[0];
for (auto v : G[x]) preDfs(v);
}
int ox[M], oy[M], wh[M];
vector<int> pnt[M];
int _fa[M];
int find(int x) {
return (_fa[x] == x ? x : _fa[x] = find(_fa[x]));
}
struct B_Info {
int val, pos;
B_Info(int _val = 1e9, int _pos = 0) {
val = _val, pos = _pos;
}
bool operator < (const B_Info y) const {
return (val != y.val ? val < y.val : pos < y.pos);
}
B_Info operator + (int x) {
return B_Info(val + x, pos);
}
} mn[N];
struct Info {
B_Info mn, sec;
Info() {
mn = sec = B_Info();
}
B_Info get(int x) {
return (x != mn.pos ? mn : sec);
}
void operator += (B_Info y) {
if (y.pos == mn.pos) {
mn = min(mn, y);
} else if (y < mn) {
sec = mn, mn = y;
} else {
sec = min(sec, y);
}
}
Info operator + (B_Info y) {
Info z = *this;
z += y;
return z;
}
void operator += (Info y) {
*this += y.mn;
*this += y.sec;
}
Info operator + (Info y) {
Info z = *this;
z += y;
return z;
}
};
namespace Solver1 {
vector<int> qr[N];
vector<B_Info> md[N];
Info dfs(int x) {
Info now;
for (auto v : md[x]) now += v;
for (auto v : G[x]) {
now += dfs(v);
}
for (auto v : qr[x]) {
mn[wh[v]] = min(mn[wh[v]], now.get(wh[v]) + siz[ox[v]] + siz[oy[v]]);
}
return now;
}
void main() {
for (int i = 1; i <= n; ++i) {
qr[i].clear();
md[i].clear();
}
for (int i = 1; i <= m; ++i) {
qr[oy[i]].push_back(i);
md[oy[i]].push_back(B_Info(siz[ox[i]] - siz[oy[i]], wh[i]));
}
dfs(1);
}
}
namespace Solver2 {
vector<int> qr[N];
vector<B_Info> md[N];
void dfs(int x, Info now) {
for (auto v : md[x]) now += v;
for (auto v : qr[x]) {
mn[wh[v]] = min(mn[wh[v]], now.get(wh[v]) + (siz[ox[v]] - siz[oy[v]]));
}
for (auto v : G[x]) {
dfs(v, now);
}
}
void main() {
for (int i = 1; i <= n; ++i) {
qr[i].clear();
md[i].clear();
}
for (int i = 1; i <= m; ++i) {
qr[oy[i]].push_back(i);
md[oy[i]].push_back(B_Info(siz[ox[i]] + siz[oy[i]], wh[i]));
}
dfs(1, Info());
}
}
struct SegmentTree {
struct Node {
int l, r;
Info dt;
} p[M * 40];
int tot;
int newNode() {
++tot;
p[tot].l = p[tot].r = 0;
p[tot].dt = Info();
return tot;
}
void modify(int &k, int l, int r, int x, B_Info y) {
if (!k) k = newNode();
p[k].dt += y;
if (l == r) return;
int mid = (l + r) >> 1;
if (x <= mid) modify(p[k].l, l, mid, x, y);
else modify(p[k].r, mid + 1, r, x, y);
}
int merge(int l, int r, int x, int y) {
if (!x || !y) return x + y;
p[x].dt = p[x].dt + p[y].dt;
if (l == r) return x;
int mid = (l + r) >> 1;
p[x].l = merge(l, mid, p[x].l, p[y].l);
p[x].r = merge(mid + 1, r, p[x].r, p[y].r);
return x;
}
Info query(int k, int l, int r, int x, int y) {
if (!k) return Info();
if (l >= x && r <= y) return p[k].dt;
int mid = (l + r) >> 1;
if (y <= mid) return query(p[k].l, l, mid, x, y);
if (x > mid) return query(p[k].r, mid + 1, r, x, y);
return query(p[k].l, l, mid, x, y) + query(p[k].r, mid + 1, r, x, y);
}
void Init() {
tot = 0;
}
};
namespace Solver3 {
vector<int> qr[N];
vector< pair<B_Info, int> > md[N];
SegmentTree seg;
int dfs(int x) {
int now = 0;
for (auto [v, w] : md[x]) {
seg.modify(now, 1, n, w, v);
}
for (auto v : G[x]) {
now = seg.merge(1, n, now, dfs(v));
}
for (auto v : qr[x]) {
mn[wh[v]] = min(mn[wh[v]], seg.query(now, 1, n, dfn[ox[v]], dfn[ox[v]] + siz[ox[v]] - 1).get(wh[v]) + siz[ox[v]] + siz[oy[v]]);
}
return now;
}
void main() {
for (int i = 1; i <= n; ++i) {
qr[i].clear();
md[i].clear();
}
for (int i = 1; i <= m; ++i) {
qr[oy[i]].push_back(i);
md[oy[i]].push_back({B_Info(-siz[ox[i]] - siz[oy[i]], wh[i]), dfn[ox[i]]});
}
seg.Init();
dfs(1);
}
}
struct PersistentSegmentTree {
struct Node {
int l, r;
Info dt;
} p[M * 40];
int tot;
int newNode() {
++tot;
p[tot].l = p[tot].r = 0;
p[tot].dt = Info();
return tot;
}
int clone(int x) {
int z = newNode();
p[z] = p[x];
return z;
}
void modify(int &k, int l, int r, int x, B_Info y) {
k = clone(k);
p[k].dt += y;
if (l == r) return;
int mid = (l + r) >> 1;
if (x <= mid) modify(p[k].l, l, mid, x, y);
else modify(p[k].r, mid + 1, r, x, y);
}
Info query(int k, int l, int r, int x, int y) {
if (!k) return Info();
if (l >= x && r <= y) return p[k].dt;
int mid = (l + r) >> 1;
if (y <= mid) return query(p[k].l, l, mid, x, y);
if (x > mid) return query(p[k].r, mid + 1, r, x, y);
return query(p[k].l, l, mid, x, y) + query(p[k].r, mid + 1, r, x, y);
}
void Init() {
tot = 0;
}
};
namespace Solver4 {
vector<int> qr[N];
vector< pair<B_Info, int> > md[N];
PersistentSegmentTree seg;
void dfs(int x, int now) {
for (auto [v, w] : md[x]) {
seg.modify(now, 1, n, w, v);
}
for (auto v : qr[x]) {
mn[wh[v]] = min(mn[wh[v]], seg.query(now, 1, n, dfn[ox[v]], dfn[ox[v]] + siz[ox[v]] - 1).get(wh[v]) + (siz[ox[v]] - siz[oy[v]]));
}
for (auto v : G[x]) {
dfs(v, now);
}
}
void main() {
for (int i = 1; i <= n; ++i) {
qr[i].clear();
md[i].clear();
}
for (int i = 1; i <= m; ++i) {
qr[oy[i]].push_back(i);
md[oy[i]].push_back({B_Info(-siz[ox[i]] + siz[oy[i]], wh[i]), dfn[ox[i]]});
}
seg.Init();
dfs(1, 0);
}
}
struct PersistentSegmentTree2 {
struct Node {
int l, r;
Info dt;
} p[M * 40];
int tot;
int newNode() {
++tot;
p[tot].l = p[tot].r = 0;
p[tot].dt = Info();
return tot;
}
int clone(int x) {
int z = newNode();
p[z] = p[x];
return z;
}
void modify(int &k, int l, int r, int x, int y, B_Info v) {
if (l > y || r < x) return;
k = clone(k);
if (l >= x && r <= y) {
p[k].dt += v;
return;
}
int mid = (l + r) >> 1;
modify(p[k].l, l, mid, x, y, v);
modify(p[k].r, mid + 1, r, x, y, v);
}
Info query(int k, int l, int r, int x) {
if (!k) return Info();
if (l == r) return p[k].dt;
int mid = (l + r) >> 1;
if (x <= mid) {
return query(p[k].l, l, mid, x) + p[k].dt;
}
return query(p[k].r, mid + 1, r, x) + p[k].dt;
}
void Init() {
tot = 0;
}
};
namespace Solver5 {
vector<int> qr[N];
vector< pair<B_Info, pair<int, int> > > md[N];
PersistentSegmentTree2 seg;
void dfs(int x, int now) {
for (auto [v, w] : md[x]) {
seg.modify(now, 1, n, w.first, w.second, v);
}
for (auto v : qr[x]) {
mn[wh[v]] = min(mn[wh[v]], seg.query(now, 1, n, dfn[ox[v]]).get(wh[v]) + (-siz[ox[v]] - siz[oy[v]]));
}
for (auto v : G[x]) {
dfs(v, now);
}
}
void main() {
for (int i = 1; i <= n; ++i) {
qr[i].clear();
md[i].clear();
}
for (int i = 1; i <= m; ++i) {
qr[oy[i]].push_back(i);
md[oy[i]].push_back({B_Info(siz[ox[i]] + siz[oy[i]], wh[i]), {dfn[ox[i]], dfn[ox[i]] + siz[ox[i]] - 1}});
}
seg.Init();
dfs(1, 0);
}
}
void NN() {
Info now;
for (int i = 1; i <= m; ++i) {
now += B_Info(siz[ox[i]] + siz[oy[i]], wh[i]);
}
for (int i = 1; i <= m; ++i) {
mn[wh[i]] = min(mn[wh[i]], now.get(wh[i]) + siz[ox[i]] + siz[oy[i]]);
}
}
void NA() {
Solver1::main();
}
void ND() {
Solver2::main();
}
void AN() {
for (int i = 1; i <= m; ++i) swap(ox[i], oy[i]);
NA();
for (int i = 1; i <= m; ++i) swap(ox[i], oy[i]);
}
void AA() {
Solver3::main();
}
void AD() {
Solver4::main();
}
void DN() {
for (int i = 1; i <= m; ++i) swap(ox[i], oy[i]);
ND();
for (int i = 1; i <= m; ++i) swap(ox[i], oy[i]);
}
void DA() {
for (int i = 1; i <= m; ++i) swap(ox[i], oy[i]);
AD();
for (int i = 1; i <= m; ++i) swap(ox[i], oy[i]);
}
void DD() {
Solver5::main();
}
bool ED;
signed main() {
cerr << abs(&ED - &ST) / 1024.0 / 1024.0 << "MB" << endl;
scanf("%d%d", &n, &m);
for (int i = 2; i <= n; ++i) {
scanf("%d", &fa[i]);
}
for (int i = n; i >= 1; --i) {
++siz[i];
if (i != 1) {
siz[fa[i]] += siz[i];
G[fa[i]].push_back(i);
}
}
preDfs(1);
for (int i = 1; i <= m; ++i) {
scanf("%d%d", &ox[i], &oy[i]);
wh[i] = i;
pnt[i].push_back(i);
}
long long res = 0;
while (count(wh + 1, wh + m + 1, wh[1]) != m) {
for (int i = 1; i <= m; ++i) mn[i] = B_Info();
NN(), NA(), ND(), AN(), AA(), AD(), DN(), DA(), DD();
map< pair<int, int>, int> E;
for (int i = 1; i <= m; ++i) {
if (pnt[i].empty()) continue;
_fa[i] = i;
int x = i, y = mn[i].pos;
if (x > y) swap(x, y);
E[{x, y}] = mn[i].val;
}
for (auto [x, y] : E) {
auto [a, b] = x;
a = find(a), b = find(b);
if (a == b) continue;
res += y;
if (pnt[a].size() < pnt[b].size()) swap(a, b);
for (auto v : pnt[b]) {
pnt[a].push_back(v), wh[v] = a;
}
pnt[b].clear(), _fa[b] = a;
}
}
printf("%lld\n", res);
return 0;
}
Details
Subtask #1:
score: 10
Accepted
Test #1:
score: 10
Accepted
time: 68ms
memory: 557948kb
Test #2:
score: 10
Accepted
time: 47ms
memory: 558544kb
Test #3:
score: 10
Accepted
time: 62ms
memory: 557776kb
Test #4:
score: 10
Accepted
time: 48ms
memory: 557352kb
Test #5:
score: 10
Accepted
time: 68ms
memory: 557704kb
Subtask #2:
score: 10
Accepted
Dependency #1:
100%
Accepted
Test #6:
score: 10
Accepted
time: 3869ms
memory: 598868kb
Test #7:
score: 10
Accepted
time: 1880ms
memory: 596556kb
Test #8:
score: 10
Accepted
time: 979ms
memory: 590228kb
Test #9:
score: 10
Accepted
time: 1087ms
memory: 594652kb
Test #10:
score: 10
Accepted
time: 1471ms
memory: 594396kb
Subtask #3:
score: 10
Accepted
Dependency #2:
100%
Accepted
Test #11:
score: 10
Accepted
time: 5337ms
memory: 615504kb
Test #12:
score: 10
Accepted
time: 3052ms
memory: 613396kb
Test #13:
score: 10
Accepted
time: 1706ms
memory: 607548kb
Test #14:
score: 10
Accepted
time: 1875ms
memory: 611856kb
Test #15:
score: 10
Accepted
time: 2460ms
memory: 611296kb
Subtask #4:
score: 20
Accepted
Test #16:
score: 20
Accepted
time: 370ms
memory: 577904kb
Test #17:
score: 20
Accepted
time: 410ms
memory: 577588kb
Test #18:
score: 20
Accepted
time: 328ms
memory: 579220kb
Test #19:
score: 20
Accepted
time: 352ms
memory: 578084kb
Test #20:
score: 20
Accepted
time: 337ms
memory: 576824kb
Subtask #5:
score: 10
Accepted
Test #21:
score: 10
Accepted
time: 6803ms
memory: 871336kb
Test #22:
score: 10
Accepted
time: 6773ms
memory: 871280kb
Test #23:
score: 10
Accepted
time: 6886ms
memory: 871188kb
Test #24:
score: 10
Accepted
time: 6866ms
memory: 871156kb
Test #25:
score: 10
Accepted
time: 7078ms
memory: 871184kb
Subtask #6:
score: 10
Accepted
Test #26:
score: 10
Accepted
time: 1489ms
memory: 625868kb
Test #27:
score: 10
Accepted
time: 1516ms
memory: 625580kb
Test #28:
score: 10
Accepted
time: 1486ms
memory: 625576kb
Test #29:
score: 10
Accepted
time: 1449ms
memory: 625692kb
Test #30:
score: 10
Accepted
time: 1480ms
memory: 625444kb
Subtask #7:
score: 30
Accepted
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Dependency #3:
100%
Accepted
Dependency #4:
100%
Accepted
Dependency #5:
100%
Accepted
Dependency #6:
100%
Accepted
Test #31:
score: 30
Accepted
time: 6699ms
memory: 641940kb
Test #32:
score: 30
Accepted
time: 3781ms
memory: 639828kb
Test #33:
score: 30
Accepted
time: 2392ms
memory: 634192kb
Test #34:
score: 30
Accepted
time: 2605ms
memory: 638660kb
Test #35:
score: 30
Accepted
time: 3183ms
memory: 637740kb
Test #36:
score: 30
Accepted
time: 6871ms
memory: 641772kb
Test #37:
score: 30
Accepted
time: 3883ms
memory: 639780kb
Test #38:
score: 30
Accepted
time: 2494ms
memory: 634020kb
Test #39:
score: 30
Accepted
time: 2659ms
memory: 638628kb
Test #40:
score: 30
Accepted
time: 3143ms
memory: 637764kb