結果
| 問題 |
No.1776 Love Triangle 2 (Hard)
|
| ユーザー |
 hitonanode
|
| 提出日時 | 2021-11-19 19:58:05 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
TLE
(最新)
AC
(最初)
|
| 実行時間 | - |
| コード長 | 7,043 bytes |
| コンパイル時間 | 2,715 ms |
| コンパイル使用メモリ | 146,332 KB |
| 最終ジャッジ日時 | 2025-01-25 19:50:33 |
|
ジャッジサーバーID （参考情報） |
judge5 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 121 TLE * 55 |
ソースコード
#include <array>
#include <chrono>
#include <iostream>
#include <random>
#include <vector>
using namespace std;
// https://epubs.siam.org/doi/10.1137/1.9781611973099.139
// Nimber (64 bit)
// Reference:
// - https://en.wikipedia.org/wiki/Nimber
// - https://kyopro-friends.hatenablog.com/entry/2020/04/07/195850
// - https://judge.yosupo.jp/submission/4542 (implementation idea)
struct Nimber {
using ull = unsigned long long;
ull v;
const static std::array<std::array<unsigned, 256>, 256> small_table;
const static std::array<std::array<std::array<ull, 256>, 8>, 8> precalc;
explicit operator bool() const { return v != 0; }
Nimber(ull val = 0) : v(val) {}
Nimber operator+(const Nimber &x) const { return Nimber(v ^ x.v); }
Nimber operator-(const Nimber &x) const { return Nimber(v ^ x.v); }
Nimber operator-() const { return *this; }
Nimber &operator+=(const Nimber &x) { return *this = *this + x; }
Nimber &operator-=(const Nimber &x) { return *this = *this + x; }
template <class IStream> friend IStream &operator>>(IStream &is, Nimber &x) {
ull v;
return is >> v, x = Nimber(v), is;
}
template <class OStream> friend OStream &operator<<(OStream &os, const Nimber &x) {
return os << x.v;
}
bool operator==(const Nimber &x) const { return v == x.v; }
bool operator!=(const Nimber &x) const { return v != x.v; }
bool operator<(const Nimber &x) const { return v < x.v; }
static ull _rec(ull x, ull y) {
if (x == 0 or y == 0) return 0;
if (x < y) x ^= y, y ^= x, x ^= y; // Make x >= y
if (y == 1) return x;
for (int shift = 64 / 2;; shift >>= 1) {
ull mask = (1ULL << shift) - 1;
if (y >> shift) {
ull v00 = _rec(x & mask, y & mask);
ull v01 = _rec(x & mask, y >> shift);
ull v10 = _rec(x >> shift, y & mask);
ull v11 = _rec(x >> shift, y >> shift);
return v00 ^ ((v01 ^ v10 ^ v11) << shift) ^ _rec(v11, 1ULL << (shift - 1));
} else if (x >> shift) {
return (_rec(x >> shift, y) << shift) ^ _rec(x & mask, y);
}
}
}
Nimber operator*(const Nimber &x) const {
if (this->v < 256 and x.v < 256) return small_table[this->v][x.v];
ull ret = 0;
for (int d = 0; d < 2; ++d) { // 16 bit
for (int e = 0; e < 2; ++e) { // 16 bit
ret ^= precalc[d][e][small_table[(v >> (d * 8)) & 255][(x.v >> (e * 8)) & 255]];
}
}
return Nimber(ret);
}
Nimber &operator*=(const Nimber &x) { return *this = *this * x; }
};
const std::array<std::array<unsigned, 256>, 256> Nimber::small_table = []() {
std::array<std::array<unsigned, 256>, 256> ret;
for (int i = 0; i < 256; ++i) {
for (int j = 0; j < 256; ++j) ret[i][j] = _rec(i, j);
}
return ret;
}();
const std::array<std::array<std::array<unsigned long long, 256>, 8>, 8> Nimber::precalc = []() {
std::array<std::array<std::array<unsigned long long, 256>, 8>, 8> ret;
for (int d = 0; d < 8; ++d) {
for (int e = 0; e < 8; ++e) {
ull p = _rec(1ULL << (8 * d), 1ULL << (8 * e));
for (int i = 0; i < 256; ++i) ret[d][e][i] = _rec(p, i);
}
}
return ret;
}();
struct rand_int_ {
using lint = long long;
mt19937 mt;
rand_int_() : mt(chrono::steady_clock::now().time_since_epoch().count()) {}
lint operator()(lint x) { return this->operator()(0, x); } // [0, x)
lint operator()(lint l, lint r) {
uniform_int_distribution<lint> d(l, r - 1);
return d(mt);
}
} rnd;
template <class Fq>
int can_reach(const vector<vector<Fq>> &w, int x, int y, int z, int dlim) {
// x を始点に y, z を経由し N に到達する長さ dlim 以下のパスがあるかを判定
int N = w.size() - 1;
// dp[visited y][visited z][current v][previous v]
vector dp(2, vector(2, vector(N + 1, vector<Fq>(N + 1, 0))));
dp[0][0][x][N] = 1;
for (int d = 1; d <= dlim; ++d) {
vector dpnxt(2, vector(2, vector(N + 1, vector<Fq>(N + 1, 0))));
for (int visy = 0; visy < 2; ++visy) {
for (int visz = 0; visz < 2; ++visz) {
for (int now = 0; now < N; ++now) {
Fq sum = 0;
for (int prv = 0; prv <= N; ++prv) sum += dp[visy][visz][now][prv];
for (int nxt = 0; nxt <= N; ++nxt) {
if (visy and (nxt == y)) continue;
if (visz and (nxt == z)) continue;
dpnxt[visy | (nxt == y)][visz | (nxt == z)][nxt][now] += (sum - dp[visy][visz][now][nxt]) * w[now][nxt];
}
}
}
}
dp = dpnxt;
for (int i = 0; i < N; ++i) {
if (dp[1][1][N][i] != 0) return d;
}
}
return 0; // not found
}
int main() {
int N, M;
cin >> N >> M;
int x, y, z;
cin >> x >> y >> z;
--x, --y, --z;
vector weight(N + 1, vector<Nimber>(N + 1));
for (int i = 0; i < N; ++i) {
for (int j = 0; j < i; ++j) {
Nimber w = rnd(1LL << 16);
Nimber wn = rnd(1LL << 16);
if (j != x) {
weight[i][j] = w;
} else {
weight[i][N] = wn;
}
if (i != x) {
weight[j][i] = w;
} else {
weight[j][N] = wn;
}
}
}
vector<vector<pair<int, Nimber>>> to(N);
vector exist_edge(N, vector<int>(N, 1));
while (M--) {
int a, b;
cin >> a >> b;
--a, --b;
weight[a][b] = weight[b][a] = 0;
if (a == x) weight[b][N] = 0;
if (b == x) weight[a][N] = 0;
}
int len = can_reach(weight, x, y, z, N);
if (!len) {
puts("-1");
return 0;
}
cout << len << '\n';
vector<int> path{x};
for (int l = 1; l < len; ++l) {
int ok = N, ng = -1; // ok 以下の頂点で到達可能、ng 以下の頂点で到達無理
while (ok - ng > 1) {
int thres = (ok + ng) / 2;
auto mat = weight;
int cur = path.back();
int prv = -1;
if (path.size() >= 2) prv = path[path.size() - 2];
for (int i = thres + 1; i <= N; ++i) {
mat[cur][i] = mat[i][cur] = 0;
}
if (prv >= 0) mat[cur][prv] = mat[prv][cur] = 1;
int cur_len = can_reach(mat, x, y, z, len);
(cur_len == len ? ok : ng) = thres;
}
int cur = path.back();
int prv = -1;
if (path.size() >= 2) prv = path[path.size() - 2];
path.push_back(ok);
for (int i = 0; i <= N; ++i) {
weight[cur][i] = weight[i][cur] = 0;
}
if (prv >= 0) weight[cur][prv] = weight[prv][cur] = 1;
}
path.push_back(x);
for (auto x : path) cout << x + 1 << ' ';
cout << '\n';
}