結果

問題 No.1775 Love Triangle 2
ユーザー tko919tko919
提出日時 2021-12-25 04:05:37
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 2,473 ms / 8,000 ms
コード長 3,114 bytes
コンパイル時間 2,822 ms
コンパイル使用メモリ 218,664 KB
最終ジャッジ日時 2025-01-27 06:15:14
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 90
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

#define rep(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define ALL(v) (v).begin(),(v).end()
using ll=long long int;
const int inf = 0x3fffffff; const ll INF = 0x1fffffffffffffff; const double eps=1e-12;
template<typename T>inline bool chmax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
template<typename T>inline bool chmin(T& a,T b){if(a>b){a=b;return 1;}return 0;}

using ull=unsigned long long;
struct NimberManager{
    ull memo[256][256];
    NimberManager(){
        rep(i,0,256)rep(j,0,256)memo[i][j]=256;
        memo[0][0]=memo[0][1]=memo[1][0]=0;
        memo[1][1]=1;
        rep(i,0,256)rep(j,0,256)memo[i][j]=mul(i,j,8);
    }
    ull mul(ull x,ull y,int k=64){
        if(k<=8&&memo[x][y]<256)return memo[x][y];
        k>>=1;
        ull a=x>>k,b=x^(a<<k),c=y>>k,d=y^(c<<k);
        ull ac=mul(a,c,k),bd=mul(b,d,k),abcd=mul(a^b,c^d,k);
        return mul(ac,1ull<<(k-1),k)^(abcd^bd)<<k^bd;
    }
};
NimberManager Nim;
struct Nimber{
    ull v;
    Nimber(ull _v=0):v(_v){}
    Nimber& operator+=(const Nimber& x){v^=x.v; return *this;}
    Nimber& operator-=(const Nimber& x){v^=x.v; return *this;}
    Nimber& operator*=(const Nimber& x){v=Nim.mul(v,x.v); return *this;}
    Nimber operator+(const Nimber& x)const{return Nimber(*this)+=x;}
    Nimber operator-(const Nimber& x)const{return Nimber(*this)-=x;}
    Nimber operator*(const Nimber& x)const{return Nimber(*this)*=x;}
    bool operator==(const Nimber& x)const{return v==x.v;}
    bool operator!=(const Nimber& x)const{return v!=x.v;}
    friend istream& operator>>(istream& is,Nimber& x){return is>>x.v;}
    friend ostream& operator<<(ostream& os,const Nimber& x){return os<<x.v;}
};

struct XorShift{
    random_device rnd;
    unsigned x=123456789,y=362436069,z=521288629,w=rnd();
    XorShift(){}
    unsigned run(){
        unsigned t=x^(x<<11);
        x=y,y=z,z=w;
        return w=(w^(w<<19))^(t^(t>>8));
    }
};

int main(){
    int n,m;
    cin>>n>>m;
    int x,y,z;
    cin>>x>>y>>z;
    x--; y--; z--;

    XorShift rnd;
    Nimber w[n][n];
    rep(i,0,n)rep(j,0,i){
        w[i][j]=w[j][i]=(ull(rnd.run())<<32)|rnd.run();
    }
    rep(_,0,m){
        int a,b;
        cin>>a>>b;
        a--; b--;
        w[a][b]=w[b][a]=0;
    }

    Nimber dp[2][2][2][n][n];
    // used y,z, current, previous
    int par=0;
    dp[par][0][0][x][x]=1;
    rep(len,1,n+1){
        rep(p,0,2)rep(q,0,2)rep(r,0,n)rep(s,0,n)dp[par^1][p][q][r][s]=0;
        rep(uy,0,2)rep(uz,0,2)rep(cur,0,n)rep(pre,0,n){
            rep(nxt,0,n){
                int nuy=uy,nuz=uz;
                if(uy and nxt==y)continue;
                if(uz and nxt==z)continue;
                if(pre==nxt)continue;
                if(nxt==y)nuy=1;
                if(nxt==z)nuz=1;
                dp[par^1][nuy][nuz][nxt][cur]+=dp[par][uy][uz][cur][pre];
            }
        }
        rep(p,0,2)rep(q,0,2)rep(r,0,n)rep(s,0,n)dp[par^1][p][q][r][s]*=w[r][s];
        par^=1;
        rep(pre,0,n)if(dp[par][1][1][x][pre].v){
            cout<<len<<'\n';
            return 0;
        }
    }
    puts("-1");
    return 0;
}
0