Submission #963652

#	Time	Username	Problem	Language	Result	Execution time	Memory
963652		four_specks	Duathlon (APIO18_duathlon)	C++17	0 / 100	70 ms	25268 KiB

count_triplets

#include <bits/stdc++.h>

using namespace std;

namespace {

template <typename Fun>
struct YCombinator {
  template <typename T>
  YCombinator(T &&_fun) : fun(forward<T>(_fun)) {}

  template <typename... Args>
  decltype(auto) operator()(Args &&...args) {
    return fun(ref(*this), forward<Args>(args)...);
  }

 private:
  Fun fun;
};

template <typename T>
YCombinator(T &&) -> YCombinator<decay_t<T>>;

pair<vector<vector<int>>, vector<int>> biconnected_components(int n, const auto &edges) {
  vector<vector<int>> adj(n);
  for (auto [u, v] : edges) {
    adj[u].push_back(v);
    adj[v].push_back(u);
  }
  vector<int> articulation_points;
  vector<vector<int>> components;
  {
    vector<int> tin(n, -1), low(n);
    stack<int> st;
    int timer = 0;
    auto dfs = [&](auto self, int u, int p) -> void {
      low[u] = tin[u] = timer++;
      st.push(u);
      bool ap = false;
      for (int v : adj[u]) {
        if (tin[v] == -1) {
          self(self, v, u);
          low[u] = min(low[u], low[v]);
          if (low[v] == tin[u]) {
            if (p != -1 || tin[v] > tin[u] + 1) {
              ap = true;
            }
            vector<int> &comp = components.emplace_back();
            comp.push_back(u);
            while (comp.back() != v) {
              comp.push_back(st.top());
              st.pop();
            }
          }
        } else {
          low[u] = min(low[u], tin[v]);
        }
      }
      if (ap) {
        articulation_points.push_back(u);
      }
    };
    for (int u = 0; u < n; u++) {
      if (tin[u] == -1) {
        dfs(dfs, u, -1);
      }
    }
  }
  return pair(components, articulation_points);
}

}  // namespace

void solve() {
  int n, m;
  cin >> n >> m;
  vector<array<int, 2>> edges(m);
  for (auto &[u, v] : edges) {
    cin >> u >> v;
    --u;
    --v;
  }
  auto [bcc, art] = biconnected_components(n, edges);
  int art_sz = (int)art.size(), bcc_sz = (int)bcc.size();
  int l = art_sz + bcc_sz;
  vector id(n, -1);
  vector<vector<int>> bc_tree(l);
  vector<int> sub(l);
  for (int i = 0; i < art_sz; i++) {
    id[art[i]] = i;
    sub[i]++;
  }
  for (int i = 0; i < bcc_sz; i++) {
    int j = art_sz + i;
    for (int u : bcc[i]) {
      if (id[u] == -1) {
        id[u] = j;
        sub[j]++;
      } else {
        bc_tree[id[u]].push_back(j);
        bc_tree[j].push_back(id[u]);
      }
    }
  }
  YCombinator([&](auto self, int i, int p) -> void {
    for (int j : bc_tree[i]) {
      if (j != p) {
        self(j, i);
        sub[i] += sub[j];
      }
    }
  })(0, -1);
  long ans = n * (n - 1) * (n - 2);
  for (int u : art) {
    for (int j : bc_tree[id[u]]) {
      int x = (int)bcc[j - art_sz].size() - 1, y = (sub[id[u]] > sub[j] ? n - sub[j] : sub[id[u]]);
      ans -= (long)x * y * (y - 1);
    }
  }
  cout << ans << '\n';
}

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

  solve();

  return 0;
}

Compilation message (stderr)

count_triplets.cpp:24:76: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   24 | pair<vector<vector<int>>, vector<int>> biconnected_components(int n, const auto &edges) {
      |                                                                            ^~~~

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