QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#44661#4408. 燃烧的呐球Remakee#100 ✓7397ms867076kbC++148.0kb2022-08-20 18:05:432022-08-21 09:27:29

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-08-21 09:27:29]
  • 评测
  • 测评结果:100
  • 用时:7397ms
  • 内存:867076kb
  • [2022-08-20 18:05:43]
  • 提交

answer

// Skyqwq
#include <bits/stdc++.h>

#define pb push_back
#define fi first
#define se second
#define mp make_pair

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

template <typename T> bool chkMax(T &x, T y) { return (y > x) ? x = y, 1 : 0; }
template <typename T> bool chkMin(T &x, T y) { return (y < x) ? x = y, 1 : 0; }

template <typename T> void inline read(T &x) {
    int f = 1; x = 0; char s = getchar();
    while (s < '0' || s > '9') { if (s == '-') f = -1; s = getchar(); }
    while (s <= '9' && s >= '0') x = x * 10 + (s ^ 48), s = getchar();
    x *= f;
}

const int N = 1e6 + 5, M = 1e5 + 5, INF = 1e9;

int n, m, fa[N], X[M], Y[M], f[M], siz[M], c[M], top[N], dfn[N], sz[N], dfncnt, d[N], son[N], pre[N];

LL ans;

vector<int> g[N], px[N], py[N], ta[N];

int find(int x) {
	return x == f[x] ? x : f[x] = find(f[x]);
}

void inline merge(int x, int y) {
	x = find(x), y = find(y);
	if (x == y) return;
	if (siz[x] > siz[y]) swap(x, y);
	f[x] = y, siz[y] += siz[x];
}

void dfs0(int u) {
	sz[u] = 1;
	for (int v: g[u]) {
		d[v] = d[u] + 1;
		dfs0(v);
		sz[u] += sz[v];
		if (sz[v] > sz[son[u]]) son[u] = v;
	}
}

void dfs1(int u, int tp) {
	dfn[u] = ++dfncnt;
	pre[dfn[u]] = u;
	top[u] = tp;
	if (son[u]) dfs1(son[u], tp);
	for (int v : g[u]) {
		if (v == son[u]) continue;
		dfs1(v, v);
	}
}

// x is y ancestor?

bool inline isA(int x, int y) {
	return dfn[x] <= dfn[y] && dfn[y] < dfn[x] + sz[x];
}

int inline D(int x, int y) {
	if (isA(y, x)) return 0;
	if (isA(x, y)) return sz[x] - sz[y];
	return sz[x];
}

PII e[N];

struct Node{
	PII c[2];
	void inline init() {
		c[0] = c[1] = mp(INF, INF);
	}
	void inline ins(PII x) {
		if (c[0].se == x.se) {
			chkMin(c[0].fi, x.fi);
			return;
		} else if (c[1].se == x.se) {
			chkMin(c[1].fi, x.fi);
			if (c[0].fi > c[1].fi) swap(c[0], c[1]);
			return;
		}
		if (x.fi <= c[0].fi) c[1] = c[0], c[0] = x;
		else if (x.fi <= c[1].fi) c[1] = x;
	}
	void inline add(int x) {
		c[0].fi += x;
		c[1].fi += x;
	}
	void inline ext(Node x) {
		ins(x.c[0]), ins(x.c[1]);
	}
} E;

void inline upd(int x, Node o) {
	if (x != o.c[0].se) chkMin(e[x], o.c[0]);
	else chkMin(e[x], o.c[1]);
}

Node Add(Node x, int b) {
	x.c[0].fi += b, x.c[1].fi += b;
	return x;
}

Node operator + (const Node &a, const Node &b) {
	Node c = a;
	c.ext(b);
	return c;
}

Node UP[N][2], DO[N][2];


struct T{
	int l, r;
	Node v;
};

