QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#884282#4408. 燃烧的呐球ddxrS100 ✓6343ms855616kbC++146.9kb2025-02-05 23:29:482025-02-05 23:29:49

Judging History

This is the latest submission verdict.

  • [2025-02-05 23:29:49]
  • Judged
  • Verdict: 100
  • Time: 6343ms
  • Memory: 855616kb
  • [2025-02-05 23:29:48]
  • Submitted

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