This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub SSRS-cp/cp_library
#define PROBLEM "https://judge.yosupo.jp/problem/enumerate_triangles" #include <bits/stdc++.h> using namespace std; const long long MOD = 998244353; #include "../../../graph/enumerate_triangles.hpp" int main(){ int N, M; cin >> N >> M; vector<long long> x(N); for (int i = 0; i < N; i++){ cin >> x[i]; } vector<vector<int>> E(N); for (int i = 0; i < M; i++){ int u, v; cin >> u >> v; E[u].push_back(v); E[v].push_back(u); } vector<tuple<int, int, int>> T = enumerate_triangles(E); int cnt = T.size(); long long ans = 0; for (int i = 0; i < cnt; i++){ int a = get<0>(T[i]); int b = get<1>(T[i]); int c = get<2>(T[i]); ans += x[a] * x[b] % MOD * x[c] % MOD; ans %= MOD; } cout << ans << endl; }
#line 1 "test/library_checker/graph/enumerate_triangles.test.cpp" #define PROBLEM "https://judge.yosupo.jp/problem/enumerate_triangles" #include <bits/stdc++.h> using namespace std; const long long MOD = 998244353; #line 2 "graph/enumerate_triangles.hpp" /** * @brief 三角形列挙 */ vector<tuple<int, int, int>> enumerate_triangles(vector<vector<int>> &E){ int N = E.size(); vector<int> d(N); for (int i = 0; i < N; i++){ d[i] = E[i].size(); } vector<vector<int>> E2(N); for (int i = 0; i < N; i++){ for (int j : E[i]){ if (d[i] < d[j] || d[i] == d[j] && i < j){ E2[i].push_back(j); } } } vector<bool> flg(N, false); vector<tuple<int, int, int>> ans; for (int i = 0; i < N; i++){ for (int j : E2[i]){ for (int k : E2[i]){ flg[k] = true; } for (int k : E2[j]){ if (flg[k]){ ans.push_back(make_tuple(i, j, k)); } } for (int k : E2[i]){ flg[k] = false; } } } return ans; } #line 6 "test/library_checker/graph/enumerate_triangles.test.cpp" int main(){ int N, M; cin >> N >> M; vector<long long> x(N); for (int i = 0; i < N; i++){ cin >> x[i]; } vector<vector<int>> E(N); for (int i = 0; i < M; i++){ int u, v; cin >> u >> v; E[u].push_back(v); E[v].push_back(u); } vector<tuple<int, int, int>> T = enumerate_triangles(E); int cnt = T.size(); long long ans = 0; for (int i = 0; i < cnt; i++){ int a = get<0>(T[i]); int b = get<1>(T[i]); int c = get<2>(T[i]); ans += x[a] * x[b] % MOD * x[c] % MOD; ans %= MOD; } cout << ans << endl; }