test/yosupo/enumerate_triangles.test.cpp

• View this file on GitHub
• Last update: 2020-10-27 16:52:37+09:00
• Problem: https://judge.yosupo.jp/problem/enumerate_triangles

Depends on

• graph/triangle.cpp

Code

// 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;
}

Back to top page