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

提出ソース

結果

問題	No.1775 Love Triangle 2
ユーザー	👑 Nachia
提出日時	2021-12-12 22:26:32
言語	C++17 (gcc 13.2.0 + boost 1.83.0)
結果	AC
実行時間	552 ms / 8,000 ms
コード長	7,077 bytes
コンパイル時間	1,489 ms
コンパイル使用メモリ	116,928 KB
実行使用メモリ	4,452 KB
最終ジャッジ日時	2023-09-28 16:05:29
合計ジャッジ時間	8,938 ms
ジャッジサーバーID （参考情報）	judge12 / judge15

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 4,380 KB
testcase_01	AC	3 ms 4,376 KB
testcase_02	AC	3 ms 4,376 KB
testcase_03	AC	2 ms 4,380 KB
testcase_04	AC	437 ms 4,396 KB
testcase_05	AC	552 ms 4,376 KB
testcase_06	AC	544 ms 4,376 KB
testcase_07	AC	176 ms 4,376 KB
testcase_08	AC	519 ms 4,384 KB
testcase_09	AC	4 ms 4,376 KB
testcase_10	AC	4 ms 4,380 KB
testcase_11	AC	4 ms 4,376 KB
testcase_12	AC	4 ms 4,376 KB
testcase_13	AC	5 ms 4,376 KB
testcase_14	AC	5 ms 4,380 KB
testcase_15	AC	6 ms 4,380 KB
testcase_16	AC	6 ms 4,376 KB
testcase_17	AC	7 ms 4,380 KB
testcase_18	AC	14 ms 4,380 KB
testcase_19	AC	4 ms 4,376 KB
testcase_20	AC	5 ms 4,376 KB
testcase_21	AC	4 ms 4,376 KB
testcase_22	AC	4 ms 4,376 KB
testcase_23	AC	4 ms 4,376 KB
testcase_24	AC	4 ms 4,376 KB
testcase_25	AC	4 ms 4,380 KB
testcase_26	AC	5 ms 4,376 KB
testcase_27	AC	4 ms 4,376 KB
testcase_28	AC	5 ms 4,380 KB
testcase_29	AC	16 ms 4,408 KB
testcase_30	AC	22 ms 4,376 KB
testcase_31	AC	33 ms 4,380 KB
testcase_32	AC	37 ms 4,380 KB
testcase_33	AC	32 ms 4,376 KB
testcase_34	AC	33 ms 4,376 KB
testcase_35	AC	28 ms 4,376 KB
testcase_36	AC	20 ms 4,376 KB
testcase_37	AC	13 ms 4,376 KB
testcase_38	AC	5 ms 4,380 KB
testcase_39	AC	18 ms 4,380 KB
testcase_40	AC	28 ms 4,376 KB
testcase_41	AC	32 ms 4,380 KB
testcase_42	AC	27 ms 4,376 KB
testcase_43	AC	20 ms 4,376 KB
testcase_44	AC	15 ms 4,380 KB
testcase_45	AC	28 ms 4,380 KB
testcase_46	AC	11 ms 4,380 KB
testcase_47	AC	4 ms 4,376 KB
testcase_48	AC	6 ms 4,376 KB
testcase_49	AC	10 ms 4,452 KB
testcase_50	AC	21 ms 4,376 KB
testcase_51	AC	30 ms 4,376 KB
testcase_52	AC	27 ms 4,380 KB
testcase_53	AC	26 ms 4,380 KB
testcase_54	AC	28 ms 4,376 KB
testcase_55	AC	21 ms 4,376 KB
testcase_56	AC	19 ms 4,376 KB
testcase_57	AC	13 ms 4,376 KB
testcase_58	AC	9 ms 4,376 KB
testcase_59	AC	16 ms 4,380 KB
testcase_60	AC	25 ms 4,376 KB
testcase_61	AC	24 ms 4,380 KB
testcase_62	AC	14 ms 4,380 KB
testcase_63	AC	11 ms 4,376 KB
testcase_64	AC	12 ms 4,376 KB
testcase_65	AC	6 ms 4,376 KB
testcase_66	AC	6 ms 4,376 KB
testcase_67	AC	5 ms 4,380 KB
testcase_68	AC	4 ms 4,376 KB
testcase_69	AC	4 ms 4,376 KB
testcase_70	AC	6 ms 4,380 KB
testcase_71	AC	7 ms 4,376 KB
testcase_72	AC	9 ms 4,376 KB
testcase_73	AC	9 ms 4,376 KB
testcase_74	AC	8 ms 4,380 KB
testcase_75	AC	9 ms 4,380 KB
testcase_76	AC	7 ms 4,376 KB
testcase_77	AC	8 ms 4,376 KB
testcase_78	AC	8 ms 4,380 KB
testcase_79	AC	5 ms 4,376 KB
testcase_80	AC	6 ms 4,376 KB
testcase_81	AC	7 ms 4,380 KB
testcase_82	AC	7 ms 4,376 KB
testcase_83	AC	9 ms 4,376 KB
testcase_84	AC	6 ms 4,380 KB
testcase_85	AC	8 ms 4,380 KB
testcase_86	AC	5 ms 4,380 KB
testcase_87	AC	6 ms 4,380 KB
testcase_88	AC	10 ms 4,376 KB
testcase_89	AC	5 ms 4,376 KB

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

ソースコード

raw source code


#include <vector>

// reference
// https://drive.google.com/file/d/16g1tfSHUU4NXNTDgaD8FSA1WB4FtJCyV/edit
class nimber_manager{
private:
    using u32 = unsigned int;
    using u64 = unsigned long long;
    
    std::vector<u32> precalc1;
    void fill_precalc1(){
        precalc1.assign(1 << 16, 0);
        precalc1[(1 << 8) ^ 1] = 1;
        for(int dd=1; dd<8; dd<<=1){
            int d = 1 << dd;
            int c = d >> 1;
            for(int a0=0; a0<d; a0++) for(int a1=0; a1<d; a1++) if(a0 | a1) {
                for(int b0=0; b0<d; b0++) for(int b1=0; b1<d; b1++) if(b0 | b1) {
                    u64 buf = 0;
                    buf ^= precalc1[(a1 << 8) ^ b1];
                    buf ^= precalc1[(a1 << 8) ^ b0];
                    buf ^= precalc1[(a0 << 8) ^ b1];
                    buf <<= dd;
                    buf ^= precalc1[(c << 8) ^ precalc1[(a1 << 8) ^ b1]];
                    buf ^= precalc1[(a0 << 8) ^ b0];
                    precalc1[(((a1 << dd) ^ a0) << 8) ^ ((b1 << dd) ^ b0)] = buf;
                }
            }
        }
    }
    
    u64 product_full(u64 a, u64 b, int d = 6){
        if(!(a && b)) return 0;
        if(d == 3){ return precalc1[(a << 8) ^ b]; }
        d--;
        u64 lm = ((u64)1 << (1 << d)) - 1;
        u64 us = ((u64)1 << d);
        u64 buf = 0;
        u64 a1b1 = product_full(a >> us, b >> us, d);
        buf ^= a1b1;
        buf ^= product_full(a & lm, b >> us, d);
        buf ^= product_full(a >> us, b & lm, d);
        buf <<= us;
        buf ^= product_full(a & lm, b & lm, d);
        buf ^= product_full((u64)1 << (us - 1), a1b1, d);
        return buf;
    }
public:
    nimber_manager(){ fill_precalc1(); }
    
    unsigned long long product(unsigned long long a, unsigned long long b){ return product_full(a,b); }
};


#include <algorithm>
#include <unordered_map>
#include <cassert>
#include <cstdint>


class Randomizer_NV{
public:

  using i32 = int32_t;
  using u32 = uint32_t;
  using i64 = int64_t;
  using u64 = uint64_t;


private:

  u32 rngx = 1234567890;
  u32 rngy = 987654321;
  u32 rngz = 998244353;
  u32 rngw = 1000000007;

public:

  void seed(u32 x = 1234567890, u32 y = 987654321, u32 z = 998244353, u32 w = 1000000007){
    rngx = x;
    rngy = y;
    rngz = z;
    rngw = w;
  }

  u32 rng32() {
    const u32 t = rngx ^ (rngx << 11);
    rngx = rngy; rngy = rngz; rngz = rngw;
    return rngw = rngw ^ (rngw >> 19) ^ t ^ (t >> 8);
  }
  u64 rng64() {
    return (u64)rng32() << 32 | rng32();
  }

  // generate x : l <= x <= r
  u64 random_unsigned(u64 l,u64 r){
    assert(l<=r);
    r-=l;
    auto res = rng64();
    if(res<=r) return res+l;
    u64 d = r+1;
    u64 max_valid = 0xffffffffffffffff/d*d;
    while(true){
      auto res = rng64();
      if(res<=max_valid) break;
    }
    return res%d+l;
  }

  // generate x : l <= x <= r
  i64 random_signed(i64 l,i64 r){
    assert(l<=r);
    u64 unsigned_l = (u64)l ^ (1ull<<63);
    u64 unsigned_r = (u64)r ^ (1ull<<63);
    u64 unsigned_res = random_unsigned(unsigned_l,unsigned_r) ^ (1ull<<63);
    return (i64)unsigned_res;
  }


  // permute x : n_left <= x <= n_right
  // output r from the front
  std::vector<i64> random_nPr(i64 n_left,i64 n_right,i64 r){
    i64 n = n_right-n_left;

    assert(n>=0);
    assert(r<=(1ll<<27));
    if(r==0) return {};  
    assert(n>=r-1);

    if(n==0) return {};
    std::vector<i64> V;
    std::unordered_map<i64,i64> G;
    for(int i=0; i<r; i++){
      i64 p = random_signed(i,n);
      i64 x = p - G[p];
      V.push_back(x);
      G[p] = p - (i - G[i]);
    }

    for(i64& v : V) v+=n_left;
    return move(V);
  }



