#1194368 (C++23(gcc16)) No.1640 簡単な色塗り

提出ソース

結果

問題	No.1640 簡単な色塗り
コンテスト
ユーザー	C
提出日時	2026-10-23 14:51:59
言語	C++23(gcc16) (gcc 16.2.0 + boost 1.92.0 + ACL) コンパイル: `g++-16 -O2 -lm -std=c++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_` 実行: `./a.out`
結果	AC
実行時間	44 ms / 2,000 ms
	+ 0µs
コード長	5,918 bytes
記録記録タグの例: 初AC ショートコード純ショートコード純主流ショートコード最速実行時間
コンパイル時間	8,054 ms
コンパイル使用メモリ	402,752 KB
実行使用メモリ	28,148 KB
最終ジャッジ日時	2026-10-23 14:52:21
合計ジャッジ時間	20,009 ms
ジャッジサーバーID （参考情報）	judge1_0 / judge4_0

このコードへのチャレンジ
（要ログイン）

ファイルパターン	結果
sample	AC * 3
other	AC * 53

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include <bits/stdc++.h>
#include <atcoder/all>
#include <boost/polygon/point_data.hpp>
#include <boost/polygon/voronoi.hpp>
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define all(x) begin(x),end(x)
#define sz(x) (int)(x).size()
using namespace std;
using namespace atcoder;
using ll=long long;
using ld=long double;
using vll=vector<ll>;
using vvll=vector<vll>;
using vi=vector<int>;
using vvi=vector<vi>;
using pll=pair<ll,ll>;
using pi=pair<int,int>;

// using mint=modint998244353;
// using mint2=static_modint<2>;

// using BoostPoint=boost::polygon::point_data<int>;
// using Voronoi=boost::polygon::voronoi_diagram<double>;

#line 2 "graph/others/eulerian-trail.hpp"

#include <algorithm>
#include <cstdlib>
#include <iterator>
#include <stack>
#include <utility>
#include <vector>

#line 2 "structure/union-find/union-find.hpp"

#line 4 "structure/union-find/union-find.hpp"
#include <cstddef>
#line 7 "structure/union-find/union-find.hpp"

struct UnionFind {
  std::vector<int> data;

  UnionFind() = default;

  explicit UnionFind(std::size_t sz) : data(sz, -1) {}

  bool unite(int x, int y) {
    x = find(x), y = find(y);
    if (x == y) return false;
    if (data[x] > data[y]) std::swap(x, y);
    data[x] += data[y];
    data[y] = x;
    return true;
  }

  int find(int k) {
    if (data[k] < 0) return (k);
    return data[k] = find(data[k]);
  }

  int size(int k) { return -data[find(k)]; }

  bool same(int x, int y) { return find(x) == find(y); }

  std::vector<std::vector<int>> groups() {
    int n = (int)data.size();
    std::vector<std::vector<int>> ret(n);
    for (int i = 0; i < n; i++) {
      ret[find(i)].emplace_back(i);
    }
    ret.erase(
        std::remove_if(ret.begin(), ret.end(),
                       [&](const std::vector<int>& v) { return v.empty(); }),
        ret.end());
    return ret;
  }
};
#line 11 "graph/others/eulerian-trail.hpp"

/**
 * @brief Eulerian Trail(オイラー路)
 *
 */
template <bool directed>
struct EulerianTrail {
  std::vector<std::vector<std::pair<int, int> > > g;
  std::vector<std::pair<int, int> > es;
  int M;
  std::vector<int> used_vertex, used_edge, deg;

  explicit EulerianTrail(int V) : g(V), M(0), used_vertex(V), deg(V) {}

  void add_edge(int a, int b) {
    es.emplace_back(a, b);
    g[a].emplace_back(b, M);
    if (directed) {
      deg[a]++;
      deg[b]--;
    } else {
      g[b].emplace_back(a, M);
      deg[a]++;
      deg[b]++;
    }
    M++;
  }

  std::pair<int, int> get_edge(int idx) const { return es[idx]; }

