QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#883813#4408. 燃烧的呐球TrueFalse40 8056ms811564kbC++148.5kb2025-02-05 19:06:432025-02-05 19:06:43

Judging History

This is the latest submission verdict.

  • [2025-02-05 19:06:43]
  • Judged
  • Verdict: 40
  • Time: 8056ms
  • Memory: 811564kb
  • [2025-02-05 19:06:43]
  • Submitted

answer

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1e6 + 5, MAXM = 1e5 + 5, inf = 1e9;

vector<int> G[MAXN], qx[MAXN], qy[MAXN];
int fa[MAXN], siz[MAXN], id[MAXN], dcnt, L[MAXN], R[MAXN];
int n, m, col[MAXN], X[MAXN], Y[MAXN];
vector<int> dfn, rdfn, eul;

long long ans = 0;

inline void dfs(int u) {
  L[u] = id[u] = ++dcnt, siz[u] = 1;
  dfn.push_back(u), eul.push_back(u);
  for (int v : G[u]) dfs(v), siz[u] += siz[v];
  R[u] = dcnt;
  rdfn.push_back(u), eul.push_back(-u);
}

struct E {
  int v, w;
  E(int x = 0, int c = inf) : v(x), w(c) {}
  inline friend bool operator==(E x, E y) { return x.v == y.v; }
  inline friend bool operator<(E x, E y) { return x.w < y.w; }
};

struct I {
  E mn1, mn2;
  I(int x = 0, int c = inf) : mn1(x, c), mn2(0, inf) {}
  inline I operator+=(I oth) {
    if (oth.mn1 < mn1) swap(oth.mn1, mn1), swap(oth.mn2, mn2);
    mn2 = min(mn2, oth.mn1 == mn1 ? oth.mn2 : oth.mn1);
    return *this;
  }
  inline I operator+=(int oth) {
    mn1.w += oth, mn2.w += oth;
    return *this;
  }
  inline I operator+(I oth) const {
    I tmp(*this);
    return tmp += oth;
  }
  inline I operator+(int oth) const {
    I tmp(*this);
    return tmp += oth;
  }
};

struct D {
  int id;
  I val;
  D(int i = 0, I v = I()) : id(i), val(v) {}
};

I r[MAXN];

namespace Case1 {  // out,out
inline void main() {
  I now;
  for (int i = 1; i <= m; ++i) now += I(col[i], siz[X[i]] + siz[Y[i]]);
  for (int i = 1; i <= m; ++i) r[i] += now + (siz[X[i]] + siz[Y[i]]);
}
}  // namespace Case1

namespace Case2 {  // son,out
I minx[MAXN], miny[MAXN];
inline void main() {
  for (int i = 1; i <= n; ++i) minx[i] = miny[i] = I();
  for (int u : rdfn) {
    for (int i : qx[u]) minx[u] += I(col[i], siz[Y[i]] - siz[X[i]]);
    for (int i : qy[u]) miny[u] += I(col[i], siz[X[i]] - siz[Y[i]]);
    for (int v : G[u]) minx[u] += minx[v], miny[u] += miny[v];
    for (int i : qx[u]) r[i] += minx[u] + (siz[Y[i]] + siz[X[i]]);
    for (int i : qy[u]) r[i] += miny[u] + (siz[X[i]] + siz[Y[i]]);
  }
}
}  // namespace Case2

namespace Case3 {  // fa,out
inline void dfs2(int u, I minx) {
  for (int i : qx[u]) minx += I(col[i], siz[X[i]] + siz[Y[i]]);
  for (int i : qx[u]) r[i] += minx + (siz[Y[i]] - siz[X[i]]);
  for (int v : G[u]) dfs2(v, minx);
}
inline void dfs3(int u, I miny) {
  for (int i : qy[u]) miny += I(col[i], siz[Y[i]] + siz[X[i]]);
  for (int i : qy[u]) r[i] += miny + (siz[X[i]] - siz[Y[i]]);
  for (int v : G[u]) dfs3(v, miny);
}
inline void main() { dfs2(1, I()), dfs3(1, I()); }
}  // namespace Case3

