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

提出ソース

結果

問題	No.1775 Love Triangle 2
ユーザー	tko919
提出日時	2021-12-25 04:05:37
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	1,933 ms / 8,000 ms
コード長	3,114 bytes
コンパイル時間	3,022 ms
コンパイル使用メモリ	223,784 KB
実行使用メモリ	5,376 KB
最終ジャッジ日時	2024-09-20 04:41:18
合計ジャッジ時間	72,304 ms
ジャッジサーバーID （参考情報）	judge1 / judge4

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 5,248 KB
testcase_01	AC	2 ms 5,376 KB
testcase_02	AC	2 ms 5,376 KB
testcase_03	AC	3 ms 5,376 KB
testcase_04	AC	1,933 ms 5,376 KB
testcase_05	AC	1,851 ms 5,376 KB
testcase_06	AC	1,875 ms 5,376 KB
testcase_07	AC	1,850 ms 5,376 KB
testcase_08	AC	1,831 ms 5,376 KB
testcase_09	AC	467 ms 5,376 KB
testcase_10	AC	518 ms 5,376 KB
testcase_11	AC	336 ms 5,376 KB
testcase_12	AC	299 ms 5,376 KB
testcase_13	AC	228 ms 5,376 KB
testcase_14	AC	186 ms 5,376 KB
testcase_15	AC	151 ms 5,376 KB
testcase_16	AC	135 ms 5,376 KB
testcase_17	AC	120 ms 5,376 KB
testcase_18	AC	114 ms 5,376 KB
testcase_19	AC	435 ms 5,376 KB
testcase_20	AC	429 ms 5,376 KB
testcase_21	AC	347 ms 5,376 KB
testcase_22	AC	287 ms 5,376 KB
testcase_23	AC	231 ms 5,376 KB
testcase_24	AC	346 ms 5,376 KB
testcase_25	AC	285 ms 5,376 KB
testcase_26	AC	231 ms 5,376 KB
testcase_27	AC	278 ms 5,376 KB
testcase_28	AC	211 ms 5,376 KB
testcase_29	AC	119 ms 5,376 KB
testcase_30	AC	236 ms 5,376 KB
testcase_31	AC	447 ms 5,376 KB
testcase_32	AC	659 ms 5,376 KB
testcase_33	AC	920 ms 5,376 KB
testcase_34	AC	918 ms 5,376 KB
testcase_35	AC	1,114 ms 5,376 KB
testcase_36	AC	1,345 ms 5,376 KB
testcase_37	AC	1,504 ms 5,376 KB
testcase_38	AC	1,802 ms 5,376 KB
testcase_39	AC	169 ms 5,376 KB
testcase_40	AC	331 ms 5,376 KB
testcase_41	AC	480 ms 5,376 KB
testcase_42	AC	559 ms 5,376 KB
testcase_43	AC	558 ms 5,376 KB
testcase_44	AC	392 ms 5,376 KB
testcase_45	AC	1,036 ms 5,376 KB
testcase_46	AC	630 ms 5,376 KB
testcase_47	AC	264 ms 5,376 KB
testcase_48	AC	729 ms 5,376 KB
testcase_49	AC	112 ms 5,376 KB
testcase_50	AC	222 ms 5,376 KB
testcase_51	AC	433 ms 5,376 KB
testcase_52	AC	662 ms 5,376 KB
testcase_53	AC	917 ms 5,376 KB
testcase_54	AC	926 ms 5,376 KB
testcase_55	AC	1,119 ms 5,376 KB
testcase_56	AC	1,315 ms 5,376 KB
testcase_57	AC	1,518 ms 5,376 KB
testcase_58	AC	1,806 ms 5,376 KB
testcase_59	AC	190 ms 5,376 KB
testcase_60	AC	277 ms 5,376 KB
testcase_61	AC	383 ms 5,376 KB
testcase_62	AC	260 ms 5,376 KB
testcase_63	AC	331 ms 5,376 KB
testcase_64	AC	440 ms 5,376 KB
testcase_65	AC	227 ms 5,376 KB
testcase_66	AC	420 ms 5,376 KB
testcase_67	AC	610 ms 5,376 KB
testcase_68	AC	328 ms 5,376 KB
testcase_69	AC	683 ms 5,376 KB
testcase_70	AC	1,372 ms 5,376 KB
testcase_71	AC	1,626 ms 5,376 KB
testcase_72	AC	1,751 ms 5,376 KB
testcase_73	AC	1,664 ms 5,376 KB
testcase_74	AC	1,791 ms 5,376 KB
testcase_75	AC	1,830 ms 5,376 KB
testcase_76	AC	1,614 ms 5,376 KB
testcase_77	AC	1,788 ms 5,376 KB
testcase_78	AC	1,775 ms 5,376 KB
testcase_79	AC	511 ms 5,376 KB
testcase_80	AC	579 ms 5,376 KB
testcase_81	AC	914 ms 5,376 KB
testcase_82	AC	835 ms 5,376 KB
testcase_83	AC	953 ms 5,376 KB
testcase_84	AC	712 ms 5,376 KB
testcase_85	AC	911 ms 5,376 KB
testcase_86	AC	579 ms 5,376 KB
testcase_87	AC	927 ms 5,376 KB
testcase_88	AC	1,326 ms 5,376 KB
testcase_89	AC	1,159 ms 5,376 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

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

yukicoder

結果

テストケース

ソースコード