This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub beet-aizu/library
// verification-helper: PROBLEM https://judge.yosupo.jp/problem/enumerate_triangles #include <bits/stdc++.h> using namespace std; #define call_from_test #include "../../graph/triangle.cpp" #undef call_from_test signed main(){ cin.tie(0); ios::sync_with_stdio(0); using ll = long long; int n,m; cin>>n>>m; vector<ll> xs(n); for(int i=0;i<n;i++) cin>>xs[i]; Triangle G(n); for(int i=0;i<m;i++){ int u,v; cin>>u>>v; G.add_edge(u,v); } const ll mod = 998244353; ll ans=0; auto f=[&](int x,int y,int z){ ans+=xs[x]*xs[y]%mod*xs[z]%mod; ans%=mod; }; G.build(f); cout<<ans<<endl; return 0; }
#line 1 "test/yosupo/enumerate_triangles.test.cpp" // verification-helper: PROBLEM https://judge.yosupo.jp/problem/enumerate_triangles #include <bits/stdc++.h> using namespace std; #define call_from_test #line 1 "graph/triangle.cpp" #line 3 "graph/triangle.cpp" using namespace std; #endif //BEGIN CUT HERE struct Triangle{ // if not simple, use vector<set<int>> vector<vector<int>> G; Triangle(int n):G(n){} void add_edge(int u,int v){ G[u].emplace_back(v); G[v].emplace_back(u); } template<typename F> void build(F f){ int n=G.size(); using P = pair<int, int>; vector<P> vp(n); for(int i=0;i<n;i++) vp[i]=P(G[i].size(),i); vector<vector<int>> H(n); for(int i=0;i<n;i++) for(int j:G[i]) if(vp[i]>vp[j]) H[i].emplace_back(j); vector<int> used(n,0); // x->y->z for(int x=0;x<n;x++){ for(int z:H[x]) used[z]=1; for(int y:H[x]) for(int z:H[y]) if(used[z]) f(x,y,z); for(int z:H[x]) used[z]=0; } } }; //END CUT HERE #ifndef call_from_test //INSERT ABOVE HERE signed main(){ return 0; } #endif #line 8 "test/yosupo/enumerate_triangles.test.cpp" #undef call_from_test signed main(){ cin.tie(0); ios::sync_with_stdio(0); using ll = long long; int n,m; cin>>n>>m; vector<ll> xs(n); for(int i=0;i<n;i++) cin>>xs[i]; Triangle G(n); for(int i=0;i<m;i++){ int u,v; cin>>u>>v; G.add_edge(u,v); } const ll mod = 998244353; ll ans=0; auto f=[&](int x,int y,int z){ ans+=xs[x]*xs[y]%mod*xs[z]%mod; ans%=mod; }; G.build(f); cout<<ans<<endl; return 0; }