struct T1{
	T t[M * 22];
	int idx, rt[N];
	void inline clr() {
		for (int i = 1; i <= idx; i++) 
			t[i] = (T) { 0, 0 };
		idx = 0;
		for (int i = 1; i <= n; i++) rt[i] = 0;
	}	
	#define ls t[p].l
	#define rs t[p].r
	void inline ins(int &p, int l, int r, int x, PII y) {
		if (!p) {
			t[p = ++idx].v.init();
		}
		t[p].v.ins(y);
		if (l == r) return;
		int mid = (l + r) >> 1;
		if (x <= mid) ins(ls, l, mid, x, y);
		else ins(rs, mid + 1, r, x, y);
	}
	Node inline qry(int p, int l, int r, int x, int y) {
		if (!p) return E;
		if (x <= l && r <= y) return t[p].v;
		int mid = (l + r) >> 1;
		if (y <= mid) return qry(ls, l, mid, x, y);
		if (x > mid) return qry(rs, mid + 1, r, x, y);
		return qry(ls, l, mid, x, y) + qry(rs, mid + 1, r, x, y);
	}
	void inline mg(int &p, int q, int l, int r) {
		if (!q) return;
		if (!p) {
			p = q;
			return;
		}
		t[p].v.ext(t[q].v);
		int mid = (l + r) >> 1;
		mg(ls, t[q].l, l, mid);
		mg(rs, t[q].r, mid + 1, r);
	}
} t1;

struct T2{
	T t[M * 84];
	int idx, rt[N];
	void inline clr() {
		for (int i = 1; i <= idx; i++) 
			t[i] = (T) { 0, 0 };
		idx = 0;
		for (int i = 1; i <= n; i++) rt[i] = 0;
	}	
	#define ls t[p].l
	#define rs t[p].r
	void inline ins(int &p, int l, int r, int x, int y, PII k) {
		if (!p) {
			t[p = ++idx].v.init();
		}
		if (x <= l && r <= y) {
			t[p].v.ins(k);
			return;
		}
		int mid = (l + r) >> 1;
		if (x <= mid) ins(ls, l, mid, x, y, k);
		if (mid < y) ins(rs, mid + 1, r, x, y, k);
	}
	Node inline qry(int p, int l, int r, int x) {
		if (!p) return E;
		if (l == r) return t[p].v;
		int mid = (l + r) >> 1;
		if (x <= mid) return t[p].v + qry(ls, l, mid, x);
		else return t[p].v + qry(rs, mid + 1, r, x);
	}
	void inline mg(int &p, int q, int l, int r) {
		if (!q) return;
		if (!p) {
			p = q;
			return;
		}
		t[p].v.ext(t[q].v);
		int mid = (l + r) >> 1;
		mg(ls, t[q].l, l, mid);
		mg(rs, t[q].r, mid + 1, r);
	}
} t2[2];


struct T3{
	T t[N << 1];
	int idx, rt;
	void inline clr() {
		for (int i = 1; i <= idx; i++) 
			t[i] = (T) { 0, 0 };
		idx = 0;
		rt = 0;
	}	
	#define ls t[p].l
	#define rs t[p].r
	void inline ins(int &p, int l, int r, int x, int y, PII k) {
		if (!p) {
			t[p = ++idx].v.init();
		}
		if (x <= l && r <= y) {
			t[p].v.ins(k);
			return;
		}
		int mid = (l + r) >> 1;
		if (x <= mid) ins(ls, l, mid, x, y, k);
		if (mid < y) ins(rs, mid + 1, r, x, y, k);
	}
	Node inline qry(int p, int l, int r, int x) {
		if (!p) return E;
		if (l == r) return t[p].v;
		int mid = (l + r) >> 1;
		if (x <= mid) return t[p].v + qry(ls, l, mid, x);
		else return t[p].v + qry(rs, mid + 1, r, x);
	}
} t3;

