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

• 問題: No.3552 Triangular Coloring
• ユーザー: MaTi
• 提出日時: 2026-05-24 22:15:03
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: WA
• 実行時間: -
• コード長: 6,213 bytes
• コンパイル時間: 2,295 ms
• コンパイル使用メモリ: 347,520 KB
• 実行使用メモリ: 68,104 KB
• 最終ジャッジ日時: 2026-05-24 22:15:12
• 合計ジャッジ時間: 6,310 ms
• ジャッジサーバーID （参考情報）: judge2_0 / judge1_1

ファイルパターン	結果
sample	AC * 1
other	AC * 2 WA * 15

ソースコード

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
#define rep(i,a,b) for (int i=a; i<b; i++)
#define rrep(i,a,b) for(int i=a; i>=b; i--)
#define fore(i,a) for(auto &i:a)
#define pb push_back
#define _GLIBCXX_DEBUG
#define All(a) (a).begin(), (a).end()
#define YN(a) ((a) ? "Yes" : "No")
template <typename T> inline bool chmin(T& a, const T& b) {bool c=a>b; if(a>b) a=b; return c;}
template <typename T> inline bool chmax(T& a, const T& b) {bool c=a<b; if(a<b) a=b; return c;}
template <typename T> inline T gcd(T a,T b) {return (b==0)?a:gcd(b,a%b);}
template <typename T> inline T lcm(T a, T b) {return (a*b)/gcd(a,b);}
const int inf = INT_MAX / 2;
const ll infl = 1LL << 61;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using vvvi = vector<vector<vector<int>>>;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;
using vvvll = vector<vector<vector<ll>>>;

template <typename T>
void OUT(const T& x) {
    cout << x;
}
// ----- pair -----
template <typename T, typename U>
void OUT(const pair<T,U>& p) {
    cout << "(";
    OUT(p.first);
    cout << ", ";
    OUT(p.second);
    cout << ")";
}
// ----- vector -----
template <typename T>
void OUT(const vector<T>& v) {
    cout << "[ ";
    for (const auto& x : v) {
        OUT(x);
        cout << " ";
    }
    cout << "]";
}
// ----- set -----
template <typename T>
void OUT(const set<T>& s) {
    cout << "{ ";
    for (const auto& x : s) {
        OUT(x);
        cout << " ";
    }
    cout << "}";
}
// ----- map -----
template <typename K, typename V>
void OUT(const map<K,V>& mp) {
    cout << "{ ";
    for (const auto& [k,v] : mp) {
        OUT(k);
        cout << ": ";
        OUT(v);
        cout << ", ";
    }
    cout << "}";
}
// ----- queue -----
template <typename T>
void OUT(queue<T> q) {
    cout << "< ";
    while (!q.empty()) {
        OUT(q.front());
        cout << " ";
        q.pop();
    }
    cout << ">";
}
// ----- priority_queue -----
template <typename T>
void OUT(priority_queue<T> pq) {
    cout << "< ";
    while (!pq.empty()) {
        OUT(pq.top());
        cout << " ";
        pq.pop();
    }
    cout << ">";
}
// ----- stack -----
template <typename T>
void OUT(stack<T> st) {
    cout << "< ";
    while (!st.empty()) {
        OUT(st.top());
        cout << " ";
        st.pop();
    }
    cout << ">";
}
// ----- deque -----
template <typename T>
void OUT(const deque<T>& dq) {
    cout << "[ ";
    for (const auto& x : dq) {
        OUT(x);
        cout << " ";
    }
    cout << "]";
}
#define out(x) cerr << #x << ": ", OUT(x), cerr << '\n';

template<typename T = long long> // costの型
struct Graph {
    ///////////////辺の構造体↓/////////////
    struct Edge{
        T c;
        int u,v; // u→vの辺
        // 辺同士の比較は、c → u → vの順番に比較
        bool operator<(const Edge &other) const {
            return tie(c,u,v) < tie(other.c, other.u, other.v);
        }
    };
    
    /////////////メンバ変数↓///////////////
    vector<vector<pair<T,int>>> _nexts; // nexts[i] := i番目からの隣接リスト{コスト、行き先}
    vector<Edge> _edges; // 辺リスト
    T _total_edge_cost; // 全ての辺のコストの合計
    vector<int> _deg_in; // 全ての頂点の入次数を保持
    vector<int> _deg_out; // 全ての頂点の出次数を保持
    
    //////////コンストラクタ↓////////////
    Graph(int n): _nexts(n), _total_edge_cost(0), _deg_in(n,0), _deg_out(n,0) {}
    
    //////////メンバ関数↓////////////////
    //コスト1の辺u → vを追加する関数
    void add_edge(int u, int v){
        add_edge(T(1), u, v);
    }
    //コストcの辺u → vを追加する関数
    void add_edge(T c, int u, int v){
        _nexts[u].push_back({c, v});
        _edges.push_back(Edge{c, u, v});
        _total_edge_cost += c;
        _deg_out[u]++;
        _deg_in[v]++;
    }
    //頂点数を返す関数
    int size_n() const {
        return _nexts.size();
    }
    //辺の本数を返す関数
    int size_e() const {
        return _edges.size();
    }
    // 全ての辺のコストの合計を返す
    T total_edge_cost() const {
        return _total_edge_cost;
    }
    // 辺リストを返す関数
    const vector<Edge>& edges() const {
        return _edges;
    }
    // 隣接リストを返す関数
    const vector<vector<pair<T,int>>>& nexts() const {
        return _nexts;
    }
    // iから行ける場所の{コスト、行き先}の集合を返す関数
    const vector<pair<T,int>>& nexts(int i) const {
        return _nexts[i];
    }
    // 入次数配列を返す関数
    const vector<int>& deg_in() const {
        return _deg_in;
    }
    // 頂点iの入次数を返す関数
    int deg_in(int i) const {
        return _deg_in[i];
    }
    // 出次数配列を返す関数
    const vector<int>& deg_out() const {
        return _deg_out;
    }
    // 頂点iの出次数を返す関数
    int deg_out(int i) const {
        return _deg_out[i];
    }
};


int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m;
    cin >> n >> m;
    Graph<ll> G(n);
    rep(i,0,m){
        int u,v;
        cin >> u >> v;
        u--; v--;
        G.add_edge(u,v);
        G.add_edge(v,u);
    }
    vi col(n,-1);
    vi visited(n,0);
    queue<int> q;
    col[0] = 1;
    visited[0] = 1;
    rep(i,0,G.deg_out(0)){
        q.push(G.nexts(0)[i].second);
        visited[G.nexts(0)[i].second] = 1;
    }

    while(!q.empty()){
        int cur = q.front(); q.pop();
        vi used(5,0);
        rep(i,0,G.deg_out(cur)){
            int nx = G.nexts(cur)[i].second;
            if(col[nx] != -1){
                used[col[nx]] = 1;
                //out(col[nx]);
            }
            if(!visited[nx]){
                q.push(nx);
                visited[nx] = 1;
            }
        }
        rep(i,1,5){
            if(!used[i]){
                col[cur] = i;
                break;
            }
        }
    }

    cout << "Yes" << endl;
    rep(i,0,n){
        cout << col[i] << " ";
    }
    cout << endl;

    cout << fixed << setprecision(30);
    return 0;
}