oj.uz

Submission #963652

# Submission time Handle Problem Language Result Execution time Memory
963652 2024-04-15T12:25:17 Z four_specks Duathlon (APIO18_duathlon) C++17
0 / 100
 70 ms 25268 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 48 ms 25268 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 2 ms 604 KB Output is correct
5 Correct 1 ms 600 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Incorrect 1 ms 604 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 69 ms 19184 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 604 KB Output is correct
13 Correct 1 ms 604 KB Output is correct
14 Correct 1 ms 604 KB Output is correct
15 Correct 1 ms 604 KB Output is correct
16 Incorrect 1 ms 604 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 70 ms 19804 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -