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

• 問題: No.1775 Love Triangle 2
• ユーザー: Nachia
• 提出日時: 2021-12-12 22:26:32
• 言語: C++17 (gcc 13.3.0 + boost 1.87.0)
• 結果: AC
• 実行時間: 569 ms / 8,000 ms
• コード長: 7,077 bytes
• コンパイル時間: 1,543 ms
• コンパイル使用メモリ: 111,200 KB
• 最終ジャッジ日時: 2025-01-26 09:27:17
• ジャッジサーバーID （参考情報）: judge2 / judge5

ファイルパターン	結果
other	AC * 90

ソースコード

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