結果
問題 | No.1640 簡単な色塗り |
ユーザー |
|
提出日時 | 2021-08-06 23:13:52 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
RE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 1,858 bytes |
コンパイル時間 | 1,252 ms |
コンパイル使用メモリ | 110,720 KB |
実行使用メモリ | 16,416 KB |
最終ジャッジ日時 | 2024-06-29 16:14:34 |
合計ジャッジ時間 | 14,252 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 51 RE * 2 |
ソースコード
#include <iostream>#include <string>#include <algorithm>#include <vector>#include <iomanip>#include <cmath>#include <stdio.h>#include <queue>#include <deque>#include <cstdio>#include <set>#include <map>#include <bitset>#include <stack>#include <cctype>using namespace std;vector<vector<pair<int,int>>> vec(200020);bool bo[200020] = { false }, bo1[200020] = { false };bool bo2[200020] = { false };int ans[200020];int main() {int n;cin >> n;for (int i = 0; i < n; i++) {int a, b;cin >> a >> b;vec[a].emplace_back(make_pair(b,i));vec[b].emplace_back(make_pair(a,i));}for (int i = 1; i <= n; i++) {if (!bo[i]) {queue<pair<int, int>> que;queue<int> que1;que.push(make_pair(i, -1));bo[i] = true;set<int> st;int co = 0, a = -1, b = -1, c = -1;while (!que.empty()) {pair<int, int> p = que.front();int now = que.front().first;que.pop();st.insert(now);for (int j = 0; j < vec[now].size(); j++) {co++;if (!bo[vec[now][j].first]) {bo[vec[now][j].first] = true;bo2[vec[now][j].second] = true;que.push(make_pair(vec[now][j].first, now));}else if (!bo2[vec[now][j].second]) {a = now;b = vec[now][j].first;c = vec[now][j].second;}}}if (st.size() == co + 1) {cout << "No" << endl;return 0;}ans[c] = a;que1.push(a);bo1[a] = true;while (!que1.empty()) {int now = que1.front();que1.pop();for (int j = 0; j < vec[now].size(); j++) {if (vec[now][j].second != c) {if (!bo1[vec[now][j].first]) {bo1[vec[now][j].first] = true;que1.push(vec[now][j].first);ans[vec[now][j].second] = vec[now][j].first;}}}}}}cout << "Yes" << endl;for (int i = 0; i < n; i++) {cout << ans[i] << endl;}}