namespace Case4 {  // son son
struct SegmentTree {
  struct Node {
    int ls, rs;
    I min;
  } tr[MAXM * 32];
  int tot;
  inline void init() { tot = 0; }
  inline void ins(int u, I k, int l, int r, int &p) {
    if (!p) tr[p = ++tot] = {0, 0, I()};
    tr[p].min += k;
    if (l == r) return;
    int mid = (l + r) >> 1;
    if (u <= mid)
      ins(u, k, l, mid, tr[p].ls);
    else
      ins(u, k, mid + 1, r, tr[p].rs);
  }
  inline I qry(int ul, int ur, int l, int r, int p) {
    if (!p || ul > ur) return I();
    if (ul <= l && r <= ur) return tr[p].min;
    int mid = (l + r) >> 1;
    if (ur <= mid) return qry(ul, ur, l, mid, tr[p].ls);
    if (mid < ul) return qry(ul, ur, mid + 1, r, tr[p].rs);
    return qry(ul, ur, l, mid, tr[p].ls) + qry(ul, ur, mid + 1, r, tr[p].rs);
  }
  inline void merge(int l, int r, int q, int &p) {
    if (!p || !q) return p += q, void();
    tr[p].min += tr[q].min;
    if (l == r) return;
    int mid = (l + r) >> 1;
    merge(l, mid, tr[q].ls, tr[p].ls), merge(mid + 1, r, tr[q].rs, tr[p].rs);
  }
} T;
int rt[MAXN];
inline void dfs4(int u) {
  for (int i : qx[u])
    T.ins(id[Y[i]], I(col[i], -siz[X[i]] - siz[Y[i]]), 1, n, rt[u]);
  for (int v : G[u]) dfs4(v), T.merge(1, n, rt[v], rt[u]);
  for (int i : qx[u])
    r[i] += T.qry(L[Y[i]], R[Y[i]], 1, n, rt[u]) + (siz[X[i]] + siz[Y[i]]);
}
inline void main() {
  T.init();
  for (int i = 1; i <= n; ++i) rt[i] = 0;
  dfs4(1);
}
}  // namespace Case4

namespace Case5 {  // fa,son
D stk[MAXM * 32];
int tp;
struct SegmentTree {
  static const int N = 1 << 20;
  I tr[N << 1];
  inline void upd(int x, I z) {
    x += N, stk[++tp] = D(x, tr[x]), tr[x] += z;
    for (x >>= 1; x; x >>= 1) stk[++tp] = D(x, tr[x]), tr[x] += z;
  }
  inline I qry(int l, int r) {
    I g = I();
    for (l += N - 1, r += N + 1; l ^ r ^ 1; l >>= 1, r >>= 1) {
      if (!(l & 1)) g += tr[l ^ 1];
      if (r & 1) g += tr[r ^ 1];
    }
    return g;
  }
} T;
inline void dfs5(int u) {
  int lst = tp;
  for (int i : qx[u]) T.upd(id[Y[i]], I(col[i], siz[X[i]] - siz[Y[i]]));
  for (int i : qx[u]) r[i] += T.qry(L[Y[i]], R[Y[i]]) + (siz[Y[i]] - siz[X[i]]);
  for (int v : G[u]) dfs5(v);
  while (tp > lst) T.tr[stk[tp].id] = stk[tp].val, --tp;
}
inline void dfs6(int u) {
  int lst = tp;
  for (int i : qy[u]) T.upd(id[X[i]], I(col[i], siz[Y[i]] - siz[X[i]]));
  for (int i : qy[u]) r[i] += T.qry(L[X[i]], R[X[i]]) + (siz[X[i]] - siz[Y[i]]);
  for (int v : G[u]) dfs6(v);
  while (tp > lst) T.tr[stk[tp].id] = stk[tp].val, --tp;
}
inline void main() { dfs5(1), dfs6(1); }
}  // namespace Case5

namespace Case6 {  // fa,fa
int siz[MAXN], hson[MAXN], top[MAXN];
inline void dfs7(int u) {
  siz[u] = 1;
  for (int v : G[u]) {
    dfs7(v), siz[u] += siz[v];
    if (siz[v] > siz[hson[u]]) hson[u] = v;
  }
}
inline void dfs8(int u, int rt) {
  top[u] = rt;
  if (hson[u]) dfs8(hson[u], rt);
  for (int v : G[u])
    if (v ^ hson[u]) dfs8(v, v);
}
D stk1[MAXM * 32], stk2[MAXM];
int tp1, tp2;
struct BalanceTree {
  int ls[MAXN], rs[MAXN], f[MAXN];
  I w[MAXN], mx[MAXN];
  inline void build() {
    for (int s = 1; s <= n; ++s)
      if (top[s] == s) {
        vector<int> ci;
        for (int u = s; u; u = hson[u]) ci.push_back(u);
        function<int(int, int)> link = [&](int x, int y) {
          if (x > y) return 0;
          int all = 0, tsiz = 0;
          for (int i = x; i <= y; ++i) all += siz[ci[i]] - siz[hson[ci[i]]];
          for (int i = x; i <= y; ++i) {
            tsiz += siz[ci[i]] - siz[hson[ci[i]]];
            if (tsiz > all / 2) {
              int p = ci[i];
              ls[p] = link(x, i - 1), rs[p] = link(i + 1, y);
              if (ls[p]) f[ls[p]] = p;
              if (rs[p]) f[rs[p]] = p;
              return p;
            }
          }
          return -1;
        };
        f[link(0, ci.size() - 1)] = fa[s];
      }
  }
  inline void upd(int x, I z) {
    stk2[++tp2] = D(x, w[x]), w[x] += z;
    for (; x; x = f[x]) {
      stk1[++tp1] = D(x, mx[x]), mx[x] += z;
      if (x != ls[f[x]] && x != rs[f[x]]) break;
    }
  }
  inline I qry(int x) {
    I g = w[x] + mx[ls[x]];
    for (; f[x]; x = f[x])
      if (x != ls[f[x]]) g += w[f[x]] + mx[ls[f[x]]];
    return g;
  }
} T;
inline void init() { dfs7(1), dfs8(1, 1), T.build(); }
inline void dfs9(int u) {
  int lst1 = tp1, lst2 = tp2;
  for (int i : qx[u]) T.upd(Y[i], I(col[i], siz[X[i]] + siz[Y[i]]));
  for (int i : qx[u]) r[i] += T.qry(Y[i]) + (-siz[X[i]] - siz[Y[i]]);
  for (int v : G[u]) dfs9(v);
  while (tp1 > lst1) T.mx[stk1[tp1].id] = stk1[tp1].val, --tp1;
  while (tp2 > lst2) T.w[stk2[tp2].id] = stk2[tp2].val, --tp2;
}
inline void main() { dfs9(1); }
}  // namespace Case6