void inline Ins(int u) {
	for (int o: px[u]) {
		t1.ins(t1.rt[u], 1, n, dfn[Y[o]], mp(-sz[X[o]] - sz[Y[o]], c[o]));
		UP[u][0].ins(mp(sz[X[o]] + sz[Y[o]], c[o])), DO[u][0].ins(mp(-sz[X[o]] + sz[Y[o]], c[o]));
		t2[0].ins(t2[0].rt[u], 1, n, dfn[Y[o]], dfn[Y[o]] + sz[Y[o]] - 1, mp(-sz[X[o]] + sz[Y[o]], c[o]));
	}
	for (int o: py[u]) {
		UP[u][1].ins(mp(sz[X[o]] + sz[Y[o]], c[o])), DO[u][1].ins(mp(sz[X[o]] - sz[Y[o]], c[o]));
		t2[1].ins(t2[1].rt[u], 1, n, dfn[X[o]], dfn[X[o]] + sz[X[o]] - 1, mp(sz[X[o]] - sz[Y[o]], c[o]));
	}
}


void inline Chk(int u) {
	for (int o: px[u]) {
		upd(c[o], Add(UP[u][0], -sz[X[o]] + sz[Y[o]]));
		upd(c[o], Add(DO[u][0], sz[X[o]] + sz[Y[o]]));
		upd(c[o], Add(t1.qry(t1.rt[u], 1, n, dfn[Y[o]], dfn[Y[o]] + sz[Y[o]] - 1), sz[X[o]] + sz[Y[o]]));
		upd(c[o], Add(t2[0].qry(t2[0].rt[u], 1, n, dfn[Y[o]]), sz[X[o]] - sz[Y[o]]));
	}
	for (int o: py[u]) {
		upd(c[o], Add(UP[u][1], sz[X[o]] - sz[Y[o]]));
		upd(c[o], Add(DO[u][1], sz[X[o]] + sz[Y[o]]));
		upd(c[o], Add(t2[1].qry(t2[1].rt[u], 1, n, dfn[X[o]]), -sz[X[o]] + sz[Y[o]]));
	}
}


void inline boruvka() {
	for (int i = 1; i <= m; i++) f[i] = i, siz[i] = 1;
	while (siz[find(1)] < m) {
		t1.clr();
		t2[0].clr(), t2[1].clr();
		for (int i = 1; i <= m; i++) c[i] = find(i), e[i] = mp(INF, INF);
		
		Node sm; sm.init();
		for (int i = 1; i <= m; i++) {
			sm.ins(mp(sz[X[i]] + sz[Y[i]], c[i]));
		}
		for (int i = 1; i <= m; i++) {
			upd(c[i], Add(sm, sz[X[i]] + sz[Y[i]]));
		}
		for (int i = 1; i <= n; i++) {
			for (int j = 0; j < 2; j++) DO[i][j].init(), UP[i][j].init();
		}
		for (int i = 1; i <= n; i++) Ins(i);
		for (int i = 2; i <= n; i++) {
			UP[i][0].ext(UP[fa[i]][0]);
			UP[i][1].ext(UP[fa[i]][1]);
		}
		for (int i = n; i >= 1; i--) {
			Chk(i);
			if (i == 1) break;
			t1.mg(t1.rt[fa[i]], t1.rt[i], 1, n);
			t2[0].mg(t2[0].rt[fa[i]], t2[0].rt[i], 1, n);
			t2[1].mg(t2[1].rt[fa[i]], t2[1].rt[i], 1, n);
			for (int j = 0; j < 2; j++) {
				DO[fa[i]][j].ext(DO[i][j]);
			}
		}
		for (int i = 1; i <= n; i++) {
			int u = pre[i];
			if (top[u] == u) t3.clr();
			for (int o: px[u]) {
				t3.ins(t3.rt, 1, n, dfn[Y[o]], dfn[Y[o]] + sz[Y[o]] - 1, mp(sz[X[o]] + sz[Y[o]], c[o]));
			}
			for (int o: ta[u]) {
				upd(c[o], Add(t3.qry(t3.rt, 1, n, dfn[Y[o]]), -sz[X[o]] - sz[Y[o]]));
			}
		}
		for (int i = 1; i <= m; i++) {
			if (c[i] == i) {
				PII o = e[i];
				if (find(i) != find(o.se)) {
					merge(i, o.se);
					ans += o.fi;
				}
			}
		}
	}
}

