QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#552643#8544. Colorful Graph 2ucup-team3646WA 80ms3872kbC++204.0kb2024-09-08 00:15:452024-09-08 00:15:46

Judging History

你现在查看的是最新测评结果

  • [2024-09-08 00:15:46]
  • 评测
  • 测评结果:WA
  • 用时:80ms
  • 内存:3872kb
  • [2024-09-08 00:15:45]
  • 提交

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)