#1166212 (C++23) No.3552 Triangular Coloring

• 問題: No.3552 Triangular Coloring
• ユーザー: zawakasu
• 提出日時: 2026-05-22 23:32:54
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: RE
• 実行時間: -
• コード長: 3,878 bytes
• コンパイル時間: 2,253 ms
• コンパイル使用メモリ: 226,604 KB
• 実行使用メモリ: 65,408 KB
• 最終ジャッジ日時: 2026-05-22 23:33:14
• 合計ジャッジ時間: 16,539 ms
• ジャッジサーバーID （参考情報）: judge3_1 / judge1_0

ファイルパターン	結果
sample	AC * 1
other	RE * 17

ソースコード

#include <iostream>
#include <iomanip>
#include <cassert>
#include <vector>
#include <algorithm>
#include <utility>
#include <numeric>
#include <tuple>
#include <ranges>
#include <random>
// #include "Src/Number/IntegerDivision.hpp"
// #include "Src/Utility/BinarySearch.hpp"
// #include "Src/Sequence/CompressedSequence.hpp"
// #include "Src/Sequence/RunLengthEncoding.hpp"
// #include "Src/Algebra/Group/AdditiveGroup.hpp"
// #include "Src/DataStructure/FenwickTree/FenwickTree.hpp"
// #include "Src/DataStructure/SegmentTree/SegmentTree.hpp"
// #include "Src/DataStructure/DisjointSetUnion/DisjointSetUnion.hpp"
// #include "Src/DataStructure/Heap/BinaryHeap.hpp"
namespace zawa {}
using namespace zawa;
// #include "atcoder/modint"
// using mint = atcoder::modint998244353;
// #include <array>
// #include <bit>
// #include <bitset>
// #include <climits>
// #include <cmath>
#include <set>
// #include <unordered_set>
// #include <map>
// #include <unordered_map>
// #include <optional>
#include <queue>
// #include <stack>
// #include <deque>
// #pragma GCC target("avx2")
// #pragma GCC optimize("O3")
// #pragma GCC optimize("unroll-loops")
using namespace std;
template <class T, class U>
ostream& operator<<(ostream& os, const pair<T, U>& p) {
    os << '(' << p.first << ',' << p.second << ')';
    return os;
}
template <class T>
ostream& operator<<(ostream& os, const vector<T>& v) {
    for (int i = 0 ; i < ssize(v) ; i++)
        os << v[i] << (i + 1 == ssize(v) ? "" : " ");
    return os;
}
/*
 * グラフの生成手順がわかれば
 * - 外周を0,1,2
 * - 点を増やす毎にmexをいれる
 * とすればOK
 * 生成手順はわかるのでしょうか？
 * N=4が無理なんですね
 * 次数3を見つける -> ごにょる
 */
int main() {
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);
    cout << fixed << setprecision(20);
#if !defined DEBUG
    int N,M;
    cin >> N >> M;
    vector<set<int>> G(N);
    vector<int> deg(N);
    for (int i = 0 ; i < M ; i++) {
        int u,v;
        cin >> u >> v;
        u--; v--;
        G[u].insert(v);
        G[v].insert(u);
        deg[u]++;
        deg[v]++;
    }
    vector<int> ans(N,-1);
    queue<int> que;
    for (int i = 0 ; i < N ; i++)
        if (deg[i] == 3)
            que.push(i);
    while (que.size()) {
        const int v = que.front();
        que.pop();
        if (ssize(G[v]) < 3) {
            assert(0 <= ans[v] and ans[v] < 4);
            for (int x : G[v])
                assert(0 <= ans[x] and ans[x] < 4);
            continue;
        }
        assert(ssize(G[v]) == 3);
        vector<bool> remain(4);
        if (ans[v] != -1)
            remain[ans[v]] = 1;
        for (int x : G[v])
            if (ans[x] != -1) {
                assert(remain[ans[x]] == 0);
                remain[ans[x]] = 1;
            }
        int idx = 0;
        auto get = [&]() -> int {
            while (idx < 4 and remain[idx])
                idx++;
            assert(idx < 4);
            remain[idx] = 1;
            return idx;
        };
        if (ans[v] == -1)
            ans[v] = get();
        for (int x : G[v])
            if (ans[x] == -1)
                ans[x] = get();
        for (int x : G[v]) {
            assert(G[x].contains(v));
            G[x].erase(v);
            if (ssize(G[x]) == 3)
                que.push(x);
        }
    }
    for (int& a : ans) {
        assert(0 <= a and a < 4);
        a++;
    }
    cout << "Yes\n";
    cout << ans << '\n';
#else
    mt19937_64 mt{random_device{}()};
    for (int testcase = 0 ; ; ) {
        cerr << "----------" << ++testcase << "----------" << endl;
        
        auto a = solve(), b = naive();
        if (a != b) {
            // print testcase

            cerr << "you: " << a << endl;
            cout << "correct: " << b << endl;
            exit(0);
        }
    }
#endif
}