結果
問題 | No.3056 Disconnected Coloring |
ユーザー |
![]() |
提出日時 | 2025-03-14 21:47:39 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 259 ms / 2,000 ms |
コード長 | 2,218 bytes |
コンパイル時間 | 3,688 ms |
コンパイル使用メモリ | 289,956 KB |
実行使用メモリ | 17,824 KB |
最終ジャッジ日時 | 2025-03-14 21:48:07 |
合計ジャッジ時間 | 10,296 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 34 |
ソースコード
#include <bits/stdc++.h> using namespace std; #define rep(i, l, r) for (int i = (int)(l); i<(int)(r); i++) #define ll long long int main() { int N, M; cin >> N >> M; if (M%2) { cout << -1 << endl; return 0; } vector<vector<pair<int, int>>> G(N); vector<int> unuse; rep(i, 0, M) { int u, v; cin >> u >> v; u--; v--; if (u == 0 and v == N-1) { cout << -1 << endl; return 0; } if (u != 0 and u != N-1 and v != 0 and v != N-1) { unuse.push_back(i); } G[u].push_back({v, i}); G[v].push_back({u, i}); } // cout << "ok1" << endl; auto reachable = [&](int v) -> vector<bool> { int x = N - 1 - v; vector<bool> ret(N, false); queue<int> Q; ret[v] = true; Q.push(v); while(!Q.empty()) { int u = Q.front(); Q.pop(); // cout << u << " "; for (auto[to, id] : G[u]) { if (to == x) continue; if (!ret[to]) { ret[to] = true; Q.push(to); } } } // cout << endl; assert(ret[x] == false); return ret; }; vector<bool> R1 = reachable(0), RN = reachable(N-1); // for (auto v : R1) cout << v << " "; // cout << endl; // for (auto v : RN) cout << v << " "; // cout << endl; string ans(M, '.'); int R = 0, B = 0; for (auto[to, id] : G[0]) { if (!R1[to] or !RN[to]) { //いらない unuse.push_back(id); } else { ans[id] = 'R'; R++; } } // cout << "ok" << endl; for (auto[to, id] : G[N-1]) { if (!R1[to] or !RN[to]) { //いらない unuse.push_back(id); } else { ans[id] = 'B'; B++; } } // cout << "ok3" << endl; // cout << ans << endl; assert(R <= M/2); assert(B <= M/2); while(R < M/2) { int t = unuse.back(); unuse.pop_back(); ans[t] = 'R'; R++; } for (auto t : unuse) ans[t] = 'B'; cout << ans << endl; }