제출 #969208

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
969208		kilkuwu	Duathlon (APIO18_duathlon)	C++17	100 / 100	91 ms	32404 KiB

count_triplets

#include <bits/stdc++.h>

#define nl '\n'
#ifdef LOCAL
#include "template/debug.hpp"
#else
#define dbg(...) ;
#define timer(...) ;
#endif

signed main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  
  int n, m;
  std::cin >> n >> m;
  std::vector<std::vector<int>> adj(n);

  for (int i = 0; i < m; i++) {
    int u, v;
    std::cin >> u >> v;
    --u, --v;
    adj[u].push_back(v);
    adj[v].push_back(u);
  }

  std::vector<int> st(n, -1), lo(n, -1);
  int ti = 0;

  std::stack<int> stk;

  std::vector<std::vector<int>> g(n);

  auto add_edge = [&](int u, int v) {
    g[u].emplace_back(v);
    g[v].emplace_back(u);
  };

  int cnt = 0;

  std::vector<int> cnt_bcc(n);

  auto dfs = [&](auto self, int u, int p) -> void {
    dbg(u, p);
    cnt++;
    st[u] = lo[u] = ti++;
    stk.push(u);
    
    for (int v : adj[u]) {
      if (v == p) continue;
      if (st[v] == -1) {
        self(self, v, u);
        lo[u] = std::min(lo[u], lo[v]);

        if (lo[v] >= st[u]) {
          g.emplace_back(); // new comp
          add_edge(g.size() - 1, u);
          int lst = u;
          while (lst != v) {
            lst = stk.top();
            add_edge(lst, g.size() - 1);
            stk.pop();
          }
        }
      } else {
        lo[u] = std::min(lo[u], st[v]);
      }
    }
  };

  int64_t ans = 0;
  auto dfs2 = [&](auto self, int u, int p) -> int {
    int sz = u < n;
    for (int v : g[u]) {
      if (v == p) continue;
      int szv = self(self, v, u);
      sz += szv;
      if (u >= n) {
        ans -= 1LL * szv * (szv - 1) * (g[u].size() - 1);
      }
    }

    if (u >= n) {
      ans -= 1LL * (cnt - sz) * (cnt - sz - 1) * (g[u].size() - 1);
    }
    return sz;
  };

  for (int i = 0; i < n; i++) {
    if (st[i] == -1) {
      cnt = 0;
      dfs(dfs, i, i);
      ans += 1LL * cnt * (cnt - 1) * (cnt - 2);
      dfs2(dfs2, i, i);
    }
  }

  std::cout << ans << nl;
}

• 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