Submission #963768

#	Time	Username	Problem	Language	Result	Execution time	Memory
963768		four_specks	Duathlon (APIO18_duathlon)	C++17	0 / 100	90 ms	38812 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>>;

struct DSU {
  DSU(int n) : e(n, -1) {}

  int find(int x) {
    return e[x] < 0 ? x : e[x] = find(e[x]);
  }

  bool same(int x, int y) {
    return find(x) == find(y);
  }

  bool unite(int x, int y) {
    x = find(x);
    y = find(y);
    if (x == y) {
      return false;
    }
    if (e[x] > e[y]) {
      swap(x, y);
    }
    e[x] += e[y];
    e[y] = x;
    return true;
  }

  int size(int x) {
    return -e[find(x)];
  }

  int size() const {
    return (int)e.size();
  }

 private:
  vector<int> e;
};

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);
  DSU dsu(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]);
        dsu.unite(id[u], j);
      }
    }
  }
  YCombinator dfs = [&](auto self, int i, int p) -> int {
    for (int j : bc_tree[i]) {
      if (j != p) {
        sub[i] += self(j, i);
      }
    }
    return sub[i];
  };
  long ans = 0;
  for (int i = 0; i < l; i++) {
    if (dsu.find(i) == i) {
      int k = dfs(i, -1);
      ans += (long)k * (k - 1) * (k - 2);
    }
  }
  for (int u : art) {
    int k = sub[dsu.find(u)];
    for (int j : bc_tree[id[u]]) {
      int x = (int)bcc[j - art_sz].size() - 1, y = (sub[id[u]] > sub[j] ? k - 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:61:76: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   61 | 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