QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#864742 | #4408. 燃烧的呐球 | 1234567890 | 40 | 5694ms | 1483500kb | C++14 | 13.8kb | 2025-01-20 22:44:18 | 2025-01-20 22:44:19 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#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(ll x) {
if(x < 0) x = -x, putchar('-');
if(x >= 10) write(x / 10);
putchar(x % 10 + '0');
}
ll n, m, Ans, Rtt;
ll Fa[1000005], siz[1000005];
vector <ll> G[1000005];
vector <pii> V[1000005];
struct Pa {
ll x, y;
}p[100005];
ll dfn[1000005], pos[1000005], posr[1000005], son[1000005], tot;
inline void dfs(ll 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;
}
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];
inline void push_up(ll x) {
if(ls(x)) {
upd(mn[x], mnse[x], mn[ls(x)].fr, mn[ls(x)].se);
upd(mn[x], mnse[x], mnse[ls(x)].fr, mnse[ls(x)].se);
}
if(rs(x)) {
upd(mn[x], mnse[x], mn[ls(x)].fr, mn[ls(x)].se);
upd(mn[x], mnse[x], mnse[ls(x)].fr, mnse[ls(x)].se);
}
}
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) {
push_up(sta[l]);
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;
push_up(sta[i]);
return sta[i];
}
}
return 0;
}
inline ll build(ll x) {
mn[x] = mnse[x] = mp(inf, 0);
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];
}
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++) {
if(U.findSet(i) != U.findSet(mn.se)) Mn(i, mn.se, siz[p[i].x] + siz[p[i].y] + mn.fr);
if(U.findSet(i) != U.findSet(mnse.se)) 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 dfs2(ll x) {
mnx[x] = mnsex[x] = mp(inf, 0);
mny[x] = mnsey[x] = mp(inf, 0);
for(auto i : V[x]) {
if(i.se == 0) upd(mnx[x], mnsex[x], -siz[p[i.fr].x] + siz[p[i.fr].y], i.fr);
else upd(mny[x], mnsey[x], siz[p[i.fr].x] - siz[p[i.fr].y], i.fr);
}
// if(x == 2) printf("!! %lld %lld\n", mnx[x].se, mnsex)
for(auto y : G[x]) {
dfs2(y);
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 init() {
dfs2(1);
}
inline void dfs22(ll x) {
for(auto i : V[x]) {
// if(x == 2 && i.se == 1) printf("?? %lld %lld %lld\n", i.fr, mny[x].se, mnsey[x].se);
if(i.se == 0) {
Mn(i.fr, mnx[x].se, mnx[x].fr + siz[p[i.fr].x] + siz[p[i.fr].y]);
Mn(i.fr, mnsex[x].se, mnsex[x].fr + siz[p[i.fr].x] + siz[p[i.fr].y]);
}
else {
Mn(i.fr, mny[x].se, mny[x].fr + siz[p[i.fr].x] + siz[p[i.fr].y]);
Mn(i.fr, mnsey[x].se, mnsey[x].fr + siz[p[i.fr].x] + siz[p[i.fr].y]);
}
}
for(auto y : G[x]) dfs22(y);
}
inline void solve() {
dfs22(1);
}
};
//+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 dfs3(ll x) {
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 : V[x]) {
if(i.se == 0) upd(mnx[cntx], mnsex[cntx], siz[p[i.fr].x] + siz[p[i.fr].y], i.fr);
else upd(mny[cnty], mnsey[cnty], siz[p[i.fr].x] + siz[p[i.fr].y], i.fr);
}
for(auto i : V[x]) {
if(i.se == 0) {
Mn(i.fr, mnx[cntx].se, mnx[cntx].fr - siz[p[i.fr].x] + siz[p[i.fr].y]);
Mn(i.fr, mnsex[cntx].se, mnsex[cntx].fr - siz[p[i.fr].x] + siz[p[i.fr].y]);
}
else {
Mn(i.fr, mny[cnty].se, mny[cnty].fr + siz[p[i.fr].x] - siz[p[i.fr].y]);
Mn(i.fr, mnsey[cnty].se, mnsey[cnty].fr + siz[p[i.fr].x] - siz[p[i.fr].y]);
}
}
for(auto y : G[x]) dfs3(y);
cntx--, cnty--;
}
inline void solve() {
dfs3(1);
}
};
//-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].mn;
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 dfs4(ll x) {
ll topx = Tx.top, topy = Ty.top;
for(auto i : V[x]) {
if(i.se == 0) Tx.update(1, pos[p[i.fr].y], siz[p[i.fr].x] - siz[p[i.fr].y], i.fr);
else Ty.update(1, pos[p[i.fr].x], -siz[p[i.fr].x] + siz[p[i.fr].y], i.fr);
}
for(auto i : V[x]) {
if(i.se == 0) {
Tx.Get_ans(pos[p[i.fr].y], posr[p[i.fr].y]);
Mn(i.fr, Tx.mn.se, Tx.mn.fr - siz[p[i.fr].x] + siz[p[i.fr].y]);
Mn(i.fr, Tx.mnse.se, Tx.mnse.fr - siz[p[i.fr].x] + siz[p[i.fr].y]);
}
else {
Ty.Get_ans(pos[p[i.fr].x], posr[p[i.fr].x]);
Mn(i.fr, Ty.mn.se, Ty.mn.fr + siz[p[i.fr].x] - siz[p[i.fr].y]);
Mn(i.fr, Ty.mnse.se, Ty.mnse.fr + siz[p[i.fr].x] - siz[p[i.fr].y]);
}
}
for(auto y : G[x]) dfs4(y);
Tx.Back(topx), Ty.Back(topy);
}
inline void solve() {
dfs4(1);
}
};
//-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 dfs5(ll x) {
for(auto i : V[x]) {
if(i.se == 0) {
T.insert(rt[x], 1, n, pos[p[i.fr].y], -siz[p[i.fr].x] - siz[p[i.fr].y], i.fr);
}
}
for(auto y : G[x]) {
dfs5(y);
rt[x] = T.Merge(rt[x], rt[y], 1, n);
}
for(auto i : V[x]) {
if(i.se == 0) {
T.Get_ans(rt[x], pos[p[i.fr].y], posr[p[i.fr].y]);
Mn(i.fr, T.mn.se, T.mn.fr + siz[p[i.fr].x] + siz[p[i.fr].y]);
Mn(i.fr, T.mnse.se, T.mnse.fr + siz[p[i.fr].x] + siz[p[i.fr].y]);
}
}
}
inline void solve() {
dfs5(1);
}
};
//+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 dfs6(ll x) {
ll lst = BT.top;
for(auto i : V[x]) if(i.se == 0) BT.Insert(p[i.fr].y, siz[p[i.fr].x] + siz[p[i.fr].y], i.fr);
for(auto i : V[x]) {
if(i.se == 0) {
BT.Get_ans(p[i.fr].y);
Mn(i.fr, BT.Mn.se, BT.Mn.fr - siz[p[i.fr].x] - siz[p[i.fr].y]);
Mn(i.fr, BT.Mnse.se, BT.Mnse.fr - siz[p[i.fr].x] - siz[p[i.fr].y]);
}
}
for(auto y : G[x]) dfs6(y);
BT.Back(lst);
}
inline void solve() {
dfs6(1);
}
};
//-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++) {
// printf("??? %lld %lld %lld\n", i, lk[i].fr, lk[i].se);
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;
}
}
// exit(0);
}
int main() {
// freopen(".in", "r", stdin);
// freopen(".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();
V[p[i].x].push_back(mp(i, 0));
V[p[i].y].push_back(mp(i, 1));
}
dfs(1);
Rtt = BT.build(1);
while(chk()) Boruvka();
write(Ans), putchar('\n');
return 0;
}
/*
5 2
1 2 1 3
1 1
5 2
*/
详细
Subtask #1:
score: 10
Accepted
Test #1:
score: 10
Accepted
time: 79ms
memory: 1307852kb
Test #2:
score: 10
Accepted
time: 65ms
memory: 1306048kb
Test #3:
score: 10
Accepted
time: 59ms
memory: 1307592kb
Test #4:
score: 10
Accepted
time: 62ms
memory: 1308484kb
Test #5:
score: 10
Accepted
time: 60ms
memory: 1306012kb
Subtask #2:
score: 10
Accepted
Dependency #1:
100%
Accepted
Test #6:
score: 10
Accepted
time: 3822ms
memory: 1477844kb
Test #7:
score: 10
Accepted
time: 2014ms
memory: 1476424kb
Test #8:
score: 10
Accepted
time: 1099ms
memory: 1470272kb
Test #9:
score: 10
Accepted
time: 1209ms
memory: 1483500kb
Test #10:
score: 10
Accepted
time: 1709ms
memory: 1474756kb
Subtask #3:
score: 10
Accepted
Dependency #2:
100%
Accepted
Test #11:
score: 10
Accepted
time: 5694ms
memory: 1480520kb
Test #12:
score: 10
Accepted
time: 3403ms
memory: 1478016kb
Test #13:
score: 10
Accepted
time: 2060ms
memory: 1472236kb
Test #14:
score: 10
Accepted
time: 2204ms
memory: 1477204kb
Test #15:
score: 10
Accepted
time: 2951ms
memory: 1477196kb
Subtask #4:
score: 0
Wrong Answer
Test #16:
score: 0
Wrong Answer
time: 553ms
memory: 1314248kb
Subtask #5:
score: 0
Time Limit Exceeded
Test #21:
score: 0
Time Limit Exceeded
Subtask #6:
score: 10
Accepted
Test #26:
score: 10
Accepted
time: 1964ms
memory: 1446692kb
Test #27:
score: 10
Accepted
time: 1866ms
memory: 1449224kb
Test #28:
score: 10
Accepted
time: 1886ms
memory: 1447832kb
Test #29:
score: 10
Accepted
time: 1869ms
memory: 1449508kb
Test #30:
score: 10
Accepted
time: 1910ms
memory: 1449064kb
Subtask #7:
score: 0
Skipped
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Dependency #3:
100%
Accepted
Dependency #4:
0%