  // V[i] := V[perm[i]]
  // using swap
  template<class E,class PermInt_t>
  void permute_inplace(std::vector<E>& V,std::vector<PermInt_t> perm){
    assert(V.size() == perm.size());
    int N=V.size();
    for(int i=0; i<N; i++){
      int p=i;
      while(perm[p]!=i){
        assert(0 <= perm[p] && perm[p] < N);
        assert(perm[p] != perm[perm[p]]);
        std::swap(V[p],V[perm[p]]);
        /* std::swap(p,perm[p]); */ { int pbuf = perm[p]; perm[p] = p; p = pbuf; }
      }
      perm[p] = p;
    }
  }

  template<class E>
  std::vector<E> shuffle(const std::vector<E>& V){
    int N=V.size();
    auto P = random_nPr(0,N-1,N);
    std::vector<E> res;
    res.reserve(N);
    for(int i=0; i<N; i++) res.push_back(V[P[i]]);
  }

  // shuffle using swap
  template<class E>
  void shuffle_inplace(std::vector<E>& V){
    int N=V.size();
    permute_inplace(V,random_nPr(0,N-1,N));
  }


};

#include <iostream>
using namespace std;
using i32 = int32_t;
using u32 = uint32_t;
using i64 = int64_t;
using u64 = uint64_t;
#define rep(i,n) for(int i=0; i<(n); i++)


nimber_manager nim;
Randomizer_NV rng;

struct Edge{ int from, to, rev; u64 h; };


int N, M;
int X, Y, Z;
int goal;
vector<vector<int>> H;
vector<Edge> edges;
vector<vector<int>> Ei;

vector<u64> dp;


int main() {
    cin >> N >> M;
    cin >> X >> Y >> Z; X--; Y--; Z--;
    H.assign(N+1, vector<int>(N+1, 1));
    rep(i,N) H[i][i] = 0;
    rep(i,M){
        int u,v; cin >> u >> v; u--; v--;
        H[u][v] = H[v][u] = 0;
    }
    H[X][Y] = H[Y][X] = 0;
    H[X][Z] = H[Z][X] = 0;
    H[Y][Z] = H[Z][Y] = 0;

    Ei.resize(N+1);
    rep(i,N) rep(j,i) if(H[i][j]){
        u64 h = rng.rng32() / 2 + 7001;
        Ei[i].push_back(edges.size());
        edges.push_back({ i,j,(int)edges.size()+1,h });
        Ei[j].push_back(edges.size());
        edges.push_back({ j,i,(int)edges.size()-1,h });
    }
    
    goal = N;
    rep(i,N) if(H[i][X]){
        u64 h = rng.rng32() / 2 + 7001;
        Ei[i].push_back(edges.size());
        edges.push_back({ i,goal,(int)edges.size()+1,h });
        Ei[goal].push_back(edges.size());
        edges.push_back({ goal,i,(int)edges.size()-1,h });
    }
    N++;

    dp.assign(edges.size() * 4, 0);

    //for(auto e : edges) cout << "(" << e.from << ", " << e.to << ", " << e.rev << ", " << e.h << ")" << endl;

    int ans = 0;
    while(true){
        if(ans >= 150) break;
        vector<u64> dptmp(dp.size(), 0);
        vector<u64> dpvtx(N*4, 0);
        rep(d,4) rep(i,edges.size()) dpvtx[edges[i].to*4+d] ^= dp[i*4+d];
        if(ans == 0){ dpvtx[X*4] = 1; }

        //rep(i,N){ rep(d,4) cout << (dpvtx[i*4+d]?1:0) << " "; cout << " "; } cout << endl;
        if(dpvtx[goal*4+3] != 0) break;

        rep(d,4) rep(from, N-1) for(int ei : Ei[from]){
            auto e = edges[ei];
            int nx = ei*4+d;
            u64 ddp = dpvtx[e.from*4+d];
            if(e.to == Y) if(nx & 1) continue;
            if(e.to == Z) if(nx & 2) continue;
            if(e.from == Y){ ddp ^= dp[e.rev*4+d]; nx |= 1; }
            if(e.from == Z){ ddp ^= dp[e.rev*4+d]; nx |= 2; }
            ddp = nim.product(ddp, e.h);
            dptmp[nx] ^= ddp;
        }

        swap(dp, dptmp);
        ans++;
    }

    if(ans >= 150) ans = -1;

    cout << ans << endl;

    return 0;
}


struct ios_do_not_sync{
    ios_do_not_sync(){
        ios::sync_with_stdio(false);
        cin.tie(nullptr);
    }
} ios_do_not_sync_instance;

yukicoder

結果

テストケース

ソースコード