QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#884085#4408. 燃烧的呐球TrueFalse0 77ms257204kbC++147.9kb2025-02-05 21:15:452025-02-05 21:15:46

Judging History

This is the latest submission verdict.

  • [2025-02-05 21:15:46]
  • Judged
  • Verdict: 0
  • Time: 77ms
  • Memory: 257204kb
  • [2025-02-05 21:15:45]
  • Submitted

answer

/**
 * @author TrueFalse
 * @details 抽象的闭环传递
 */

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

using ci = const int;

using u32 = uint32_t;
using i64 = int64_t;
using u64 = uint64_t;

template <class T>
inline void Max(T &x, const T &y) noexcept {
  if (x < y) x = y;
}
template <class T>
inline void Min(T &x, const T &y) noexcept {
  if (y < x) x = y;
}

const int inf = 1 << 30;
const int bf_sz = 10 << 24;

char Buf[bf_sz], *bf = Buf + bf_sz;
void Buf_clear() {
  memset(bf, 0x00, Buf + bf_sz - bf);
  bf = Buf + bf_sz;
}

struct Point {
  int x, y;
};

// min with position
struct Minp {
  int v, p;

  Minp(int _v = inf, int _p = 0) : v(_v), p(_p) {}

  bool operator<(const Minp &x) const { return v < x.v; }
  void operator+=(int _v) { v += _v; }
  Minp operator+(int _v) {
    *this += _v;
    return *this;
  }
};

// minp and second-minp
struct Msp {
  using cm = const Msp;
  Minp mn, se;

  Msp() : mn(), se() {}
  Msp(const Minp &_1, const Minp &_2) : mn(_1), se(_2) {}

  void operator+=(const Minp &v) {
    if (v.p == mn.p) {
      Min(mn.v, v.v);
      return;
    }
    if (v.p == se.p) {
      Min(se.v, v.v);
      if (se < mn) swap(mn, se);
      return;
    }
    if (mn.v > v.v)
      se = mn, mn = v;
    else
      se = min(se, v);
  }
  void operator+=(cm &v) {
    *this += v.mn;
    *this += v.se;
  }
  void operator+=(int v) {
    mn += v;
    se += v;
  }
  Msp operator+(int v) {
    *this += v;
    return *this;
  }
  Msp operator+(cm &v) {
    *this += v;
    return *this;
  }
};

const int N = 1e6 + 5;
const int M = 1e5 + 5;

int n, m, fa[N], col[M];
int siz[N];
int dfn[N], rnk[N], tcnt;
int sxy[N];  // siz[a[i].x] + siz[a[i].y]
Point a[M];
Msp con[M];
vector<int> e[N];
vector<int> vx[N], vy[N];
i64 ans;

void dfs(int u) {
  rnk[dfn[u] = ++tcnt] = u;
  siz[u] = 1;
  for (ci &v : e[u]) {
    dfs(v);
    siz[u] += siz[v];
  }
}

int fd(int x) { return col[x] == x ? x : col[x] = fd(col[x]); }
void mg(int x, int y, int v) {
  x = fd(x), y = fd(y);
  if (x != y) col[x] = y, ans += v;
}

bool is_merged() {
  int tot = 0;
  for (int i = 1; i <= n; ++i) col[i] = fd(i), tot += col[i] == i;
  return tot == 1;
}

// double unlimited
namespace Case1 {

void solve() {
  Msp nw;
  for (int i = 1; i <= m; ++i) nw += Minp(sxy[i], col[i]);
  for (int i = 1; i <= m; ++i) con[i] += nw + sxy[i];
}

}  // namespace Case1

