結果

問題 No.3552 Triangular Coloring
コンテスト
ユーザー areik
提出日時 2026-05-22 23:32:26
言語 C++17
(gcc 15.2.0 + boost 1.89.0)
コンパイル:
g++-15 -O2 -lm -std=c++17 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 325 ms / 2,000 ms
コード長 1,597 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,500 ms
コンパイル使用メモリ 229,480 KB
実行使用メモリ 67,328 KB
最終ジャッジ日時 2026-05-22 23:32:32
合計ジャッジ時間 5,070 ms
ジャッジサーバーID
（参考情報） 		judge2_1 / judge3_1
純コード判定待ち
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 17
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
#include <atcoder/modint.hpp>
using namespace std;
 
using i32 = int;
using i64 = long long;
using i128 = __int128_t;
using f64 = double;
using p2 = pair<i64, i64>;
using p3 = tuple<i64, i64, i64>;
using mint = atcoder::modint998244353;
constexpr i64 inf = 1e18;
 
void _main();
int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(18);
  _main();
}

void _main() {
  i64 n, m;
  cin >> n >> m;
  vector<bool> one(n, false);
  vector<p2> edge(m);
  vector<vector<i64>> g(n);
  for (i64 i = 0; i < m; i++) {
    i64 u, v;
    cin >> u >> v;
    u--, v--;
    if (u > v) swap(u, v);
    g[u].push_back(v);
    g[v].push_back(u);
    if (u == 0) one[v] = true;
    edge[i] = {u, v};
  }
  vector<i64> ans(n, -1);
  vector<set<i64>> adj(n);
  vector<i64> stack;
  for (auto [u, v] : edge) {
    if (!one[u] || !one[v]) continue;
    adj[0] = {1, 2, 3};
    adj[u] = {0, 2, 3};
    adj[v] = {0, 1, 3};
    ans[0] = 0, ans[u] = 1, ans[v] = 2;
    stack = {0, u, v};
    break;
  }
  while (!stack.empty()) {
    i64 i = stack.back();
    stack.pop_back();
    for (i64 ni : g[i]) {
      if (ans[ni] != -1) {
        assert(ans[i] != ans[ni]);
        continue;
      }
      adj[ni].insert(ans[i]);
      if (adj[ni].size() >= 3) {
        assert(adj[ni].size() == 3);
        for (i64 k = 0; k < 4; k++) {
          if (!adj[ni].count(k)) {
            ans[ni] = k;
          }
        }
        stack.push_back(ni);
      }
    }
  }
  cout << "Yes\n";
  for (i64 i = 0; i < n; i++) {
    cout << ans[i] + 1 << " ";
  }
  cout << "\n";
}
0