  std::vector<std::vector<int> > enumerate_eulerian_trail() {
    if (directed) {
      for (auto& p : deg)
        if (p != 0) return {};
    } else {
      for (auto& p : deg)
        if (p & 1) return {};
    }
    used_edge.assign(M, 0);
    std::vector<std::vector<int> > ret;
    for (int i = 0; i < (int)g.size(); i++) {
      if (g[i].empty() || used_vertex[i]) continue;
      ret.emplace_back(go(i));
    }
    return ret;
  }

  std::vector<std::vector<int> > enumerate_semi_eulerian_trail() {
    UnionFind uf(g.size());
    for (auto& p : es) uf.unite(p.first, p.second);
    std::vector<std::vector<int> > group(g.size());
    for (int i = 0; i < (int)g.size(); i++) group[uf.find(i)].emplace_back(i);
    std::vector<std::vector<int> > ret;
    used_edge.assign(M, 0);
    for (auto& vs : group) {
      if (vs.empty()) continue;
      int latte = -1, malta = -1;
      if (directed) {
        for (auto& p : vs) {
          if (std::abs(deg[p]) > 1) {
            return {};
          } else if (deg[p] == 1) {
            if (latte >= 0) return {};
            latte = p;
          }
        }
      } else {
        for (auto& p : vs) {
          if (deg[p] & 1) {
            if (latte == -1)
              latte = p;
            else if (malta == -1)
              malta = p;
            else
              return {};
          }
        }
      }
      ret.emplace_back(go(latte == -1 ? vs.front() : latte));
      if (ret.back().empty()) ret.pop_back();
    }
    return ret;
  }

  std::vector<int> go(int s) {
    std::stack<std::pair<int, int> > st;
    std::vector<int> ord;
    st.emplace(s, -1);
    while (!st.empty()) {
      int idx = st.top().first;
      used_vertex[idx] = true;
      if (g[idx].empty()) {
        ord.emplace_back(st.top().second);
        st.pop();
      } else {
        auto e = g[idx].back();
        g[idx].pop_back();
        if (used_edge[e.second]) continue;
        used_edge[e.second] = true;
        st.emplace(e);
      }
    }
    ord.pop_back();
    std::reverse(ord.begin(), ord.end());
    return ord;
  }
};



int main()
{
  	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int N;
	cin>>N;
	vi a(N),b(N),ans(N,-1),rev(N,-1),deg(N,0);
	vvi g(N);
	rep(i,0,N){
		cin>>a[i]>>b[i];
		a[i]--,b[i]--;
		if(a[i]==b[i]){
			ans[i]=a[i];
			rev[a[i]]=i;
			continue;
		}
		g[a[i]].push_back(i);
		g[b[i]].push_back(i);
		deg[a[i]]++,deg[b[i]]++;
	}

	queue<int>q;
	rep(i,0,N){
		if(deg[i]==1)q.push(i);
	}
	while(!q.empty()){
		int ball=q.front();
		q.pop();
		if(deg[ball]==0||rev[ball]!=-1)continue;
		for(auto op:g[ball]){
			if(ans[op]==-1){
				ans[op]=ball;
				rev[ball]=op;
				int other=(ball==a[op])?b[op]:a[op];
				if(deg[other]>0){
					deg[other]--;
					if(deg[other]==1)q.push(other);
				}
				break;
			}
		}
		deg[ball]=0;
	}

	int remainL=0,remainR=0;
	bool deg0=false;
	rep(i,0,N){
		if(ans[i]==-1)remainR++;
		if(rev[i]==-1){
			remainL++;
			if(deg[i]==0)deg0=true;
		}
	}
	if(remainL!=remainR||deg0){
		cout<<"No\n";
		return 0;
	}

	EulerianTrail<false>et(2*N);
	rep(op,0,N){
		if(ans[op]!=-1)continue;
		et.add_edge(a[op],op+N);
		et.add_edge(b[op],op+N);
	}
	for(auto& tour:et.enumerate_eulerian_trail()){
		for(int j=0;j<sz(tour);j+=2){
			auto [ball,op]=et.get_edge(tour[j]);
			ans[op-N]=ball;
		}
	}

	cout<<"Yes\n";
	rep(op,0,N){
		cout<<ans[op]+1<<'\n';
	}
}

yukicoder

結果

ソースコード