QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#552643 | #8544. Colorful Graph 2 | ucup-team3646 | WA | 80ms | 3872kb | C++20 | 4.0kb | 2024-09-08 00:15:45 | 2024-09-08 00:15:46 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define elif else if
#define vi vector<int>
#define vll vector<ll>
#define vvi vector<vi>
#define pii pair<int,int>
#define repname(a, b, c, d, e, ...) e
#define rep(...) repname(__VA_ARGS__, rep3, rep2, rep1, rep0)(__VA_ARGS__)
#define rep0(x) for (int rep_counter = 0; rep_counter < (x); ++rep_counter)
#define rep1(i, x) for (int i = 0; i < (x); ++i)
#define rep2(i, l, r) for (int i = (l); i < (r); ++i)
#define rep3(i, l, r, c) for (int i = (l); i < (r); i += (c))
struct ScalarInput {
template<class T>
operator T(){
T ret;
cin >> ret;
return ret;
}
};
struct VectorInput {
size_t n;
VectorInput(size_t n): n(n) {}
template<class T>
operator vector<T>(){
vector<T> ret(n);
for(T &x : ret) cin >> x;
return ret;
}
};
ScalarInput input(){ return ScalarInput(); }
VectorInput input(size_t n){ return VectorInput(n); }
template<typename T>
void print(vector<T> a){
for(int i=0;i<a.size();i++){
cout<<a[i]<<" \n"[i+1==a.size()];
}
}
template<class T>
void print(T x){
cout << x << '\n';
}
template <class Head, class... Tail>
void print(Head&& head, Tail&&... tail){
cout << head << ' ';
print(forward<Tail>(tail)...);
}
#include <algorithm>
#include <cassert>
#include <vector>
namespace atcoder {
struct dsu {
public:
dsu() : _n(0) {}
explicit dsu(int n) : _n(n), parent_or_size(n, -1) {}
int merge(int a, int b) {
assert(0 <= a && a < _n);
assert(0 <= b && b < _n);
int x = leader(a), y = leader(b);
if (x == y) return x;
if (-parent_or_size[x] < -parent_or_size[y]) std::swap(x, y);
parent_or_size[x] += parent_or_size[y];
parent_or_size[y] = x;
return x;
}
bool same(int a, int b) {
assert(0 <= a && a < _n);
assert(0 <= b && b < _n);
return leader(a) == leader(b);
}
int leader(int a) {
assert(0 <= a && a < _n);
if (parent_or_size[a] < 0) return a;
return parent_or_size[a] = leader(parent_or_size[a]);
}
int size(int a) {
assert(0 <= a && a < _n);
return -parent_or_size[leader(a)];
}
std::vector<std::vector<int>> groups() {
std::vector<int> leader_buf(_n), group_size(_n);
for (int i = 0; i < _n; i++) {
leader_buf[i] = leader(i);
group_size[leader_buf[i]]++;
}
std::vector<std::vector<int>> result(_n);
for (int i = 0; i < _n; i++) {
result[i].reserve(group_size[i]);
}
for (int i = 0; i < _n; i++) {
result[leader_buf[i]].push_back(i);
}
result.erase(
std::remove_if(result.begin(), result.end(),
[&](const std::vector<int>& v) { return v.empty(); }),
result.end());
return result;
}
private:
int _n;
std::vector<int> parent_or_size;
};
} // namespace atcoder
using namespace atcoder;
void solve(){
int n,m;
cin>>n>>m;
dsu uf(n);
vector<vector<int>>tree(n);
rep(i,m){
int u,v;
cin>>u>>v;
if(!uf.same(u,v)){
uf.merge(u,v);
tree[u].push_back(v);
tree[v].push_back(u);
}
}
rep(v,n){
int u=(v+1)%n;
if(!uf.same(u,v)){
uf.merge(u,v);
tree[u].push_back(v);
tree[v].push_back(u);
}
}
string ans(n,'X');
ans[0]='B';
vector<int>todo={0};
while(!todo.empty()){
int v=todo.back();
todo.pop_back();
for(auto u:tree[v]){
if(ans[u]=='X'){
todo.push_back(u);
if(ans[v]=='B')ans[u]='R';
else ans[u]='B';
}
}
}
print(ans);
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin>>T;
while(T--)solve();
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3852kb
input:
3 3 0 4 1 1 3 6 3 0 2 2 4 4 0
output:
BRB BRBB BRRBBR
result:
ok ok (3 test cases)
Test #2:
score: -100
Wrong Answer
time: 80ms
memory: 3872kb
input:
100000 9 6 2 0 4 6 3 6 0 6 0 7 2 6 3 0 5 2 2 4 2 0 6 3 1 5 4 1 2 4 9 6 3 1 6 4 8 1 3 6 1 6 8 6 3 0 7 4 3 0 4 0 6 4 3 1 7 4 5 1 5 0 3 1 1 4 4 1 1 3 6 3 2 4 4 0 2 0 6 3 3 0 1 3 5 3 7 4 0 5 2 5 5 1 3 5 8 5 4 1 5 1 5 0 1 3 5 7 3 0 8 5 0 2 4 6 0 6 0 3 4 0 8 5 5 1 1 4 5 0 3 1 5 7 3 0 10 7 0 2 9 2 5 8 3 9 ...
output:
BRRBBRRRB BRB BRRBB BRRBBB BRBBBRRBB BRB BBRRRBB BBRRRRB BRBB BRBRRB BBRRBB BBBBRRB BBRRRRBB BRB BRRRBRRB BBRRRRBB BRB BRRRRRRBBB BRBBRBBB BRRRRRBBBB BRRRRBBBBB BRRRBRRRBB BRB BRRBBRB BRBBBB BRRBBBBB BRBB BRRRBBB BRRRRBBBBB BRRRBBB BRBRRBBB BRBBBB BRRBRB BRB BRB BRBBBRRRB BBBRRBB BBRRB BRRRBBRBBB BB...
result:
wrong answer cycle detected (test case 47)