結果

問題 No.1775 Love Triangle 2
コンテスト
ユーザー Taiki0715
提出日時 2026-01-30 21:57:25
言語 C++23
(gcc 15.2.0 + boost 1.89.0)
結果
WA  
実行時間 -
コード長 5,803 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 6,149 ms
コンパイル使用メモリ 457,248 KB
実行使用メモリ 7,968 KB
最終ジャッジ日時 2026-01-30 21:58:07
合計ジャッジ時間 41,107 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 73 WA * 17
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using ull=unsigned long long;
using P=pair<ll,ll>;
template<typename T>using minque=priority_queue<T,vector<T>,greater<T>>;
template<typename T>bool chmax(T &a,const T &b){return (a<b?(a=b,true):false);}
template<typename T>bool chmin(T &a,const T &b){return (a>b?(a=b,true):false);}
template<typename T1,typename T2>istream &operator>>(istream &is,pair<T1,T2>&p){is>>p.first>>p.second;return is;}
template<typename T1,typename T2,typename T3>istream &operator>>(istream &is,tuple<T1,T2,T3>&a){is>>std::get<0>(a)>>std::get<1>(a)>>std::get<2>(a);return is;}
template<typename T,size_t n>istream &operator>>(istream &is,array<T,n>&a){for(auto&i:a)is>>i;return is;}
template<typename T>istream &operator>>(istream &is,vector<T> &a){for(auto &i:a)is>>i;return is;}
template<typename T1,typename T2>void operator++(pair<T1,T2>&a,int n){a.first++,a.second++;}
template<typename T1,typename T2>void operator--(pair<T1,T2>&a,int n){a.first--,a.second--;}
template<typename T>void operator++(vector<T>&a,int n){for(auto &i:a)i++;}
template<typename T>void operator--(vector<T>&a,int n){for(auto &i:a)i--;}
#define overload3(_1,_2,_3,name,...) name
#define rep1(i,n) for(int i=0;i<(int)(n);i++)
#define rep2(i,l,r) for(int i=(int)(l);i<(int)(r);i++)
#define rep(...) overload3(__VA_ARGS__,rep2,rep1)(__VA_ARGS__)
#define reps(i,l,r) rep2(i,l,r)
#define all(x) x.begin(),x.end()
#define pcnt(x) __builtin_popcountll(x)
#define fin(x) return cout<<(x)<<'\n',static_cast<void>(0)
#define yn(x) cout<<((x)?"Yes\n":"No\n")
#define uniq(x) sort(all(x)),x.erase(unique(all(x)),x.end())
template<typename T>
inline int fkey(vector<T>&z,T key){return lower_bound(z.begin(),z.end(),key)-z.begin();}
ll myceil(ll a,ll b){return (a+b-1)/b;}
template<typename T,size_t n,size_t id=0>
auto vec(const int (&d)[n],const T &init=T()){
  if constexpr (id<n)return vector(d[id],vec<T,n,id+1>(d,init));
  else return init;
}
#ifdef LOCAL
#include<debug.h>
#define SWITCH(a,b) (a)
#else
#define debug(...) static_cast<void>(0)
#define debugg(...) static_cast<void>(0)
#define SWITCH(a,b) (b)
template<typename T1,typename T2>ostream &operator<<(ostream &os,const pair<T1,T2>&p){os<<p.first<<' '<<p.second;return os;}
#endif
struct Timer{
  clock_t start;
  Timer(){
    start=clock();
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout<<fixed<<setprecision(16);
  }
  inline double now(){return (double)(clock()-start)/1000;}
  #ifdef LOCAL
  ~Timer(){
    cerr<<"time:";
    cerr<<now();
    cerr<<"ms\n";
  }
  #endif
}timer;
void SOLVE();
int main(){
  int testcase=1;
  //cin>>testcase;
  for(int i=0;i<testcase;i++){
    SOLVE();
  }
}
#include<concepts>
#include<immintrin.h>
struct gf2{
private:
  unsigned long long v;
  static constexpr unsigned long long table[16]={0,27,45,54,90,65,119,108,175,180,130,153,245,238,216,195};
public:
  gf2():v(){}
  template<std::integral T>
  gf2(T x):v(x){}
  inline gf2 operator+()const{return *this;}
  inline gf2 operator-()const{return *this;}
  inline gf2 &operator+=(const gf2&rhs){v^=rhs.v;return *this;}
  inline gf2 &operator-=(const gf2&rhs){v^=rhs.v;return *this;}
  __attribute__((target("pclmul,sse4.2")))
  inline gf2 &operator*=(const gf2&rhs){
    __m128i m=_mm_clmulepi64_si128(_mm_set_epi64x(0,v),_mm_set_epi64x(0,rhs.v),0);
    unsigned long long high=_mm_extract_epi64(m,1);
    unsigned long long low=_mm_extract_epi64(m,0);
    v=high^(high<<1);
    low^=v^(v<<3);
    v=low^table[high>>60];
    return *this;
  }
  inline gf2 &operator/=(const gf2&rhs){return *this*=rhs.inv();}
  friend gf2 operator+(const gf2&lhs,const gf2&rhs){return gf2(lhs)+=rhs;}
  friend gf2 operator-(const gf2&lhs,const gf2&rhs){return gf2(lhs)-=rhs;}
  friend gf2 operator*(const gf2&lhs,const gf2&rhs){return gf2(lhs)*=rhs;}
  friend gf2 operator/(const gf2&lhs,const gf2&rhs){return gf2(lhs)/=rhs;}
  auto operator<=>(const gf2&)const=default;
  gf2 pow(unsigned long long k)const{
    gf2 res=1,a=*this;
    while(k){
      if(k&1)res*=a;
      a*=a;
      k>>=1;
    }
    return res;
  }
  inline gf2 inv()const{return pow(-2);}
  unsigned long long val()const{return v;}
  friend std::istream &operator>>(std::istream&is,gf2&rhs){is>>rhs.v;return is;}
  friend std::ostream &operator<<(std::ostream&os,const gf2&rhs){os<<rhs.v;return os;}
};
#include<type_traits>
namespace Random{
  std::mt19937_64 mt(std::random_device{}());
  template<typename T>inline std::enable_if_t<std::is_integral_v<T>,T> get(){return mt();}
  template<typename T>inline std::enable_if_t<std::is_floating_point_v<T>,T> get(){return T(mt())/T(-1ull);}
  template<typename T>inline std::enable_if_t<std::is_integral_v<T>,T>range(T n){return mt()%n;}
  template<typename T>inline std::enable_if_t<std::is_integral_v<T>,T>range(T l,T r){return l+mt()%(r-l);}
  template<typename T>inline std::enable_if_t<std::is_integral_v<T>,std::pair<T,T>>distinct(T n){
    T l=mt()%n,r=mt()%(n-1);
    if(l==r)r++;
    if(l>r)std::swap(l,r);
    return std::make_pair(l,r);
  }
}
void SOLVE(){
  int n,m;
  cin>>n>>m;
  int x,y,z;
  cin>>x>>y>>z;
  x--,y--,z--;
  vector<vector<bool>>edge(n,vector<bool>(n));
  rep(i,m){
    int u,v;
    cin>>u>>v;
    u--,v--;
    edge[u][v]=edge[v][u]=true;
  }
  vector<vector<gf2>>g(n,vector<gf2>(n));
  rep(i,n)rep(j,i+1,n)if(!edge[i][j]){
    g[i][j]=g[j][i]=Random::get<ull>();
    if(i==x||j==x)g[j][i]=Random::get<ull>();
  }
  auto dp=vec<gf2>({4,n,n});
  dp[0][x][x]=Random::get<ull>();
  vector<int>mask(n);
  mask[y]=1,mask[z]=2;
  rep(len,1,n+1){
    auto ndp=vec<gf2>({4,n,n});
    rep(i,4)rep(j,n)rep(k,n){
      rep(l,n)if(j!=l&&!edge[k][l]){
        ndp[i|mask[l]][k][l]+=dp[i][j][k]*g[k][l];
      }
    }
    dp=move(ndp);
    rep(i,n)if(dp[3][i][x].val())fin(len);
  }
  cout<<"-1\n";
}
0