Submission #255454

#	Time	Username	Problem	Language	Result	Execution time	Memory
255454		EntityIT	Duathlon (APIO18_duathlon)	C++14	100 / 100	303 ms	28472 KiB

count_triplets

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

#define ALL(x) (x).begin(), (x).end()
#define SZ(x) static_cast<int>((x).size())

template<class T, size_t D>
struct vec : vector<vec<T, D - 1>> {
  template<class... Args>
  vec(size_t n = 0, Args... args)
      : vector<vec<T, D - 1>>(n, vec<T, D - 1>(args...)) {}
};
template<class T>
struct vec<T, 1> : vector<T> {
  template<class... Args>
  vec(Args... args)
      : vector<T>(args...) {}
};

template<class T>
inline bool Minimize(T& a, const T& b) { return a > b ? a = b, true : false; }
template<class T>
inline bool Maximize(T& a, const T& b) { return a < b ? a = b, true : false; }
inline int Next(int i, int n) { return i == n - 1 ? 0 : i + 1; }
inline int Prev(int i, int n) { return !i ? n - 1 : i - 1; }

mt19937 rng(static_cast<uint32_t>(chrono::steady_clock::now().time_since_epoch().count()));

int main() {
  ios_base::sync_with_stdio(0); cin.tie(0);

  int n_vertices, n_edges; cin >> n_vertices >> n_edges;
  vec<int, 2> neighbors_vertices(n_vertices);
  while (n_edges--) {
    int u, v; cin >> u >> v; --u; --v;
    neighbors_vertices[u].emplace_back(v);
    neighbors_vertices[v].emplace_back(u);
  }

  vec<int, 1> parents(n_vertices, -1), discoveries(n_vertices, -1), earliests(n_vertices, -1);
  int n_vertices_block_cut_tree = n_vertices;
  vec<int, 2> neighbors_vertices_block_cut_tree(n_vertices);
  function<void(int)> ConstructBlockCutTree = [&](int u) {
    static int current_discovery = -1;
    static stack<pair<int, int>> current_edges;

    discoveries[u] = earliests[u] = ++current_discovery;
    for (auto& v : neighbors_vertices[u]) {
      if (!~discoveries[v]) {
        parents[v] = u;
        current_edges.emplace(u, v);
        ConstructBlockCutTree(v);
        Minimize(earliests[u], earliests[v]);

        if (earliests[v] >= discoveries[u]) {
          vec<int, 1> vertices;
          do {
            vertices.emplace_back(current_edges.top().first);
            vertices.emplace_back(current_edges.top().second);
            current_edges.pop();
          } while (vertices.rbegin()[1] != u || vertices.back() != v);
          sort(ALL(vertices)); vertices.erase(unique(ALL(vertices)), vertices.end());
          neighbors_vertices_block_cut_tree.emplace_back(vec<int, 1>());
          for (auto& vertex : vertices) {
            neighbors_vertices_block_cut_tree[vertex].emplace_back(n_vertices_block_cut_tree);
            neighbors_vertices_block_cut_tree[n_vertices_block_cut_tree].emplace_back(vertex);
          }
          ++n_vertices_block_cut_tree;
        }
      } else if (v != parents[u] && discoveries[v] < discoveries[u]) {
        current_edges.emplace(u, v);
        Minimize(earliests[u], discoveries[v]);
      }
    }
  };
  for (int u = 0; u < n_vertices; ++u) {
    if (!~discoveries[u]) {
      ConstructBlockCutTree(u);
    }
  }

  int64_t answer = 0;
  vec<int, 1> a(n_vertices_block_cut_tree), tmp_vertices;
  vec<char, 1> visited(n_vertices_block_cut_tree);
  function<int(int, int)> Solve = [&](int u, int parent) {
    visited[u] = true;
    a[u] = (u < n_vertices);
    for (auto& v : neighbors_vertices_block_cut_tree[u]) {
      if (v == parent) {
        continue;
      }
      a[u] += Solve(v, u);
      if (u >= n_vertices) {
        answer -= static_cast<int64_t>(SZ(neighbors_vertices_block_cut_tree[u]) - 1) * a[v] * (a[v] - 1);
      }
    }
    if (u >= n_vertices) {
      tmp_vertices.emplace_back(u);
    }
    return a[u];
  };
  for (int u = 0; u < n_vertices_block_cut_tree; ++u) {
    if (visited[u]) {
      continue;
    }
    auto tmp_n_vertices = Solve(u, -1);
    answer += static_cast<int64_t>(tmp_n_vertices) * (tmp_n_vertices - 1) * (tmp_n_vertices - 2);
    for (auto& vertex : tmp_vertices) {
      answer -= static_cast<int64_t>(SZ(neighbors_vertices_block_cut_tree[vertex]) - 1) * (tmp_n_vertices - a[vertex]) * ((tmp_n_vertices - a[vertex]) - 1);
    }
    tmp_vertices.clear();
  }

  cout << answer << '\n';

  return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 11 / 11
• Subtask 3: 8 / 8
• Subtask 4: 10 / 10
• Subtask 5: 13 / 13
• Subtask 6: 15 / 15
• Subtask 7: 20 / 20
• Subtask 8: 8 / 8
• Subtask 9: 10 / 10