QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#884205#4408. 燃烧的呐球ddxrS60 3457ms785080kbC++146.9kb2025-02-05 22:07:062025-02-05 22:07:08

Judging History

This is the latest submission verdict.

  • [2025-02-05 22:07:08]
  • Judged
  • Verdict: 60
  • Time: 3457ms
  • Memory: 785080kb
  • [2025-02-05 22:07:06]
  • 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);
	}
};
void chkmin(int p, node tmp, int dat) {
	// cerr<<p<<' '<<col[p]<<" "<<tmp.fi.second<<' '<<tmp.se.second<<' '<<dat<<' '<<tmp.fi.first<<'\n';
	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;
}
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;
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];
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]]);
}
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);
}
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;
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);
}
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);
}
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;
}
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]]);
}
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]]);
}
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]]);
}
void solve4() {//Case4: sxi+syi-sxi+syi -> xj in xi
	rt = tot = tp = 0;
	for(int i = 1; i <= m; i++) 
		change1(rt, 1, n, dfn[x[i]], node(-siz[x[i]] + siz[y[i]], i));
	for(int i = 1; i <= m; i++) 
		chkmin(i, query1(rt, 1, n, dfn[x[i]], dfn[x[i]] + siz[x[i]] - 1), siz[x[i]] + siz[y[i]]);
}
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]]);
}
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]);
	}
}
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]);
	}
}
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]);
	}
}
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])) 
			// cerr<<i<<' '<<pos[i]<<' '<<w[i]<<'\n',
			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: 88ms
memory: 703892kb

Test #2:

score: 10
Accepted
time: 62ms
memory: 701860kb

Test #3:

score: 10
Accepted
time: 45ms
memory: 703752kb

Test #4:

score: 10
Accepted
time: 50ms
memory: 703740kb

Test #5:

score: 10
Accepted
time: 53ms
memory: 708072kb

Subtask #2:

score: 10
Accepted

Dependency #1:

100%
Accepted

Test #6:

score: 10
Accepted
time: 1046ms
memory: 755096kb

Test #7:

score: 10
Accepted
time: 933ms
memory: 768412kb

Test #8:

score: 10
Accepted
time: 580ms
memory: 763820kb

Test #9:

score: 10
Accepted
time: 615ms
memory: 775248kb

Test #10:

score: 10
Accepted
time: 873ms
memory: 767708kb

Subtask #3:

score: 10
Accepted

Dependency #2:

100%
Accepted

Test #11:

score: 10
Accepted
time: 3457ms
memory: 779704kb

Test #12:

score: 10
Accepted
time: 2310ms
memory: 782068kb

Test #13:

score: 10
Accepted
time: 1967ms
memory: 776008kb

Test #14:

score: 10
Accepted
time: 1679ms
memory: 785080kb

Test #15:

score: 10
Accepted
time: 2065ms
memory: 775776kb

Subtask #4:

score: 20
Accepted

Test #16:

score: 20
Accepted
time: 463ms
memory: 730852kb

Test #17:

score: 20
Accepted
time: 558ms
memory: 730800kb

Test #18:

score: 20
Accepted
time: 347ms
memory: 741560kb

Test #19:

score: 20
Accepted
time: 412ms
memory: 737320kb

Test #20:

score: 20
Accepted
time: 483ms
memory: 728884kb

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: 2550ms
memory: 776604kb

Test #27:

score: 10
Accepted
time: 2998ms
memory: 782620kb

Test #28:

score: 10
Accepted
time: 2721ms
memory: 778524kb

Test #29:

score: 10
Accepted
time: 2878ms
memory: 772376kb

Test #30:

score: 10
Accepted
time: 2390ms
memory: 774552kb

Subtask #7:

score: 0
Skipped

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

100%
Accepted

Dependency #4:

100%
Accepted

Dependency #5:

0%