oj.uz

Submission #963768

# Submission time Handle Problem Language Result Execution time Memory
963768 2024-04-15T15:55:47 Z four_specks Duathlon (APIO18_duathlon) C++17
0 / 100
 90 ms 38812 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>>;

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

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

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 460 KB Output is correct
8 Runtime error 1 ms 600 KB Execution killed with signal 6
9 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 460 KB Output is correct
8 Runtime error 1 ms 600 KB Execution killed with signal 6
9 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 25300 KB Output is correct
2 Correct 43 ms 25300 KB Output is correct
3 Correct 60 ms 22136 KB Output is correct
4 Runtime error 62 ms 38812 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -

Subtask #4
0 / 10.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 604 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 1 ms 708 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 600 KB Output is correct
10 Incorrect 1 ms 600 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 19552 KB Output is correct
2 Correct 64 ms 19956 KB Output is correct
3 Correct 64 ms 19308 KB Output is correct
4 Correct 66 ms 19188 KB Output is correct
5 Correct 90 ms 19392 KB Output is correct
6 Correct 80 ms 29880 KB Output is correct
7 Correct 74 ms 25504 KB Output is correct
8 Correct 76 ms 23668 KB Output is correct
9 Correct 69 ms 22824 KB Output is correct
10 Incorrect 66 ms 19444 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #6
0 / 15.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 1 ms 604 KB Output is correct
5 Runtime error 1 ms 860 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 19696 KB Output is correct
2 Correct 79 ms 19556 KB Output is correct
3 Correct 67 ms 17740 KB Output is correct
4 Correct 56 ms 15348 KB Output is correct
5 Runtime error 53 ms 17420 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 460 KB Output is correct
8 Runtime error 1 ms 600 KB Execution killed with signal 6
9 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 460 KB Output is correct
8 Runtime error 1 ms 600 KB Execution killed with signal 6
9 Halted 0 ms 0 KB -