QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#864911 | #4408. 燃烧的呐球 | 1234567890 | 100 ✓ | 6339ms | 925824kb | C++14 | 13.1kb | 2025-01-21 11:08:51 | 2025-01-21 11:08:53 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define ll int
#define mp make_pair
#define inf (ll)1e9
#define pii pair <ll, ll>
#define fr first
#define se second
const ll mod = 1e9 + 7;
char buf[1 << 21], *p1 = buf, *p2 = buf;
#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 18, stdin), p1 == p2) ? EOF : *p1++)
inline ll read() {
ll x = 0, f = 1;
char ch = getchar();
while(ch < '0' || ch > '9') f = ((ch == '-') ? -1 : f), ch = getchar();
while(ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
return x * f;
}
inline void write(long long x) {
if(x < 0) x = -x, putchar('-');
if(x >= 10) write(x / 10);
putchar(x % 10 + '0');
}
long long Ans;
ll n, m, Rtt;
ll Fa[1000005], siz[1000005];
vector <ll> G[1000005], V0[1000005], V1[1000005];
struct Pa {
ll x, y;
}p[100005];
ll dfn[1000005], pos[1000005], posr[1000005], son[1000005], tot;
ll dfn2[2000005], tag[1000005], tagx[1000005], tagy[1000005], ttot;
inline void dfs(ll x) {
dfn2[++ttot] = x;
dfn[++tot] = x, pos[x] = tot;
siz[x] = 1;
for(auto y : G[x]) {
dfs(y);
siz[x] += siz[y];
if(siz[y] > siz[son[x]]) son[x] = y;
}
posr[x] = tot;
dfn2[++ttot] = x;
}
struct UnionSet {
ll fa[100005];
inline void makeSet(ll x) {
for(ll i = 1; i <= x; i++) fa[i] = i;
}
inline ll findSet(ll x) {
if(x == fa[x]) return x;
return fa[x] = findSet(fa[x]);
}
inline void unionSet(ll x, ll y) {
x = findSet(x), y = findSet(y);
if(x == y) return ;
fa[x] = y;
}
}U;
inline bool chk() {
for(ll i = 2; i <= m; i++) if(U.findSet(i) != U.findSet(1)) return 1;
return 0;
}
pii lk[1000005];
inline void Mn(ll i, ll j, ll val) {
if(U.findSet(i) == U.findSet(j) || !j) return ;
if(val < lk[i].fr) lk[i].fr = val, lk[i].se = j;
}
inline void upd(pii &mn, pii &mnse, ll val, ll i) {
if(!i) return ;
if(val < mn.fr) {
if(U.findSet(i) != U.findSet(mn.se)) mnse = mn;
mn = mp(val, i);
}
else if(U.findSet(i) != U.findSet(mn.se) && val < mnse.fr) mnse = mp(val, i);
}
struct BST {
#define ls(x) sn[x][0]
#define rs(x) sn[x][1]
ll sn[1000005][2], fa[1000005], lsiz[1000005];
pii amn[1000005], amnse[1000005];
pii mn[1000005], mnse[1000005];
ll sta[4000005], top;
pii tmpmn[4000005], tmpmnse[4000005];
pii tmpamn[4000005], tmpamnse[4000005];
inline ll buildline(ll l, ll r) {
if(l > r) return 0;
if(l == r) return sta[l];
ll ssiz = 0, cnt = 0;
for(ll i = l; i <= r; i++) ssiz += lsiz[sta[i]];
for(ll i = l; i <= r; i++) {
cnt += lsiz[sta[i]];
if(2 * cnt >= ssiz) {
ll lson = buildline(l, i - 1), rson = buildline(i + 1, r);
fa[lson] = fa[rson] = sta[i];
ls(sta[i]) = lson, rs(sta[i]) = rson;
return sta[i];
}
}
return 0;
}
inline ll build(ll x) {
for(ll i = x; i; i = son[i]) lsiz[i] = siz[i] - siz[son[i]];
for(ll i = x; i; i = son[i]) {
for(auto y : G[i]) {
if(!lsiz[y]) {
ll Son = build(y);
fa[Son] = i;
}
}
}
top = 0;
for(ll i = x; i; i = son[i]) sta[++top] = i;
return buildline(1, top);
}
inline ll isson(ll x) {
return (ls(fa[x]) == x || rs(fa[x]) == x);
}
inline void Save(ll x) {
sta[++top] = x, tmpmn[top] = mn[x], tmpmnse[top] = mnse[x], tmpamn[top] = amn[x], tmpamnse[top] = amnse[x];
}
inline void Insert(ll x, ll val, ll id) {
Save(x);
upd(amn[x], amnse[x], val, id);
upd(mn[x], mnse[x], val, id);
for(ll i = x; i; i = fa[i]) {
if(!fa[i] || !isson(i)) return ;
Save(fa[i]);
upd(mn[fa[i]], mnse[fa[i]], mn[i].fr, mn[i].se);
upd(mn[fa[i]], mnse[fa[i]], mnse[i].fr, mnse[i].se);
}
}
pii Mn, Mnse;
inline void Get_ans(ll x) {
Mn = Mnse = mp(inf, 0);
upd(Mn, Mnse, amn[x].fr, amn[x].se);
upd(Mn, Mnse, amnse[x].fr, amnse[x].se);
if(ls(x)) {
upd(Mn, Mnse, mn[ls(x)].fr, mn[ls(x)].se);
upd(Mn, Mnse, mnse[ls(x)].fr, mnse[ls(x)].se);
}
for(ll i = x; i; i = fa[i]) {
if(fa[i] && i != ls(fa[i])) {
upd(Mn, Mnse, amn[fa[i]].fr, amn[fa[i]].se);
upd(Mn, Mnse, amnse[fa[i]].fr, amnse[fa[i]].se);
if(ls(fa[i])) {
upd(Mn, Mnse, mn[ls(fa[i])].fr, mn[ls(fa[i])].se);
upd(Mn, Mnse, mnse[ls(fa[i])].fr, mnse[ls(fa[i])].se);
}
}
}
}
inline void Back(ll x) {
while(top > x) {
mn[sta[top]] = tmpmn[top], mnse[sta[top]] = tmpmnse[top];
amn[sta[top]] = tmpamn[top], amnse[sta[top]] = tmpamnse[top];
top--;
}
}
}BT;
namespace Sub1 {
pii mn, mnse;
inline void init() {
mn = mnse = mp(inf, 0);
for(ll i = 1; i <= m; i++) {
ll val = siz[p[i].x] + siz[p[i].y];
upd(mn, mnse, val, i);
}
}
inline void solve() {
for(ll i = 1; i <= m; i++) {
Mn(i, mn.se, siz[p[i].x] + siz[p[i].y] + mn.fr);
Mn(i, mnse.se, siz[p[i].x] + siz[p[i].y] + mnse.fr);
}
}
};
//+xi+yi +xj+yj
namespace Sub2 {
pii mnx[1000005], mnsex[1000005];
pii mny[1000005], mnsey[1000005];
inline void init() {
for(ll t = n; t >= 1; t--) {
ll x = dfn[t];
mnx[x] = mnsex[x] = mp(inf, 0);
mny[x] = mnsey[x] = mp(inf, 0);
for(auto i : V0[x]) upd(mnx[x], mnsex[x], -siz[p[i].x] + siz[p[i].y], i);
for(auto i : V1[x]) upd(mny[x], mnsey[x], siz[p[i].x] - siz[p[i].y], i);
for(auto y : G[x]) {
upd(mnx[x], mnsex[x], mnx[y].fr, mnx[y].se);
upd(mnx[x], mnsex[x], mnsex[y].fr, mnsex[y].se);
upd(mny[x], mnsey[x], mny[y].fr, mny[y].se);
upd(mny[x], mnsey[x], mnsey[y].fr, mnsey[y].se);
}
}
}
inline void solve() {
for(ll t = 1; t <= n; t++) {
ll x = dfn[t];
for(auto i : V0[x]) {
Mn(i, mnx[x].se, mnx[x].fr + siz[p[i].x] + siz[p[i].y]);
Mn(i, mnsex[x].se, mnsex[x].fr + siz[p[i].x] + siz[p[i].y]);
}
for(auto i : V1[x]) {
Mn(i, mny[x].se, mny[x].fr + siz[p[i].x] + siz[p[i].y]);
Mn(i, mnsey[x].se, mnsey[x].fr + siz[p[i].x] + siz[p[i].y]);
}
}
}
};
//+xi+yi -xj+yj
//+xi+yi +xj-yj
namespace Sub3 {
pii mnx[1000005], mnsex[1000005];
pii mny[1000005], mnsey[1000005];
ll cntx, cnty;
inline void init() {
cntx = cnty = 0;
mnx[0] = mnsex[0] = mny[0] = mnsey[0] = mp(inf, 0);
}
inline void solve() {
for(ll t = 1; t <= 2 * n; t++) {
ll x = dfn2[t];
if(!tag[x]) {
tag[x] = 1;
cntx++, cnty++;
mnx[cntx] = mnx[cntx-1], mnsex[cntx] = mnsex[cntx-1];
mny[cnty] = mny[cnty-1], mnsey[cnty] = mnsey[cnty-1];
for(auto i : V0[x]) upd(mnx[cntx], mnsex[cntx], siz[p[i].x] + siz[p[i].y], i);
for(auto i : V1[x]) upd(mny[cnty], mnsey[cnty], siz[p[i].x] + siz[p[i].y], i);
for(auto i : V0[x]) {
Mn(i, mnx[cntx].se, mnx[cntx].fr - siz[p[i].x] + siz[p[i].y]);
Mn(i, mnsex[cntx].se, mnsex[cntx].fr - siz[p[i].x] + siz[p[i].y]);
}
for(auto i : V1[x]) {
Mn(i, mny[cnty].se, mny[cnty].fr + siz[p[i].x] - siz[p[i].y]);
Mn(i, mnsey[cnty].se, mnsey[cnty].fr + siz[p[i].x] - siz[p[i].y]);
}
}
else tag[x] = 0, cntx--, cnty--;
}
}
};
//-xi+yi +xj+yj
//+xi-yi +xj+yj
namespace Sub4 {
struct Seg_Tree {
ll sta[4000005], top;
struct st {
ll l, r;
pii mn, mnse;
}t[4000005], lst[4000005];
inline void Back(ll x) {
while(top > x) t[sta[top]] = lst[top], top--;
}
inline void build(ll id, ll l, ll r) {
t[id].l = l, t[id].r = r;
t[id].mn = t[id].mnse = mp(inf, 0);
if(l == r) return ;
ll mid = (l + r) >> 1;
build(id << 1, l, mid);
build(id << 1 | 1, mid + 1, r);
}
inline void push_up(ll id) {
t[id].mn = t[id << 1].mn, t[id].mnse = t[id << 1].mnse;
upd(t[id].mn, t[id].mnse, t[id << 1 | 1].mn.fr, t[id << 1 | 1].mn.se);
upd(t[id].mn, t[id].mnse, t[id << 1 | 1].mnse.fr, t[id << 1 | 1].mnse.se);
}
inline void update(ll id, ll x, ll val, ll i) {
sta[++top] = id, lst[top] = t[id];
if(t[id].l == t[id].r) {
upd(t[id].mn, t[id].mnse, val, i);
return ;
}
ll mid = (t[id].l + t[id].r) / 2;
if(x <= mid) update(id << 1, x, val, i);
else update(id << 1 | 1, x, val, i);
push_up(id);
}
pii mn, mnse;
inline void get_ans(ll id, ll L, ll R) {
if(L <= t[id].l && t[id].r <= R) {
upd(mn, mnse, t[id].mn.fr, t[id].mn.se);
upd(mn, mnse, t[id].mnse.fr, t[id].mnse.se);
return ;
}
ll mid = (t[id].l + t[id].r) >> 1;
if(L <= mid) get_ans(id << 1, L, R);
if(R > mid) get_ans(id << 1 | 1, L, R);
}
inline void Get_ans(ll L, ll R) {
mn = mnse = mp(inf, 0);
get_ans(1, L, R);
}
}Tx, Ty;
inline void init() {
Tx.build(1, 1, n), Ty.build(1, 1, n);
}
inline void solve() {
for(ll t = 1; t <= 2 * n; t++) {
ll x = dfn2[t];
if(!tag[x]) {
tag[x] = 1, tagx[x] = Tx.top, tagy[x] = Ty.top;
for(auto i : V0[x]) Tx.update(1, pos[p[i].y], siz[p[i].x] - siz[p[i].y], i);
for(auto i : V1[x]) Ty.update(1, pos[p[i].x], -siz[p[i].x] + siz[p[i].y], i);
for(auto i : V0[x]) {
Tx.Get_ans(pos[p[i].y], posr[p[i].y]);
Mn(i, Tx.mn.se, Tx.mn.fr - siz[p[i].x] + siz[p[i].y]);
Mn(i, Tx.mnse.se, Tx.mnse.fr - siz[p[i].x] + siz[p[i].y]);
}
for(auto i : V1[x]) {
Ty.Get_ans(pos[p[i].x], posr[p[i].x]);
Mn(i, Ty.mn.se, Ty.mn.fr + siz[p[i].x] - siz[p[i].y]);
Mn(i, Ty.mnse.se, Ty.mnse.fr + siz[p[i].x] - siz[p[i].y]);
}
}
else tag[x] = 0, Tx.Back(tagx[x]), Ty.Back(tagy[x]);
}
}
};
//-xi+yi +xj-yj
//+xi-yi -xj+yj
namespace Sub5 {
ll rt[1000005];
struct Seg_Tree {
struct st {
ll l, r;
pii mn, mnse;
}t[4000005];
ll cnt;
inline void push_up(ll id) {
if(!t[id].l) t[id].mn = t[t[id].r].mn, t[id].mnse = t[t[id].r].mnse;
else {
t[id].mn = t[t[id].l].mn, t[id].mnse = t[t[id].l].mnse;
if(t[id].r) {
upd(t[id].mn, t[id].mnse, t[t[id].r].mn.fr, t[t[id].r].mn.se);
upd(t[id].mn, t[id].mnse, t[t[id].r].mnse.fr, t[t[id].r].mnse.se);
}
}
}
pii mn, mnse;
inline void insert(ll &id, ll l, ll r, ll x, ll val, ll i) {
if(!id) id = ++cnt, t[id].mn = t[id].mnse = mp(inf, 0), t[id].l = t[id].r = 0;
if(l == r) {
upd(t[id].mn, t[id].mnse, val, i);
return ;
}
ll mid = (l + r) >> 1;
if(x <= mid) insert(t[id].l, l, mid, x, val, i);
else insert(t[id].r, mid + 1, r, x, val, i);
push_up(id);
}
inline ll Merge(ll u, ll v, ll l, ll r) {
if(!u || !v) return u + v;
if(l == r) {
upd(t[u].mn, t[u].mnse, t[v].mn.fr, t[v].mn.se);
upd(t[u].mn, t[u].mnse, t[v].mnse.fr, t[v].mnse.se);
return u;
}
ll mid = (l + r) >> 1;
t[u].l = Merge(t[u].l, t[v].l, l, mid);
t[u].r = Merge(t[u].r, t[v].r, mid + 1, r);
push_up(u);
return u;
}
inline void get_ans(ll id, ll l, ll r, ll L, ll R) {
if(!id) return ;
if(L <= l && r <= R) {
upd(mn, mnse, t[id].mn.fr, t[id].mn.se);
upd(mn, mnse, t[id].mnse.fr, t[id].mnse.se);
return ;
}
ll mid = (l + r) >> 1;
if(L <= mid) get_ans(t[id].l, l, mid, L, R);
if(R > mid) get_ans(t[id].r, mid + 1, r, L, R);
}
inline void Get_ans(ll Rt, ll L, ll R) {
mn = mnse = mp(inf, 0);
get_ans(Rt, 1, n, L, R);
}
}T;
inline void init() {
T.cnt = 0;
for(ll i = 1; i <= n; i++) rt[i] = 0;
}
inline void solve() {
for(ll t = n; t >= 1; t--) {
ll x = dfn[t];
for(auto i : V0[x]) T.insert(rt[x], 1, n, pos[p[i].y], -siz[p[i].x] - siz[p[i].y], i);
for(auto y : G[x]) rt[x] = T.Merge(rt[x], rt[y], 1, n);
for(auto i : V0[x]) {
T.Get_ans(rt[x], pos[p[i].y], posr[p[i].y]);
Mn(i, T.mn.se, T.mn.fr + siz[p[i].x] + siz[p[i].y]);
Mn(i, T.mnse.se, T.mnse.fr + siz[p[i].x] + siz[p[i].y]);
}
}
}
};
//+xi+yi -xj-yj
namespace Sub6 {
inline void init() {
for(ll i = 1; i <= n; i++) BT.mn[i] = BT.mnse[i] = BT.amn[i] = BT.amnse[i] = mp(inf, 0);
BT.top = 0;
}
inline void solve() {
for(ll t = 1; t <= 2 * n; t++) {
ll x = dfn2[t];
if(!tag[x]) {
tag[x] = 1, tagx[x] = BT.top;
for(auto i : V0[x]) BT.Insert(p[i].y, siz[p[i].x] + siz[p[i].y], i);
for(auto i : V0[x]) {
BT.Get_ans(p[i].y);
Mn(i, BT.Mn.se, BT.Mn.fr - siz[p[i].x] - siz[p[i].y]);
Mn(i, BT.Mnse.se, BT.Mnse.fr - siz[p[i].x] - siz[p[i].y]);
}
}
else tag[x] = 0, BT.Back(tagx[x]);
}
}
};
//-xi-yi +xj+yj
inline void Clear() {
for(ll i = 1; i <= m; i++) lk[i] = mp(inf, 0);
}
/*
xi yi
xj yj
*/
inline void Boruvka() {
Clear();
Sub1 :: init(), Sub1 :: solve();
Sub2 :: init(), Sub2 :: solve();
Sub3 :: init(), Sub3 :: solve();
Sub4 :: init(), Sub4 :: solve();
Sub5 :: init(), Sub5 :: solve();
Sub6 :: init(), Sub6 :: solve();
for(ll i = 1; i <= m; i++) {
ll j = U.findSet(i);
if(lk[i].fr < lk[j].fr) lk[j] = lk[i];
}
for(ll i = 1; i <= m; i++) {
if(U.findSet(i) == i) {
ll j = lk[i].se;
if(!j) continue;
if(U.findSet(j) != i) U.unionSet(i, j), Ans += lk[i].fr;
}
}
}
int main() {
// freopen("1.in", "r", stdin);
// freopen("mine.out", "w", stdout);
n = read(), m = read();
U.makeSet(m);
for(ll i = 2; i <= n; i++) {
Fa[i] = read();
G[Fa[i]].push_back(i);
}
for(ll i = 1; i <= m; i++) {
p[i].x = read(), p[i].y = read();
V0[p[i].x].push_back(i);
V1[p[i].y].push_back(i);
}
dfs(1);
Rtt = BT.build(1);
while(chk()) Boruvka();
write(Ans), putchar('\n');
return 0;
}
/*
8 2
1 2 3 1 5 4 3
8 4
3 2
8 3
1 2 3 1 5 4 3
8 4
4 1
3 2
*/
詳細信息
Subtask #1:
score: 10
Accepted
Test #1:
score: 10
Accepted
time: 43ms
memory: 745420kb
Test #2:
score: 10
Accepted
time: 45ms
memory: 752580kb
Test #3:
score: 10
Accepted
time: 44ms
memory: 749824kb
Test #4:
score: 10
Accepted
time: 37ms
memory: 751928kb
Test #5:
score: 10
Accepted
time: 44ms
memory: 752052kb
Subtask #2:
score: 10
Accepted
Dependency #1:
100%
Accepted
Test #6:
score: 10
Accepted
time: 1532ms
memory: 831684kb
Test #7:
score: 10
Accepted
time: 914ms
memory: 824076kb
Test #8:
score: 10
Accepted
time: 629ms
memory: 821212kb
Test #9:
score: 10
Accepted
time: 644ms
memory: 828172kb
Test #10:
score: 10
Accepted
time: 837ms
memory: 823324kb
Subtask #3:
score: 10
Accepted
Dependency #2:
100%
Accepted
Test #11:
score: 10
Accepted
time: 2644ms
memory: 836756kb
Test #12:
score: 10
Accepted
time: 1690ms
memory: 831216kb
Test #13:
score: 10
Accepted
time: 1244ms
memory: 823040kb
Test #14:
score: 10
Accepted
time: 1234ms
memory: 824588kb
Test #15:
score: 10
Accepted
time: 1586ms
memory: 827356kb
Subtask #4:
score: 20
Accepted
Test #16:
score: 20
Accepted
time: 452ms
memory: 753864kb
Test #17:
score: 20
Accepted
time: 565ms
memory: 753896kb
Test #18:
score: 20
Accepted
time: 318ms
memory: 752396kb
Test #19:
score: 20
Accepted
time: 412ms
memory: 753936kb
Test #20:
score: 20
Accepted
time: 450ms
memory: 748672kb
Subtask #5:
score: 10
Accepted
Test #21:
score: 10
Accepted
time: 6225ms
memory: 924440kb
Test #22:
score: 10
Accepted
time: 6281ms
memory: 925824kb
Test #23:
score: 10
Accepted
time: 6339ms
memory: 923232kb
Test #24:
score: 10
Accepted
time: 6303ms
memory: 924864kb
Test #25:
score: 10
Accepted
time: 6317ms
memory: 921580kb
Subtask #6:
score: 10
Accepted
Test #26:
score: 10
Accepted
time: 1279ms
memory: 809412kb
Test #27:
score: 10
Accepted
time: 1276ms
memory: 804304kb
Test #28:
score: 10
Accepted
time: 1274ms
memory: 809472kb
Test #29:
score: 10
Accepted
time: 1291ms
memory: 813628kb
Test #30:
score: 10
Accepted
time: 1276ms
memory: 811484kb
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: 4038ms
memory: 833816kb
Test #32:
score: 30
Accepted
time: 2376ms
memory: 830228kb
Test #33:
score: 30
Accepted
time: 1845ms
memory: 822012kb
Test #34:
score: 30
Accepted
time: 1862ms
memory: 833804kb
Test #35:
score: 30
Accepted
time: 2254ms
memory: 837468kb
Test #36:
score: 30
Accepted
time: 3994ms
memory: 838092kb
Test #37:
score: 30
Accepted
time: 2352ms
memory: 839672kb
Test #38:
score: 30
Accepted
time: 1790ms
memory: 826492kb
Test #39:
score: 30
Accepted
time: 1904ms
memory: 836964kb
Test #40:
score: 30
Accepted
time: 2241ms
memory: 834444kb