#726404 (C++17) No.1775 Love Triangle 2

• 問題: No.1775 Love Triangle 2
• ユーザー: tko919
• 提出日時: 2021-12-25 04:05:37
• 言語: C++17 (gcc 13.2.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 1,992 ms / 8,000 ms
• コード長: 3,114 bytes
• コンパイル時間: 2,755 ms
• コンパイル使用メモリ: 224,812 KB
• 実行使用メモリ: 4,932 KB
• 最終ジャッジ日時: 2023-10-20 09:12:31
• 合計ジャッジ時間: 79,250 ms
• ジャッジサーバーID （参考情報）: judge14 / judge15

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 4,348 KB
testcase_01	AC	3 ms; 4,348 KB
testcase_02	AC	3 ms; 4,348 KB
testcase_03	AC	3 ms; 4,348 KB
testcase_04	AC	1,992 ms; 4,932 KB
testcase_05	AC	1,988 ms; 4,932 KB
testcase_06	AC	1,962 ms; 4,932 KB
testcase_07	AC	1,979 ms; 4,932 KB
testcase_08	AC	1,984 ms; 4,932 KB
testcase_09	AC	492 ms; 4,932 KB
testcase_10	AC	552 ms; 4,932 KB
testcase_11	AC	360 ms; 4,932 KB
testcase_12	AC	319 ms; 4,932 KB
testcase_13	AC	239 ms; 4,932 KB
testcase_14	AC	199 ms; 4,932 KB
testcase_15	AC	162 ms; 4,932 KB
testcase_16	AC	142 ms; 4,932 KB
testcase_17	AC	123 ms; 4,932 KB
testcase_18	AC	121 ms; 4,932 KB
testcase_19	AC	454 ms; 4,932 KB
testcase_20	AC	434 ms; 4,932 KB
testcase_21	AC	356 ms; 4,932 KB
testcase_22	AC	298 ms; 4,932 KB
testcase_23	AC	243 ms; 4,932 KB
testcase_24	AC	357 ms; 4,932 KB
testcase_25	AC	297 ms; 4,932 KB
testcase_26	AC	240 ms; 4,932 KB
testcase_27	AC	296 ms; 4,932 KB
testcase_28	AC	218 ms; 4,932 KB
testcase_29	AC	121 ms; 4,932 KB
testcase_30	AC	238 ms; 4,932 KB
testcase_31	AC	477 ms; 4,932 KB
testcase_32	AC	716 ms; 4,932 KB
testcase_33	AC	991 ms; 4,932 KB
testcase_34	AC	983 ms; 4,932 KB
testcase_35	AC	1,190 ms; 4,932 KB
testcase_36	AC	1,412 ms; 4,932 KB
testcase_37	AC	1,607 ms; 4,932 KB
testcase_38	AC	1,912 ms; 4,932 KB
testcase_39	AC	177 ms; 4,932 KB
testcase_40	AC	360 ms; 4,932 KB
testcase_41	AC	510 ms; 4,932 KB
testcase_42	AC	577 ms; 4,932 KB
testcase_43	AC	592 ms; 4,932 KB
testcase_44	AC	410 ms; 4,932 KB
testcase_45	AC	1,095 ms; 4,932 KB
testcase_46	AC	667 ms; 4,932 KB
testcase_47	AC	277 ms; 4,932 KB
testcase_48	AC	801 ms; 4,932 KB
testcase_49	AC	119 ms; 4,932 KB
testcase_50	AC	236 ms; 4,932 KB
testcase_51	AC	469 ms; 4,932 KB
testcase_52	AC	700 ms; 4,932 KB
testcase_53	AC	970 ms; 4,932 KB
testcase_54	AC	983 ms; 4,932 KB
testcase_55	AC	1,179 ms; 4,932 KB
testcase_56	AC	1,403 ms; 4,932 KB
testcase_57	AC	1,612 ms; 4,932 KB
testcase_58	AC	1,917 ms; 4,932 KB
testcase_59	AC	200 ms; 4,932 KB
testcase_60	AC	300 ms; 4,932 KB
testcase_61	AC	410 ms; 4,932 KB
testcase_62	AC	280 ms; 4,932 KB
testcase_63	AC	358 ms; 4,932 KB
testcase_64	AC	474 ms; 4,932 KB
testcase_65	AC	240 ms; 4,932 KB
testcase_66	AC	456 ms; 4,932 KB
testcase_67	AC	646 ms; 4,932 KB
testcase_68	AC	350 ms; 4,932 KB
testcase_69	AC	722 ms; 4,932 KB
testcase_70	AC	1,433 ms; 4,932 KB
testcase_71	AC	1,691 ms; 4,932 KB
testcase_72	AC	1,918 ms; 4,932 KB
testcase_73	AC	1,804 ms; 4,932 KB
testcase_74	AC	1,945 ms; 4,932 KB
testcase_75	AC	1,965 ms; 4,932 KB
testcase_76	AC	1,712 ms; 4,932 KB
testcase_77	AC	1,911 ms; 4,932 KB
testcase_78	AC	1,942 ms; 4,932 KB
testcase_79	AC	548 ms; 4,932 KB
testcase_80	AC	621 ms; 4,932 KB
testcase_81	AC	904 ms; 4,932 KB
testcase_82	AC	822 ms; 4,932 KB
testcase_83	AC	1,014 ms; 4,932 KB
testcase_84	AC	745 ms; 4,932 KB
testcase_85	AC	991 ms; 4,932 KB
testcase_86	AC	635 ms; 4,932 KB
testcase_87	AC	923 ms; 4,932 KB
testcase_88	AC	1,459 ms; 4,932 KB
testcase_89	AC	1,267 ms; 4,932 KB

ソースコード

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