graph/count/count_P3_P4.hpp

• View this file on GitHub
• Last update: 2023-10-24 13:35:16+09:00
• Include: #include "graph/count/count_P3_P4.hpp"
• Link: https://atcoder.jp/contests/tkppc2/tasks/tkppc2016_h
• Link: https://codeforces.com/contest/51/submission/228823033

Depends on

• graph/count/count_C3_C4.hpp

Code

#include "graph/count/count_C3_C4.hpp"

// 各 v に対して、v を始点とする P3, P4 を数える
// https://atcoder.jp/contests/tkppc2/tasks/tkppc2016_h
// 始終点ごと：https://codeforces.com/contest/51/submission/228823033
template <typename GT>
pair<vi, vi> count_P3_P4_pointwise(GT& G) {
  int N = G.N;
  auto deg = G.deg_array();
  auto [C3, C4] = count_C3_C4_pointwise(G);

  vi P2(N), P3(N), P4(N);
  using ARR = array<ll, 5>;
  vc<ARR> path(N, {1, 0, 0, 0, 0});
  FOR(v, N) path[v][1] = deg[v];

  FOR(v, N) {
    for (auto&& e: G[v]) P2[v] += deg[e.to] - 1;
  }

  FOR(v, N) {
    for (auto&& e: G[v]) { P3[v] += P2[e.to] - (deg[v] - 1); }
    P3[v] -= C3[v] * 2;
  }

  FOR(v, N) {
    for (auto&& e: G[v]) { P4[v] += P3[e.to]; }
    P4[v] -= C4[v] * 2;
    P4[v] -= C3[v] * 2 * (deg[v] - 3);
    P4[v] -= P2[v] * (deg[v] - 1);
  }
  return {P3, P4};
}

#line 1 "graph/count/count_C3_C4.hpp"

// 各点に対して、その点を含む C3, C4 を数える
template <typename GT>
pair<vi, vi> count_C3_C4_pointwise(GT &G) {
  int N = G.N;
  auto deg = G.deg_array();
  auto I = argsort(deg);
  reverse(all(I));
  vc<int> rk(N);
  FOR(i, N) rk[I[i]] = i;

  // 遷移先を降順に並べる
  vvc<int> TO(N);
  for (auto &&e: G.edges) {
    int a = rk[e.frm], b = rk[e.to];
    TO[a].eb(b);
    TO[b].eb(a);
  }
  FOR(v, N) {
    sort(all(TO[v]));
    reverse(all(TO[v]));
  }

  vc<int> A(N);
  vi C3(N), C4(N);
  FOR(a, N) {
    for (auto &&b: TO[a]) TO[b].pop_back();
    for (auto &&b: TO[a]) {
      for (auto &&c: TO[b]) { C4[a] += A[c], C4[c] += A[c], A[c] += 1; }
    }
    for (auto &&b: TO[a]) {
      C3[a] += A[b], C3[b] += A[b] + A[b];
      for (auto &&c: TO[b]) { C4[b] += A[c] - 1; }
    }
    for (auto &&b: TO[a]) {
      for (auto &&c: TO[b]) { A[c] = 0; }
    }
  }
  for (auto &&x: C3) x /= 2;
  C3 = rearrange(C3, rk);
  C4 = rearrange(C4, rk);
  return {C3, C4};
}

// (2e5,5e5) で 500 ms
// https://codeforces.com/gym/104053/problem/K
template <typename GT>
pair<ll, ll> count_C3_C4(GT &G) {
  int N = G.N;
  ll x3 = 0, x4 = 0;
  auto deg = G.deg_array();
  auto I = argsort(deg);
  reverse(all(I));
  vc<int> rk(N);
  FOR(i, N) rk[I[i]] = i;

  // 遷移先を降順に並べる
  vvc<int> TO(N);
  for (auto &&e: G.edges) {
    int a = rk[e.frm], b = rk[e.to];
    TO[a].eb(b);
    TO[b].eb(a);
  }
  FOR(v, N) {
    sort(all(TO[v]));
    reverse(all(TO[v]));
  }

  vc<int> A(N);
  FOR(a, N) {
    for (auto &&b: TO[a]) TO[b].pop_back();
    for (auto &&b: TO[a]) {
      for (auto &&c: TO[b]) { x4 += A[c]++; }
    }
    for (auto &&b: TO[a]) { x3 += A[b]; }
    for (auto &&b: TO[a]) {
      for (auto &&c: TO[b]) { A[c] = 0; }
    }
  }
  x3 /= 2;
  return {x3, x4};
}
#line 2 "graph/count/count_P3_P4.hpp"

// 各 v に対して、v を始点とする P3, P4 を数える
// https://atcoder.jp/contests/tkppc2/tasks/tkppc2016_h
// 始終点ごと：https://codeforces.com/contest/51/submission/228823033
template <typename GT>
pair<vi, vi> count_P3_P4_pointwise(GT& G) {
  int N = G.N;
  auto deg = G.deg_array();
  auto [C3, C4] = count_C3_C4_pointwise(G);

  vi P2(N), P3(N), P4(N);
  using ARR = array<ll, 5>;
  vc<ARR> path(N, {1, 0, 0, 0, 0});
  FOR(v, N) path[v][1] = deg[v];

  FOR(v, N) {
    for (auto&& e: G[v]) P2[v] += deg[e.to] - 1;
  }

  FOR(v, N) {
    for (auto&& e: G[v]) { P3[v] += P2[e.to] - (deg[v] - 1); }
    P3[v] -= C3[v] * 2;
  }

  FOR(v, N) {
    for (auto&& e: G[v]) { P4[v] += P3[e.to]; }
    P4[v] -= C4[v] * 2;
    P4[v] -= C3[v] * 2 * (deg[v] - 3);
    P4[v] -= P2[v] * (deg[v] - 1);
  }
  return {P3, P4};
}

Back to top page