結果
| 問題 | No.1640 簡単な色塗り |
| ユーザー |
 miyo2580
|
| 提出日時 | 2024-02-13 22:52:33 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 112 ms / 2,000 ms |
| コード長 | 5,910 bytes |
| コンパイル時間 | 2,699 ms |
| コンパイル使用メモリ | 217,292 KB |
| 最終ジャッジ日時 | 2025-02-19 06:04:19 |
|
ジャッジサーバーID （参考情報） |
judge2 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 53 |
ソースコード
#include <bits/stdc++.h>using namespace std;#define repd(i,a,b) for (ll i=(a);i<(b);i++)#define rep(i,n) repd(i,0,n)#define all(x) (x).begin(),(x).end()template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }typedef long long ll;typedef pair<ll,ll> P;typedef vector<ll> vec;using Graph = vector<vector<ll>>;const long long INF = 1LL<<60;const long long MOD = 1000000007;// Sieve of Eratosthenes// https://youtu.be/UTVg7wzMWQc?t=2774struct Sieve {int n;vector<int> f, primes;Sieve(int n=1):n(n), f(n+1) {f[0] = f[1] = -1;for (ll i = 2; i <= n; ++i) {if (f[i]) continue;primes.push_back(i);f[i] = i;for (ll j = i*i; j <= n; j += i) {if (!f[j]) f[j] = i;}}}bool isPrime(int x) { return f[x] == x;}vector<int> factorList(int x) {vector<int> res;while (x != 1) {res.push_back(f[x]);x /= f[x];}return res;}vector<P> factor(int x) {vector<int> fl = factorList(x);if (fl.size() == 0) return {};vector<P> res(1, P(fl[0], 0));for (int p : fl) {if (res.back().first == p) {res.back().second++;} else {res.emplace_back(p, 1);}}return res;}vector<pair<ll,int>> factor(ll x) {vector<pair<ll,int>> res;for (int p : primes) {int y = 0;while (x%p == 0) x /= p, ++y;if (y != 0) res.emplace_back(p,y);}if (x != 1) res.emplace_back(x,1);return res;}};//https://nyaannyaan.github.io/library/math/two-sat.hpp.htmlnamespace TwoSatImpl {namespace internal {template <class E>struct csr {vector<int> start;vector<E> elist;csr(int n, const vector<pair<int, E>>& edges): start(n + 1), elist(edges.size()) {for (auto e : edges) {start[e.first + 1]++;}for (int i = 1; i <= n; i++) {start[i] += start[i - 1];}auto counter = start;for (auto e : edges) {elist[counter[e.first]++] = e.second;}}};struct scc_graph {public:scc_graph(int n) : _n(n) {}int num_vertices() { return _n; }void add_edge(int from, int to) { edges.push_back({from, {to}}); }pair<int, vector<int>> scc_ids() {auto g = csr<edge>(_n, edges);int now_ord = 0, group_num = 0;vector<int> visited, low(_n), ord(_n, -1), ids(_n);visited.reserve(_n);auto dfs = [&](auto self, int v) -> void {low[v] = ord[v] = now_ord++;visited.push_back(v);for (int i = g.start[v]; i < g.start[v + 1]; i++) {auto to = g.elist[i].to;if (ord[to] == -1) {self(self, to);low[v] = min(low[v], low[to]);} else {low[v] = min(low[v], ord[to]);}}if (low[v] == ord[v]) {while (true) {int u = visited.back();visited.pop_back();ord[u] = _n;ids[u] = group_num;if (u == v) break;}group_num++;}};for (int i = 0; i < _n; i++) {if (ord[i] == -1) dfs(dfs, i);}for (auto& x : ids) {x = group_num - 1 - x;}return {group_num, ids};}vector<vector<int>> scc() {auto ids = scc_ids();int group_num = ids.first;vector<int> counts(group_num);for (auto x : ids.second) counts[x]++;vector<vector<int>> groups(ids.first);for (int i = 0; i < group_num; i++) {groups[i].reserve(counts[i]);}for (int i = 0; i < _n; i++) {groups[ids.second[i]].push_back(i);}return groups;}void add_node_size(int m) { _n += m; }int size() { return _n; }private:int _n;struct edge {int to;};vector<pair<int, edge>> edges;};} // namespace internalstruct two_sat {public:two_sat() : _n(0), built(false), scc(0) {}two_sat(int n) : _n(n), built(false), scc(2 * n) {}int add_var() {scc.add_node_size(2);return _n++;}// (not i) は ~i で渡すvoid add_clause(int i, int j) {i = max(2 * i, -1 - 2 * i);j = max(2 * j, -1 - 2 * j);assert(0 <= i && i < 2 * _n);assert(0 <= j && j < 2 * _n);scc.add_edge(i, j ^ 1);scc.add_edge(j, i ^ 1);}void if_then(int i, int j) { add_clause(~i, j); }void set_val(int i) { add_clause(i, i); }// (not i) は ~i で渡すvoid at_most_one(const vector<int>& nodes) {if ((int)nodes.size() <= 1) return;int cur = ~nodes[0];for (int i = 2; i < (int)nodes.size(); i++) {int nxt = add_var(), n_i = ~nodes[i];add_clause(cur, n_i);add_clause(cur, nxt);add_clause(n_i, nxt);cur = ~nxt;}add_clause(cur, ~nodes[1]);}bool satisfiable() {_answer.resize(_n);built = true;auto id = scc.scc_ids().second;for (int i = 0; i < _n; i++) {if (id[2 * i] == id[2 * i + 1]) {_answer.clear();return false;}_answer[i] = id[2 * i] < id[2 * i + 1];}return true;}vector<bool> answer() {if (!built) satisfiable();return _answer;}private:int _n;vector<bool> _answer;bool built;internal::scc_graph scc;};} // namespace TwoSatImplusing TwoSatImpl::two_sat;int main(){ios::sync_with_stdio(false);cin.tie(0);ll n;cin>>n;two_sat ts(n);vector<vector<int>> g(n);vec a(n),b(n);rep(i,n){ll x,y;cin>>x>>y;x--;y--;a[i]=x;b[i]=y;g[x].push_back(i);g[y].push_back(~i);}rep(i,n){ts.at_most_one(g[i]);}if(!ts.satisfiable())cout<<"No"<<endl;else{cout<<"Yes"<<endl;vector<bool> ans=ts.answer();rep(i,n){if(ans[i])cout<<a[i]+1<<'\n';else cout<<b[i]+1<<'\n';}}return 0;}