QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#44661 | #4408. 燃烧的呐球 | Remakee# | 100 ✓ | 7397ms | 867076kb | C++14 | 8.0kb | 2022-08-20 18:05:43 | 2022-08-21 09:27:29 |
Judging History
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;
}
Details
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