結果
| 問題 |
No.1775 Love Triangle 2
|
| ユーザー |
 hitonanode
|
| 提出日時 | 2021-11-28 00:17:19 |
| 言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
| 結果 |
CE
(最新)
AC
(最初)
|
| 実行時間 | - |
| コード長 | 6,663 bytes |
| コンパイル時間 | 132 ms |
| コンパイル使用メモリ | 25,088 KB |
| 最終ジャッジ日時 | 2025-01-26 02:21:06 |
|
ジャッジサーバーID （参考情報） |
judge2 / judge3 |
（要ログイン）
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、clay言語の場合は開発者のデバッグのため、公開されます。
ただし、clay言語の場合は開発者のデバッグのため、公開されます。
コンパイルメッセージ
main.cpp:2:10: fatal error: testlib.h: No such file or directory
2 | #include "testlib.h"
| ^~~~~~~~~~~
compilation terminated.
ソースコード
// Validator
#include "testlib.h"
#include <array>
#include <cassert>
#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 {
ull ret = 0;
for (int d = 0; d < 8; ++d) {
for (int e = 0; e < 8; ++e) { 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_gen;
template <class Fq> int solve(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][N][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;
Fq wadd = sum - ((now == y or now == z) ? dp[visy][visz][now][nxt] : 0);
dpnxt[visy | (nxt == y)][visz | (nxt == z)][nxt][now] += wadd * w[now][nxt];
}
}
}
}
dp = dpnxt;
for (int i = 0; i < N; ++i) {
if (dp[1][1][x][i] != 0) return d;
}
}
return -1; // not found
}
int main(int argc, char *argv[]) {
registerValidation(argc, argv);
int N = inf.readInt(1, 100);
inf.readSpace();
int M = inf.readInt(3, N * (N - 1) / 2);
inf.readEoln();
int x = inf.readInt(1, N);
inf.readSpace();
int y = inf.readInt(1, N);
inf.readSpace();
int z = inf.readInt(1, N);
inf.readEoln();
assert(x < y and 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_gen(1LL << 16);
Nimber wn = rnd_gen(1LL << 16);
if (j != x) {
weight[j][i] = w;
} else {
weight[N][i] = wn;
}
if (i != x) {
weight[i][j] = w;
} else {
weight[N][j] = wn;
}
}
}
vector<vector<int>> conn(N + 1, vector<int>(N + 1));
for (int i = 1; i <= M; ++i) {
int a = inf.readInt(1, N);
inf.readSpace();
int b = inf.readInt(1, N);
inf.readEoln();
assert(a < b);
--a, --b;
if (i == 1) assert(a == x and b == y);
if (i == 2) assert(a == x and b == z);
if (i == 3) assert(a == y and b == z);
assert(conn[a][b] == 0);
conn[a][b] = 1;
weight[a][b] = weight[b][a] = 0;
if (a == x) weight[N][b] = 0;
if (b == x) weight[N][a] = 0;
}
inf.readEof();
cout << solve(weight, x, y, z, N) << '\n';
}