結果
問題 | No.3056 Disconnected Coloring |
ユーザー |
![]() |
提出日時 | 2024-10-20 11:38:47 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 327 ms / 2,000 ms |
コード長 | 1,740 bytes |
コンパイル時間 | 2,431 ms |
コンパイル使用メモリ | 205,940 KB |
実行使用メモリ | 17,536 KB |
最終ジャッジ日時 | 2025-03-14 19:58:59 |
合計ジャッジ時間 | 14,686 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 34 |
ソースコード
#include<bits/stdc++.h> #include<atcoder/dsu> using namespace std; int main(){ int N, M; cin >> N >> M; assert(2 <= N && N <= 200000); assert(1 <= M && M <= 200000); if(M % 2 == 1){ cout << -1 << endl; return 0; } vector<int> u(M), v(M); string ret(M, 'R'); int x = 0; set<pair<int, int>>st; for(int i = 0; i < M; i++){ cin >> u[i] >> v[i]; assert(1 <= u[i] && u[i] < v[i] && v[i] <= N); assert(!st.count(make_pair(u[i], v[i]))); st.emplace(u[i], v[i]); u[i]--; v[i]--; if(u[i] > v[i]){ swap(u[i],v[i]); } if(u[i] == 0){ x++; } if(u[i] == 0 && v[i] == N - 1){ cout << -1 << endl; return 0; } } if(x * 2 > M){ x = 0; for(int i = 0; i < M; i++){ if(u[i] == 0){ u[i] = N - 1; swap(u[i], v[i]); } else if(v[i] == N - 1){ v[i] = 0; swap(u[i], v[i]); x++; } } } atcoder::dsu uf(N); for(int i = 0; i < M; i++){ if(v[i] != N - 1){ uf.merge(u[i], v[i]); } if(u[i] == 0){ ret[i] = 'B'; } else if(x * 2 < M && v[i] != N - 1){ ret[i] = 'B'; x++; } } for(int i = 0; i < M; i++){ if(x * 2 < M && v[i] == N - 1 && !uf.same(0, u[i])){ ret[i] = 'B'; x++; } } { atcoder::dsu ufr(N), ufb(N), uf(N); int cr = 0, cb = 0; for(int i = 0; i < M; i++){ uf.merge(u[i], v[i]); if(ret[i] == 'R'){ cr++; ufr.merge(u[i], v[i]); } else{ cb++; ufb.merge(u[i], v[i]); } } assert(cr == cb); assert(!ufr.same(0, N - 1) && !ufb.same(0, N - 1)); for(int i = 0; i < N; i++)assert(uf.same(0, i)); } cout << ret << endl; }