This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub suisen-cp/cp-library-cpp
#define PROBLEM "https://atcoder.jp/contests/abc258/tasks/abc258_g" #include <iostream> #include "library/graph/enumerate_triangles.hpp" int main() { int n; std::cin >> n; std::vector<std::vector<int>> g(n); for (int u = 0; u < n; ++u) { std::string s; std::cin >> s; for (int v = 0; v < n; ++v) if (s[v] == '1') { g[u].push_back(v); } } long long ans = 0; suisen::enumerate_triangles(g, [&ans](int, int, int) { ++ans; }); std::cout << ans << std::endl; return 0; }
#line 1 "test/src/graph/enumerate_triangles/abc258_g.test.cpp" #define PROBLEM "https://atcoder.jp/contests/abc258/tasks/abc258_g" #include <iostream> #line 1 "library/graph/enumerate_triangles.hpp" #include <algorithm> #include <vector> namespace suisen { /** * Type Parameters * - TriangleConsumer : type of consumer function (int, int, int) -> void * * Parameters * - std::vector<std::vector<int>> g : simple undirected graph * - TriangleConsumer fun * * Requirements * - v in g[u] <=> u in g[v] * * Complexity * - time : O(N + M^{3/2}) * - space : O(N + M) */ template <typename TriangleConsumer> void enumerate_triangles(std::vector<std::vector<int>> g, TriangleConsumer &&fun) { const int n = g.size(); std::vector<int> cnt(n + 1); for (int i = 0; i < n; ++i) ++cnt[g[i].size() + 1]; for (int i = 0; i < n; ++i) cnt[i + 1] += cnt[i]; std::vector<int> ord(n), idx(n); for (int i = 0; i < n; ++i) ord[idx[i] = cnt[g[i].size()]++] = i; for (int i = 0; i < n; ++i) g[i].erase(std::remove_if(g[i].begin(), g[i].end(), [&](int j) { return idx[j] < idx[i]; }), g[i].end()); std::vector<int8_t> exists(n, false); for (int i : ord) { for (int j : g[i]) exists[j] = true; for (int j : g[i]) for (int k : g[j]) if (exists[k]) fun(i, j, k); for (int j : g[i]) exists[j] = false; } } } // namespace suisen #line 6 "test/src/graph/enumerate_triangles/abc258_g.test.cpp" int main() { int n; std::cin >> n; std::vector<std::vector<int>> g(n); for (int u = 0; u < n; ++u) { std::string s; std::cin >> s; for (int v = 0; v < n; ++v) if (s[v] == '1') { g[u].push_back(v); } } long long ans = 0; suisen::enumerate_triangles(g, [&ans](int, int, int) { ++ans; }); std::cout << ans << std::endl; return 0; }