結果
| 問題 | No.1775 Love Triangle 2 |
| コンテスト | |
| ユーザー |
 iastm
|
| 提出日時 | 2026-06-08 14:24:04 |
| 言語 | C++23 (gcc 15.2.0 + boost 1.89.0) |
| 結果 |
AC
|
| 実行時間 | 124 ms / 8,000 ms |
| コード長 | 5,956 bytes |
| 記録 | |
| コンパイル時間 | 4,685 ms |
| コンパイル使用メモリ | 332,816 KB |
| 実行使用メモリ | 6,400 KB |
| 最終ジャッジ日時 | 2026-06-08 14:24:13 |
| 合計ジャッジ時間 | 9,159 ms |
|
ジャッジサーバーID （参考情報） |
judge1_0 / judge2_0 |
| 純コード判定待ち |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 90 |
ソースコード
#include <iostream>
#include <vector>
#include <array>
#include <random>
// #include <kotone/nimber>
// https://github.com/amiast/cpp-utility
#ifndef KOTONE_NIMBER_HPP
#define KOTONE_NIMBER_HPP 1
#include <iostream>
#include <array>
namespace kotone {
// An integer-like type encapsulated with nimber arithmetic.
// Reference: https://kyopro-friends.hatenablog.com/entry/2020/04/07/195850
// Reference: https://maspypy.com/library-checker-nim-product
struct nimber {
private:
const static inline std::array<std::array<uint8_t, 256>, 256> _TABLE = [](){
std::array<std::array<uint8_t, 256>, 256> table{};
table[1][1] = 1;
for (int k = 1; k < 8; k *= 2) {
int max = (1 << k) - 1;
for (int a = 1 << k; a < 1 << (k * 2); a++) {
int au = a >> k, al = a & max;
for (int b = 1; b <= a; b++) {
int bu = b >> k, bl = b & max;
int pu = table[au][bu];
int pm = table[au ^ al][bu ^ bl];
int pl = table[al][bl];
table[a][b] = table[b][a] = (pm ^ pl) << k | (table[pu][1 << (k - 1)] ^ pl);
}
}
}
return table;
}();
constexpr static uint32_t _MAX_U32 = 0xffffffff;
constexpr static uint16_t _MAX_U16 = 0xffff;
constexpr static uint8_t _MAX_U8 = 0xff;
uint64_t _val;
static uint16_t _prod_16(uint16_t a, uint16_t b) noexcept {
uint8_t au = a >> 8, al = a & _MAX_U8;
uint8_t bu = b >> 8, bl = b & _MAX_U8;
uint8_t pu = _TABLE[au][bu];
uint8_t pm = _TABLE[au ^ al][bu ^ bl];
uint8_t pl = _TABLE[al][bl];
return uint16_t(pm ^ pl) << 8 | (_TABLE[pu][1 << 7] ^ pl);
}
static uint16_t _prod_by_15(uint16_t a) noexcept {
uint8_t au = a >> 8, al = a & _MAX_U8;
return uint16_t(_TABLE[au ^ al][1 << 7]) << 8 | _TABLE[_TABLE[au][1 << 7]][1 << 7];
}
static uint32_t _prod_32(uint32_t a, uint32_t b) noexcept {
uint16_t au = a >> 16, al = a & _MAX_U16;
uint16_t bu = b >> 16, bl = b & _MAX_U16;
uint16_t pu = _prod_16(au, bu);
uint16_t pm = _prod_16(au ^ al, bu ^ bl);
uint16_t pl = _prod_16(al, bl);
return uint32_t(pm ^ pl) << 16 | (_prod_by_15(pu) ^ pl);
}
static uint32_t _prod_by_31(uint32_t a) noexcept {
uint16_t au = a >> 16, al = a & _MAX_U16;
return uint32_t(_prod_16(au ^ al, 1 << 15)) << 16 | _prod_by_15(_prod_by_15(au));
}
static uint64_t _prod_64(uint64_t a, uint64_t b) noexcept {
uint32_t au = a >> 32, al = a & _MAX_U32;
uint32_t bu = b >> 32, bl = b & _MAX_U32;
uint32_t pu = _prod_32(au, bu);
uint32_t pm = _prod_32(au ^ al, bu ^ bl);
uint32_t pl = _prod_32(al, bl);
return uint64_t(pm ^ pl) << 32 | (_prod_by_31(pu) ^ pl);
}
public:
// Constructs nimber equal to `0`.
nimber() noexcept : _val(0) {}
// Constructs nimber for the specified value.
nimber(uint64_t val) noexcept : _val(val) {}
// Returns the raw value.
uint64_t val() const noexcept { return _val; }
nimber& operator+=(const nimber &other) noexcept { _val ^= other._val; return *this; }
nimber& operator*=(const nimber &other) noexcept { _val = _prod_64(_val, other._val); return *this; }
friend nimber operator+(const nimber &l, const nimber &r) noexcept { return nimber(l) += r; }
friend nimber operator*(const nimber &l, const nimber &r) noexcept { return nimber(l) *= r; }
friend bool operator==(const nimber &l, const nimber &r) noexcept { return l._val == r._val; }
friend bool operator!=(const nimber &l, const nimber &r) noexcept { return !(l == r); }
friend std::ostream& operator<<(std::ostream &out, const nimber &n) { return out << n._val; }
friend std::istream& operator>>(std::istream &in, nimber &n) { return in >> n._val; }
};
} // namespace kotone
#endif // KOTONE_NIMBER_HPP
using nim = kotone::nimber;
int main() {
int N, M, x, y, z;
std::cin >> N >> M >> x >> y >> z;
x--, y--, z--;
std::vector adj(N, std::vector(N, false));
while (M--) {
int u, v;
std::cin >> u >> v;
u--, v--;
adj[u][v] = adj[v][u] = true;
}
std::vector<std::vector<std::pair<int, int>>> graph(N);
std::vector<std::pair<int, int>> edges;
std::vector<uint64_t> weight;
std::mt19937_64 gen(std::random_device{}());
for (int i = 0; i < N; i++) {
for (int j = 0; j < i; j++) {
if (adj[i][j]) continue;
graph[i].emplace_back(j, edges.size());
graph[j].emplace_back(i, edges.size() + 1);
edges.emplace_back(i, j);
edges.emplace_back(j, i);
weight.push_back(gen());
if (i == x || j == x) weight.push_back(gen());
else weight.push_back(weight.back());
}
}
M = edges.size();
std::vector<std::array<nim, 4>> dp(M);
for (int i = 0; i < M; i++) if (edges[i].first == x) dp[i][0] = weight[i];
for (int len = 2; len <= N; len++) {
std::vector<std::array<nim, 4>> ndp(M);
for (int u = 0; u < N; u++) {
for (int k = 0; k < 4; k++) {
if (u == y && k & 1) continue;
if (u == z && k >> 1 & 1) continue;
nim acc = 0;
for (auto [v, i] : graph[u]) acc += dp[i ^ 1][k];
for (auto [v, i] : graph[u]) {
int nk = k | (u == y) | (u == z) << 1;
if (k != nk) ndp[i][nk] = (acc + dp[i ^ 1][k]) * weight[i];
else ndp[i][nk] = acc * weight[i];
}
}
}
dp = ndp;
nim acc = 0;
for (auto [v, i] : graph[x]) acc += dp[i ^ 1][3];
if (acc == 0) continue;
std::cout << len << std::endl;
return 0;
}
std::cout << -1 << std::endl;
}