// one is unlimited and another is child
namespace Case2 {

// recognise x or y as the parent
Msp mnx[N], mny[N];

void dfs1(int u) {
  for (ci &v : e[u]) {
    dfs1(v);
    mnx[u] += mnx[v];
    mny[u] += mny[v];
  }
}

void solve() {
  for (int i = 1; i <= n; ++i) mnx[i] = mny[i] = Msp();
  for (int i = 1; i <= m; ++i) {
    mnx[a[i].x] += Minp(siz[a[i].y] - siz[a[i].x], col[i]);
    mny[a[i].y] += Minp(siz[a[i].x] - siz[a[i].y], col[i]);
  }
  dfs1(1);
  for (int i = 1; i <= m; ++i) {
    con[i] += mnx[a[i].x] + sxy[i];
    con[i] += mny[a[i].y] + sxy[i];
  }
}

}  // namespace Case2

// one is unlimited and another is parent
namespace Case3 {

// recognise x or y as the child
Msp mnx[N], mny[N];

void dfs1(int u) {
  for (ci &v : e[u]) {
    mnx[v] += mnx[u];
    mny[v] += mny[u];
    dfs1(v);
  }
}

void solve() {
  for (int i = 1; i <= n; ++i) mnx[i] = mny[i] = Msp();
  for (int i = 1; i <= m; ++i) {
    mnx[a[i].x] += Minp(sxy[i], col[i]);
    mny[a[i].y] += Minp(sxy[i], col[i]);
  }
  for (int i = 1, v; i <= m; ++i) {
    v = siz[a[i].y] - siz[a[i].x];
    con[i] += mnx[a[i].x] + v;
    con[i] += mny[a[i].y] + -v;
  }
}

}  // namespace Case3

// double parent-child
namespace Case4 {

// double children
namespace Case4_1 {

struct Segment {
  Msp v;
  Segment *ch[2];

  Segment() : v() { ch[0] = ch[1] = nullptr; }
  void *operator new(size_t sz) { return bf -= sz; }

  void pushup() { v = ch[0]->v + ch[1]->v; }
} *rt[N];

void add(Segment *&p, int l, int r, ci &x, const Minp &y) {
  if (!p) p = new Segment();
  p->v += y;
  if (l == r) return;
  int mid = (l + r) >> 1;
  if (x <= mid)
    add(p->ch[0], l, mid, x, y);
  else
    add(p->ch[1], mid + 1, r, x, y);
}

Msp ask(Segment *p, int l, int r, ci &al, ci &ar) {
  if (!p) return Msp();
  if (al <= l and ar >= r) return p->v;
  int mid = (l + r) >> 1;
#define Al ask(p->ch[0], l, mid, al, ar)
#define Ar ask(p->ch[1], mid + 1, r, al, ar)
  if (al > mid)
    return Ar;
  else if (ar <= mid)
    return Al;
  else
    return Al + Ar;
#undef Al
#undef Ar
}

Segment *merge(Segment *p, Segment *q, int l, int r) {
  if (!p) return q;
  if (!q) return p;
  p->v += q->v;
  if (l == r) return p;
  int mid = (l + r) >> 1;
  p->ch[0] = merge(p->ch[0], q->ch[0], l, mid);
  p->ch[1] = merge(p->ch[1], q->ch[1], mid + 1, r);
  return p;
}

void clear() {
  Buf_clear();
  memset(rt, 0x00, sizeof rt);
}

void dfs1(int u) {
  for (ci &v : e[u]) {
    dfs1(v);
    rt[u] = merge(rt[u], rt[v], 1, n);
  }
  for (int i : vx[u]) add(rt[u], 1, n, dfn[a[i].y], Minp(-sxy[i], col[i]));
  for (int i : vx[u])
    con[i] +=
        ask(rt[u], 1, n, dfn[a[i].y], dfn[a[i].y] + siz[a[i].y] - 1) + sxy[i];
}

void solve() {
  clear();
  dfs1(1);
}

}  // namespace Case4_1

// one is parent and another is child
namespace Case4_2 {

using pmi = pair<Msp, int>;

pmi sta[M << 5], *st = sta;
Msp tr[N << 1];

void change(int p, int l, int r, ci &x, const Minp &y) {
  *st++ = {tr[p], p};
  tr[p] += y;
  if (l == r) return;
  int mid = (l + r) >> 1;
  if (x <= mid)
    change(p << 1, l, mid, x, y);
  else
    change(p << 1 | 1, mid + 1, r, x, y);
}

Msp ask(int p, int l, int r, ci &al, ci &ar) {
  if (al <= l and ar >= r) return tr[p];
  int mid = (l + r) >> 1;
#define Al ask(p << 1, l, mid, al, ar)
#define Ar ask(p << 1 | 1, mid + 1, r, al, ar)
  if (al > mid)
    return Ar;
  else if (ar <= mid)
    return Al;
  else
    return Al + Ar;
#undef Al
#undef Ar
}

void dfs1(int u) {
  pmi *st_c = st;
  for (int i : vx[u])
    change(1, 1, n, dfn[a[i].y], Minp(siz[u] - siz[a[i].y], col[i]));
  for (int i : vx[u])
    con[i] += ask(1, 1, n, dfn[a[i].y], dfn[a[i].y] + siz[a[i].y] - 1) +
              (siz[a[i].y] - siz[u]);
  for (ci &v : e[u]) dfs1(v);
  while (st != st_c) --st, tr[st->second] = st->first;
}

void dfs2(int u) {
  pmi *st_c = st;
  for (int i : vy[u])
    change(1, 1, n, dfn[a[i].x], Minp(siz[u] - siz[a[i].x], col[i]));
  for (int i : vy[u])
    con[i] += ask(1, 1, n, dfn[a[i].x], dfn[a[i].x] + siz[a[i].x] - 1) +
              (siz[a[i].x] - siz[u]);
  for (ci &v : e[u]) dfs2(v);
  while (st != st_c) --st, tr[st->second] = st->first;
}

void solve() {
  dfs1(1);
  dfs2(1);
}

}  // namespace Case4_2

// double parents
namespace Case4_3 {

void solve() {}

}  // namespace Case4_3

}  // namespace Case4

