結果

問題 No.408 五輪ピック
コンテスト
ユーザー iastm
提出日時 2026-04-12 07:15:44
言語 C++23
(gcc 15.2.0 + boost 1.89.0)
コンパイル:
g++-15 -O2 -lm -std=c++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 183 ms / 5,000 ms
コード長 1,894 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 2,753 ms
コンパイル使用メモリ 195,628 KB
実行使用メモリ 6,400 KB
最終ジャッジ日時 2026-04-12 07:15:52
合計ジャッジ時間 6,713 ms
ジャッジサーバーID
（参考情報） 		judge1_1 / judge2_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 32
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <iostream>
#include <vector>
// #include <kotone/random>
// https://github.com/amiast/cpp-utility

#ifndef KOTONE_RANDOM_HPP
#define KOTONE_RANDOM_HPP 1

#include <random>

namespace kotone {

// Returns a random unsigned 64-bit integer.
uint64_t randint() {
    static std::random_device rd;
    static std::mt19937_64 gen(rd());
    return gen();
}

// Reference: https://codeforces.com/blog/entry/62393
uint64_t splitmix64(uint64_t x) noexcept {
    x += 0x9e3779b97f4a7c15;
    x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
    x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
    return x ^ (x >> 31);
}

// A randomized hash for integers.
struct randomized_hash {
    std::size_t operator()(uint64_t x) const {
        static const uint64_t SEED = randint();
        return splitmix64(x ^ SEED);
    }
};

}  // namespace kotone

#endif  // KOTONE_RANDOM_HPP

int main() {
    int N, M;
    std::cin >> N >> M;
    std::vector<std::vector<int>> graph(N);
    while (M--) {
        int u, v;
        std::cin >> u >> v;
        u--, v--;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }

    for (int t = 0; t < 100; t++) {
        std::vector<int> color(N);
        for (int i = 1; i < N; i++) color[i] = kotone::randint() % 4;
        std::vector<std::vector<bool>> dp(16, std::vector<bool>(N));
        for (int j : graph[0]) dp[1 << color[j]][j] = true;
        for (int k = 0; k < 16; k++) {
            for (int i = 1; i < N; i++) {
                if (!dp[k][i]) continue;
                for (int j : graph[i]) {
                    if (j == 0 || k >> color[j] & 1) continue;
                    dp[k | 1 << color[j]][j] = true;
                }
            }
        }
        for (int j : graph[0]) {
            if (!dp[15][j]) continue;
            std::cout << "YES" << std::endl;
            return 0;
        }
    }

    std::cout << "NO" << std::endl;
}
0