QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#884282 | #4408. 燃烧的呐球 | ddxrS | 100 ✓ | 6343ms | 855616kb | C++14 | 6.9kb | 2025-02-05 23:29:48 | 2025-02-05 23:29:49 |
Judging History
answer
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N = 1e6 + 5, inf = 0x3f3f3f3f;
int n, m, f[N], x[N], y[N], fd[N * 20], Tp[N * 20], fa[N], col[N], pos[N];
ll ans, w[N];
struct node {
pair<int, int> fi, se;
node(int a = inf, int b = 0, int c = inf, int d = 0) : fi({a, b}), se({c, d}) {}
void chkmin(node tmp) {
if(fi.first > tmp.fi.first) swap(fi, tmp.fi);
if(se.first >= tmp.fi.first && col[fi.second] != col[tmp.fi.second]) swap(se, tmp.fi);
if(se.first >= tmp.se.first && col[fi.second] != col[tmp.se.second]) swap(se, tmp.se);
}
};
inline void chkmin(int p, node tmp, int dat) {
p = col[p];
if(tmp.fi.first + dat < w[p] && p != col[tmp.fi.second]) w[p] = tmp.fi.first + dat, pos[p] = tmp.fi.second;
if(tmp.se.first + dat < w[p] && p != col[tmp.se.second]) w[p] = tmp.se.first + dat, pos[p] = tmp.se.second;
}
inline int FindSet(int x) {return x == fa[x] ? x : fa[x] = FindSet(fa[x]);}
vector<int> E[N], vec[N], Vec[N];
int dfn[N], siz[N], cnt, tcnt;
inline void dfs(int x) {
dfn[x] = ++cnt, fd[++tcnt] = x, siz[x] = 1;
for(auto y : E[x]) dfs(y), siz[x] += siz[y];
fd[++tcnt] = -x;
}
int rt, rot[N], tot, lc[N * 20], rc[N * 20];
node tr[N * 20];
inline void pushup(int p) {
tr[p] = node();
if(lc[p]) tr[p].chkmin(tr[lc[p]]);
if(rc[p]) tr[p].chkmin(tr[rc[p]]);
}
inline void change1(int &p, int l, int r, int x, node val) {
int mid = l + r >> 1;
if(!p) p = ++tot, tr[p] = node(), lc[p] = rc[p] = 0;
if(l == r) return tr[p].chkmin(val), void();
if(x <= mid) change1(lc[p], l, mid, x, val);
else change1(rc[p], mid + 1, r, x, val);
pushup(p);
}
inline node query1(int p, int l, int r, int ql, int qr) {
int mid = l + r >> 1;
if(!p) return node();
if(ql <= l && r <= qr) return tr[p];
node ans;
if(ql <= mid) ans.chkmin(query1(lc[p], l, mid, ql, qr));
if(mid < qr) ans.chkmin(query1(rc[p], mid + 1, r, ql, qr));
return ans;
}
node res, *st[N * 20], Val[N * 20]; int tp;
inline void change2(int &p, int l, int r, int ql, int qr, node val) {
int mid = l + r >> 1;
if(!p) p = ++tot, tr[p] = node(), lc[p] = rc[p] = 0;
if(ql <= l && r <= qr) return st[++tp] = tr + p, Val[tp] = *st[tp], tr[p].chkmin(val), void();
if(ql <= mid) change2(lc[p], l, mid, ql, qr, val);
if(mid < qr) change2(rc[p], mid + 1, r, ql, qr, val);
}
inline void query2(int p, int l, int r, int x) {
int mid = l + r >> 1;
if(!p) return;
res.chkmin(tr[p]);
if(l == r) return;
if(x <= mid) query2(lc[p], l, mid, x);
else query2(rc[p], mid + 1, r, x);
}
inline int merge(int pl, int pr) {
if(!pl || !pr) return pl | pr;
tr[pl].chkmin(tr[pr]);
lc[pl] = merge(lc[pl], lc[pr]), rc[pl] = merge(rc[pl], rc[pr]);
return pl;
}
inline void solve1() {//Case1: sxi+syi+sxj+syj
node tmp;
for(int i = 1; i <= m; i++) tmp.chkmin(node(siz[x[i]] + siz[y[i]], i));
for(int i = 1; i <= m; i++) chkmin(i, tmp, siz[x[i]] + siz[y[i]]);
}
inline void solve2() {//Case2: sxi+syi+sxj-syj -> yj in yi
rt = tot = tp = 0;
for(int i = 1; i <= m; i++)
change1(rt, 1, n, dfn[y[i]], node(siz[x[i]] - siz[y[i]], i));
for(int i = 1; i <= m; i++)
chkmin(i, query1(rt, 1, n, dfn[y[i]], dfn[y[i]] + siz[y[i]] - 1), siz[x[i]] + siz[y[i]]);
}
inline void solve3() {//Case3: sxi-syi+sxj+syj -> yi in yj
rt = tot = tp = 0;
for(int i = 1; i <= m; i++)
change2(rt, 1, n, dfn[y[i]], dfn[y[i]] + siz[y[i]] - 1, node(siz[x[i]] + siz[y[i]], i));
for(int i = 1; i <= m; i++)
res = node(), query2(1, 1, n, dfn[y[i]]), chkmin(i, res, siz[x[i]] - siz[y[i]]);
}
inline void solve4() {//Case4: sxi+syi-sxi+syi -> xj in xi
for(int i = 1; i <= n; i++) tr[i] = node();
for(int i = 1; i <= m; i++) tr[x[i]].chkmin(node(-siz[x[i]] + siz[y[i]], i));
for(int i = n; i > 1; i--) tr[f[i]].chkmin(tr[i]);
for(int i = 1; i <= m; i++) chkmin(i, tr[x[i]], siz[x[i]] + siz[y[i]]);
}
inline void solve5() {//Case5: -sxi+syi+sxj+syj -> xi in xj
rt = tot = tp = 0;
for(int i = 1; i <= m; i++)
change2(rt, 1, n, dfn[x[i]], dfn[x[i]] + siz[x[i]] - 1, node(siz[x[i]] + siz[y[i]], i));
for(int i = 1; i <= m; i++)
res = node(), query2(1, 1, n, dfn[x[i]]), chkmin(i, res, -siz[x[i]] + siz[y[i]]);
}
inline void solve6() {//Case6: sxi+syi-sxj-syj -> xj in xi, yj in yi
tot = tp = 0;
for(int i = 1; i <= n; i++) rot[i] = 0;
for(int i = 1; i <= m; i++)
change1(rot[x[i]], 1, n, dfn[y[i]], node({-siz[x[i]] - siz[y[i]], i}));
for(int i = n; i >= 1; i--) {
for(auto p : vec[i])
chkmin(p, query1(rot[i], 1, n, dfn[y[p]], dfn[y[p]] + siz[y[p]] - 1), siz[x[p]] + siz[y[p]]);
if(f[i]) rot[f[i]] = merge(rot[f[i]], rot[i]);
}
}
inline void solve7() {//Case7: sxi-syi-sxj+syj -> xj in xi, yi in yj
tot = tp = 0;
for(int i = 1; i <= n; i++) rot[i] = 0;
for(int i = 1; i <= m; i++)
change2(rot[x[i]], 1, n, dfn[y[i]], dfn[y[i]] + siz[y[i]] - 1, node({-siz[x[i]] + siz[y[i]], i}));
for(int i = n; i >= 1; i--) {
for(auto p : vec[i])
res = node(), query2(rot[i], 1, n, dfn[y[p]]), chkmin(p, res, siz[x[p]] - siz[y[p]]);
if(f[i]) rot[f[i]] = merge(rot[f[i]], rot[i]);
}
}
inline void solve8() {//Case8:-sxi+syi+sxj-syj -> xi in xj, yj in yi
tot = tp = 0;
for(int i = 1; i <= n; i++) rot[i] = 0;
for(int i = 1; i <= m; i++)
change2(rot[y[i]], 1, n, dfn[x[i]], dfn[x[i]] + siz[x[i]] - 1, node({siz[x[i]] - siz[y[i]], i}));
for(int i = n; i >= 1; i--) {
for(auto p : Vec[i])
res = node(), query2(rot[i], 1, n, dfn[x[p]]), chkmin(p, res, -siz[x[p]] + siz[y[p]]);
if(f[i]) rot[f[i]] = merge(rot[f[i]], rot[i]);
}
}
inline void solve9() {//Case9:-sxi-syi+sxj+syj -> xi in xj, yi in yj
rt = tot = tp = 0;
for(int i = 1, u; i <= n + n; i++)
if(fd[i] < 0) for(; tp > Tp[-fd[i]]; tp--) *st[tp] = Val[tp];
else {
Tp[u = fd[i]] = tp;
for(int j = vec[u].size(), t; j--; )
t = vec[u][j], change2(rt, 1, n, dfn[y[t]], dfn[y[t]] + siz[y[t]] - 1, node(siz[x[t]] + siz[y[t]], t));
for(int j = vec[u].size(), t; j--; )
t = vec[u][j], res = node(),query2(rt, 1, n, dfn[y[t]]), chkmin(t, res, -siz[x[t]] - siz[y[t]]);
}
}
int main() {
#ifdef ddxrS
freopen("sample.in", "r", stdin);
freopen("sample.out", "w", stdout);
#endif
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin>>n>>m;
for(int i = 2; i <= n; i++) cin>>f[i], E[f[i]].push_back(i);
for(int i = 1; i <= m; i++) cin>>x[i]>>y[i], vec[x[i]].push_back(i), Vec[y[i]].push_back(i), fa[i] = i;
dfs(1);
for(int cc = m; cc > 1; ) {
for(int i = 1; i <= m; i++) pos[i] = 0, w[i] = inf, col[i] = FindSet(i);
solve1();
solve2(), solve3(), solve4(), solve5();
solve6(), solve7(), solve8();
solve9();
for(int i = 1; i <= m; i++) if(fa[i] == i && i != FindSet(pos[i])) ans += w[i], fa[FindSet(i)] = FindSet(pos[i]), cc--;
}
cout<<ans<<'\n';
cerr<<clock() * 1.0 / CLOCKS_PER_SEC<<'\n';
return 0;
}
Details
Subtask #1:
score: 10
Accepted
Test #1:
score: 10
Accepted
time: 48ms
memory: 726380kb
Test #2:
score: 10
Accepted
time: 50ms
memory: 728772kb
Test #3:
score: 10
Accepted
time: 48ms
memory: 728156kb
Test #4:
score: 10
Accepted
time: 50ms
memory: 727696kb
Test #5:
score: 10
Accepted
time: 47ms
memory: 727000kb
Subtask #2:
score: 10
Accepted
Dependency #1:
100%
Accepted
Test #6:
score: 10
Accepted
time: 854ms
memory: 775716kb
Test #7:
score: 10
Accepted
time: 518ms
memory: 773988kb
Test #8:
score: 10
Accepted
time: 450ms
memory: 772140kb
Test #9:
score: 10
Accepted
time: 462ms
memory: 773068kb
Test #10:
score: 10
Accepted
time: 504ms
memory: 769892kb
Subtask #3:
score: 10
Accepted
Dependency #2:
100%
Accepted
Test #11:
score: 10
Accepted
time: 2144ms
memory: 785588kb
Test #12:
score: 10
Accepted
time: 1228ms
memory: 777852kb
Test #13:
score: 10
Accepted
time: 1146ms
memory: 781892kb
Test #14:
score: 10
Accepted
time: 1067ms
memory: 783064kb
Test #15:
score: 10
Accepted
time: 1185ms
memory: 777700kb
Subtask #4:
score: 20
Accepted
Test #16:
score: 20
Accepted
time: 400ms
memory: 734324kb
Test #17:
score: 20
Accepted
time: 463ms
memory: 741644kb
Test #18:
score: 20
Accepted
time: 295ms
memory: 728864kb
Test #19:
score: 20
Accepted
time: 371ms
memory: 732060kb
Test #20:
score: 20
Accepted
time: 390ms
memory: 732376kb
Subtask #5:
score: 10
Accepted
Test #21:
score: 10
Accepted
time: 6135ms
memory: 855616kb
Test #22:
score: 10
Accepted
time: 6343ms
memory: 853632kb
Test #23:
score: 10
Accepted
time: 6115ms
memory: 853692kb
Test #24:
score: 10
Accepted
time: 6161ms
memory: 847416kb
Test #25:
score: 10
Accepted
time: 6131ms
memory: 851504kb
Subtask #6:
score: 10
Accepted
Test #26:
score: 10
Accepted
time: 1671ms
memory: 780572kb
Test #27:
score: 10
Accepted
time: 1695ms
memory: 778532kb
Test #28:
score: 10
Accepted
time: 1705ms
memory: 784664kb
Test #29:
score: 10
Accepted
time: 1729ms
memory: 776468kb
Test #30:
score: 10
Accepted
time: 1687ms
memory: 778392kb
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: 4361ms
memory: 800712kb
Test #32:
score: 30
Accepted
time: 2351ms
memory: 803276kb
Test #33:
score: 30
Accepted
time: 1975ms
memory: 789128kb
Test #34:
score: 30
Accepted
time: 2006ms
memory: 790100kb
Test #35:
score: 30
Accepted
time: 2274ms
memory: 792904kb
Test #36:
score: 30
Accepted
time: 4288ms
memory: 800776kb
Test #37:
score: 30
Accepted
time: 2331ms
memory: 797128kb
Test #38:
score: 30
Accepted
time: 1977ms
memory: 785028kb
Test #39:
score: 30
Accepted
time: 2010ms
memory: 794324kb
Test #40:
score: 30
Accepted
time: 2299ms
memory: 801076kb