void boruvka() {
  for (int i = 1; i <= m; ++i) con[i] = Msp();
  Case1::solve();
  Case2::solve();
  Case3::solve();
  Case4::Case4_1::solve();
  Case4::Case4_2::solve();
  // Case4::Case4_3::solve();

  for (int i = 1; i <= m; ++i)
    if (i != col[i]) con[col[i]] += con[i];
  Msp *j = con + 1;
  for (int i = 1; i <= m; ++i, ++j) {
    if (i == col[i]) {
      if (j->mn.p == i)
        mg(i, j->se.p, j->se.v);
      else
        mg(i, j->mn.p, j->mn.v);
    }
  }
}

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];
    e[fa[i]].push_back(i);
  }
  for (int i = 1; i <= m; ++i) {
    cin >> a[i].x >> a[i].y;
    vx[a[i].x].push_back(i);
    vy[a[i].y].push_back(i);
  }

  dfs(1);
  for (int i = 1; i <= m; ++i) sxy[i] = siz[a[i].x] + siz[a[i].y];
  iota(col + 1, col + 1 + m, 1);

  int tot(0);
  while (!is_merged()) boruvka();
  cout << ans;

  return 0;
}

Details

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 35ms
memory: 249816kb

Subtask #2:

score: 0
Skipped

Dependency #1:

0%

Subtask #3:

score: 0
Skipped

Dependency #2:

0%

Subtask #4:

score: 0
Wrong Answer

Test #16:

score: 0
Wrong Answer
time: 77ms
memory: 257204kb

Subtask #5:

score: 0
Runtime Error

Test #21:

score: 0
Runtime Error

Subtask #6:

score: 0
Runtime Error

Test #26:

score: 0
Runtime Error

Subtask #7:

score: 0
Skipped

Dependency #1:

0%