結果
| 問題 | No.408 五輪ピック |
| コンテスト | |
| ユーザー |
|
| 提出日時 | 2026-10-18 21:58:19 |
| 言語 | C++23(gcc16) (gcc 16.2.0 + boost 1.92.0 + ACL) |
| 結果 |
AC
不安定
|
| 実行時間 | 387 ms / 5,000 ms |
| + 316µs | |
| コード長 | 1,373 bytes |
| 記録 | |
| コンパイル時間 | 1,462 ms |
| コンパイル使用メモリ | 206,048 KB |
| 実行使用メモリ | 9,876 KB |
| 最終ジャッジ日時 | 2026-10-21 16:26:48 |
| 合計ジャッジ時間 | 5,997 ms |
|
ジャッジサーバーID (参考情報) |
judge5_0 / judge2_0 |
(要ログイン)
| ファイルパターン | 結果 |
|---|---|
| other | AC * 35 |
ソースコード
// https://speakerdeck.com/camypaper/yukicoder-no-408?slide=16
// こういう random を使った解法身につけたいな
#include <array>
#include <iostream>
#include <random>
#include <vector>
int main() {
using namespace std;
int n, m;
cin >> n >> m;
vector<vector<int>> g(n);
for (int _ = 0; _ < m; _++) {
int u, v;
cin >> u >> v;
u--; v--;
g[u].push_back(v);
g[v].push_back(u);
}
mt19937 rng(random_device{}());
uniform_int_distribution<int> dist(0, 3);
auto ok = [&]() -> bool {
vector<int> col(n);
for (int i = 0; i < n; i++) { col[i] = dist(rng); }
vector dp(n, array<bool, 16>{});
for (int v : g[0]) { dp[v][1 << col[v]] = true; }
for (int b = 0; b < 16; b++) {
for (int v = 0; v < n; v++) {
if (!dp[v][b]) { continue; }
for (int nv : g[v]) {
if (nv == 0) { continue; }
if (b >> col[nv] & 1) { continue; }
dp[nv][b | 1 << col[nv]] = true;
}
}
}
for (int v : g[0]) {
if (dp[v][15]) { return true; }
}
return false;
};
for (int _ = 0; _ < 200; _++) {
if (ok()) {
cout << "YES\n";
return 0;
}
}
cout << "NO\n";
}