int main() {
	E.init();
	//freopen("a.in", "r", stdin);
	read(n), read(m);
	for (int i = 2; i <= n; i++) read(fa[i]), g[fa[i]].pb(i);
	for (int i = 1; i <= m; i++) {
		read(X[i]), read(Y[i]);
		px[X[i]].pb(i);
		py[Y[i]].pb(i);
	}
	dfs0(1);
	dfs1(1, 1);
	for (int i = 1; i <= m; i++) {
		int p = X[i];
		while (p) {
			ta[p].pb(i);
			p = fa[top[p]];
		}
	}
	boruvka();
	printf("%lld\n", ans);
    return 0;
}

详细

Subtask #1:

score: 10
Accepted

Test #1:

score: 10
Accepted
time: 96ms
memory: 590136kb

Test #2:

score: 0
Accepted
time: 88ms
memory: 590096kb

Test #3:

score: 0
Accepted
time: 93ms
memory: 590088kb

Test #4:

score: 0
Accepted
time: 71ms
memory: 590020kb

Test #5:

score: 0
Accepted
time: 77ms
memory: 590068kb

Subtask #2:

score: 10
Accepted

Dependency #1:

100%
Accepted

Test #6:

score: 10
Accepted
time: 1487ms
memory: 715108kb

Test #7:

score: 0
Accepted
time: 1104ms
memory: 713328kb

Test #8:

score: 0
Accepted
time: 804ms
memory: 706004kb

Test #9:

score: 0
Accepted
time: 824ms
memory: 710352kb

Test #10:

score: 0
Accepted
time: 1079ms
memory: 710980kb

Subtask #3:

score: 10
Accepted

Dependency #2:

100%
Accepted

Test #11:

score: 10
Accepted
time: 2975ms
memory: 719528kb

Test #12:

score: 0
Accepted
time: 2250ms
memory: 718256kb

Test #13:

score: 0
Accepted
time: 1720ms
memory: 709688kb

Test #14:

score: 0
Accepted
time: 1702ms
memory: 714200kb

Test #15:

score: 0
Accepted
time: 2202ms
memory: 715740kb

Subtask #4:

score: 20
Accepted

Test #16:

score: 20
Accepted
time: 508ms
memory: 595128kb

Test #17:

score: 0
Accepted
time: 636ms
memory: 595236kb

Test #18:

score: 0
Accepted
time: 439ms
memory: 594692kb

Test #19:

score: 0
Accepted
time: 444ms
memory: 594760kb

Test #20:

score: 0
Accepted
time: 640ms
memory: 595192kb

Subtask #5:

score: 10
Accepted

Test #21:

score: 10
Accepted
time: 7290ms
memory: 867040kb

Test #22:

score: 0
Accepted
time: 7335ms
memory: 866972kb

Test #23:

score: 0
Accepted
time: 7261ms
memory: 867000kb

Test #24:

score: 0
Accepted
time: 7397ms
memory: 867032kb

Test #25:

score: 0
Accepted
time: 7259ms
memory: 867076kb

Subtask #6:

score: 10
Accepted

Test #26:

score: 10
Accepted
time: 2136ms
memory: 702808kb

Test #27:

score: 0
Accepted
time: 2021ms
memory: 702828kb

Test #28:

score: 0
Accepted
time: 2038ms
memory: 702772kb

Test #29:

score: 0
Accepted
time: 2074ms
memory: 702832kb

Test #30:

score: 0
Accepted
time: 2023ms
memory: 702904kb

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: 5494ms
memory: 726748kb

Test #32:

score: 0
Accepted
time: 3839ms
memory: 725756kb

Test #33:

score: 0
Accepted
time: 2892ms
memory: 716004kb

Test #34:

score: 0
Accepted
time: 2860ms
memory: 720660kb

Test #35:

score: 0
Accepted
time: 3831ms
memory: 722964kb

Test #36:

score: 0
Accepted
time: 5500ms
memory: 726640kb

Test #37:

score: 0
Accepted
time: 3894ms
memory: 725704kb

Test #38:

score: 0
Accepted
time: 2811ms
memory: 715816kb

Test #39:

score: 0
Accepted
time: 2804ms
memory: 720428kb

Test #40:

score: 0
Accepted
time: 3777ms
memory: 722784kb