inline int find(int x) {
  while (x ^ col[x]) x = col[x] = col[col[x]];
  return x;
}

inline void boruvka() {
  for (int i = 1; i <= m; ++i) r[i] = I();
  Case1::main(), Case2::main();
  //  Case3::main();
  Case4::main(), Case5::main(), Case6::main();
  vector<array<int, 3>> cur;
  for (int i = 1; i <= m; ++i)
    if (i ^ col[i]) r[col[i]] += r[i];
  for (int i = 1; i <= m; ++i)
    if (i == col[i]) {
      E e = (r[i].mn1.v == col[i]) ? r[i].mn2 : r[i].mn1;
      cur.push_back({i, e.v, e.w});
    }
  for (auto i : cur)
    if (find(i[0]) ^ find(i[1])) col[find(i[0])] = find(i[1]), ans += i[2];
}

inline bool judge() {
  int cnt = 0;
  for (int i = 1; i <= m; ++i) col[i] = find(i), cnt += (i == col[i]);
  return cnt > 1;
}

int main() {
#ifndef ONLINE_JUDGE
  freopen(".in", "r", stdin);
  freopen(".out", "w", stdout);
#endif

  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);

  cin >> n >> m;
  for (int i = 2; i <= n; ++i) cin >> fa[i], G[fa[i]].push_back(i);

  dfs(1);
  Case6::init();
  for (int i = 1; i <= m; ++i) {
    cin >> X[i] >> Y[i];
    col[i] = i;
    qx[X[i]].push_back(i);
    qy[Y[i]].push_back(i);
  }
  while (judge()) boruvka();
  printf("%lld\n", ans);
  return 0;
}

Details

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 42ms
memory: 391380kb

Subtask #2:

score: 0
Skipped

Dependency #1:

0%

Subtask #3:

score: 0
Skipped

Dependency #2:

0%

Subtask #4:

score: 20
Accepted

Test #16:

score: 20
Accepted
time: 230ms
memory: 395496kb

Test #17:

score: 20
Accepted
time: 256ms
memory: 397804kb

Test #18:

score: 20
Accepted
time: 150ms
memory: 394252kb

Test #19:

score: 20
Accepted
time: 186ms
memory: 394992kb

Test #20:

score: 20
Accepted
time: 189ms
memory: 394936kb

Subtask #5:

score: 10
Accepted

Test #21:

score: 10
Accepted
time: 7518ms
memory: 803832kb

Test #22:

score: 10
Accepted
time: 7672ms
memory: 803720kb

Test #23:

score: 10
Accepted
time: 7395ms
memory: 803816kb

Test #24:

score: 10
Accepted
time: 7725ms
memory: 802924kb

Test #25:

score: 10
Accepted
time: 8056ms
memory: 811564kb

Subtask #6:

score: 10
Accepted

Test #26:

score: 10
Accepted
time: 1162ms
memory: 465896kb

Test #27:

score: 10
Accepted
time: 1352ms
memory: 465444kb

Test #28:

score: 10
Accepted
time: 1153ms
memory: 465136kb

Test #29:

score: 10
Accepted
time: 1480ms
memory: 466164kb

Test #30:

score: 10
Accepted
time: 1262ms
memory: 465032kb

Subtask #7:

score: 0
Skipped

Dependency #1:

0%