QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#389032#8544. Colorful Graph 2ucup-team159#WA 94ms3876kbC++234.4kb2024-04-14 00:03:062024-04-14 00:03:06

Judging History

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

  • [2024-04-14 00:03:06]
  • 评测
  • 测评结果:WA
  • 用时:94ms
  • 内存:3876kb
  • [2024-04-14 00:03:06]
  • 提交

answer

#line 1 "C.cpp"
// #pragma GCC target("avx2,avx512f,avx512vl,avx512bw,avx512dq,avx512cd,avx512vbmi,avx512vbmi2,avx512vpopcntdq,avx512bitalg,bmi,bmi2,lzcnt,popcnt")
// #pragma GCC optimize("Ofast")

#line 2 "/mnt/c/Users/tsigm/Documents/Cprogram/library/template.hpp"

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using uint = unsigned int;
using ull = unsigned long long;
#define rep(i,n) for(int i=0;i<int(n);i++)
#define rep1(i,n) for(int i=1;i<=int(n);i++)
#define per(i,n) for(int i=int(n)-1;i>=0;i--)
#define per1(i,n) for(int i=int(n);i>0;i--)
#define all(c) c.begin(),c.end()
#define si(x) int(x.size())
#define pb push_back
#define eb emplace_back
#define fs first
#define sc second
template<class T> using V = vector<T>;
template<class T> using VV = vector<vector<T>>;
template<class T,class U> bool chmax(T& x, U y){
	if(x<y){ x=y; return true; }
	return false;
}
template<class T,class U> bool chmin(T& x, U y){
	if(y<x){ x=y; return true; }
	return false;
}
template<class T> void mkuni(V<T>& v){sort(all(v));v.erase(unique(all(v)),v.end());}
template<class T> int lwb(const V<T>& v, const T& a){return lower_bound(all(v),a) - v.begin();}
template<class T>
V<T> Vec(size_t a) {
    return V<T>(a);
}
template<class T, class... Ts>
auto Vec(size_t a, Ts... ts) {
  return V<decltype(Vec<T>(ts...))>(a, Vec<T>(ts...));
}
template<class S,class T> ostream& operator<<(ostream& o,const pair<S,T> &p){
	return o<<"("<<p.fs<<","<<p.sc<<")";
}
template<class T> ostream& operator<<(ostream& o,const vector<T> &vc){
	o<<"{";
	for(const T& v:vc) o<<v<<",";
	o<<"}";
	return o;
}
constexpr ll TEN(int n) { return (n == 0) ? 1 : 10 * TEN(n-1); }

#ifdef LOCAL
#define show(x) cerr << "LINE" << __LINE__ << " : " << #x << " = " << (x) << endl
void dmpr(ostream& os){os<<endl;}
template<class T,class... Args>
void dmpr(ostream&os,const T&t,const Args&... args){
	os<<t<<" ~ ";
	dmpr(os,args...);
}
#define shows(...) cerr << "LINE" << __LINE__ << " : ";dmpr(cerr,##__VA_ARGS__)
#define dump(x) cerr << "LINE" << __LINE__ << " : " << #x << " = {";  \
	for(auto v: x) cerr << v << ","; cerr << "}" << endl;
#else
#define show(x) void(0)
#define dump(x) void(0)
#define shows(...) void(0)
#endif

template<class D> D divFloor(D a, D b){
	return a / b - (((a ^ b) < 0 && a % b != 0) ? 1 : 0);
}
template<class D> D divCeil(D a, D b) {
	return a / b + (((a ^ b) > 0 && a % b != 0) ? 1 : 0);
}

/*
x       0  1  2  3  4  5  6  7  8  9
bsr(x) -1  0  1  1  2  2  2  2  3  3
最上位bit
*/
int bsr(int x){
	return x == 0 ? -1 : 31 ^ __builtin_clz(x);
}
int bsr(uint x){
	return x == 0 ? -1 : 31 ^ __builtin_clz(x);
}
int bsr(ll x){
	return x == 0 ? -1 : 63 ^ __builtin_clzll(x);
}
int bsr(ull x){
	return x == 0 ? -1 : 63 ^ __builtin_clzll(x);
}

/*
x       0  1  2  3  4  5  6  7  8  9
bsl(x) -1  0  1  0  2  0  1  0  3  0
最下位bit
*/
int bsl(int x){
	if(x==0) return -1;
	return __builtin_ctz(x);
}
int bsl(uint x){
	if(x==0) return -1;
	return __builtin_ctz(x);
}
int bsl(ll x){
	if(x==0) return -1;
	return __builtin_ctzll(x);
}
int bsl(ull x){
	if(x==0) return -1;
	return __builtin_ctzll(x);
}


template<class T>
T rnd(T l,T r){	//[l,r)
	using D = uniform_int_distribution<T>;
	static random_device rd;
	static mt19937 gen(rd());
	return D(l,r-1)(gen);
}
template<class T>
T rnd(T n){	//[0,n)
	return rnd(T(0),n);
}
#line 5 "C.cpp"

void solve(){
	int N,M; cin >> N >> M;
	VV<int> G(N);
	rep(i,N){
		int j = (i+1)%N;
		G[i].eb(j); G[j].eb(i);
	}
	rep(i,M){
		int x,y; cin >> x >> y;
		G[x].eb(y); G[y].eb(x);
	}
	rep(i,N) sort(all(G[i]));
	V<int> col(N,-1);
	auto dfs = [&](auto&& self, int l, int r) -> void {
		if(r-l <= 1){
			return;
		}
		assert(col[l] != -1 && col[r] != -1);
		assert(col[l] != col[r]);
		V<int> vs;
		for(auto v: G[r]) if(l <= v && v < r){
			vs.eb(v);
		}
		int K = si(vs);
		rep(i,K) col[vs[i]] = col[l] ^ (i%2);
		rep(i,K-1){
			self(self,vs[i],vs[i+1]);
		}
	};
	{
		col[0] = 0;
		V<int> vs = G[0];
		int K = si(vs);
		rep(i,K) col[vs[i]] = i%2;
		rep(i,K-1) dfs(dfs,vs[i],vs[i+1]);
	}
	show(col);
	rep(i,N) cout << (col[i] ? 'B' : 'R');
	cout << '\n';
}

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);		//DON'T USE scanf/printf/puts !!
	cout << fixed << setprecision(20);

	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: 3876kb

input:

3
3 0
4 1
1 3
6 3
0 2
2 4
4 0

output:

RRB
RRBB
RRBRRB

result:

ok ok (3 test cases)

Test #2:

score: 0
Accepted
time: 94ms
memory: 3588kb

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:

RRBRBRRBR
RRB
RRBRR
RRBRBB
RRBBRBBRB
RRB
RRBBRBB
RRBBBBR
RRBB
RRBRRB
RRBBRR
RRBRBBR
RRBBBBRR
RRB
RRBRBRRB
RRBBBBRR
RRB
RRBRBRBRRR
RRBBRBBB
RRBRBRBBBB
RRBRBRBRBB
RRBRBRRBRB
RRB
RRBRBRB
RRBBBB
RRBRRRRR
RRBB
RRBRBBR
RRBRBRRRRB
RRBRBRB
RRBRBRBB
RRBBBB
RRBRRB
RRB
RRB
RRBBBRRBB
RRBRBRR
RRBBR
RRBRBBRBBB
RR...

result:

ok ok (100000 test cases)

Test #3:

score: -100
Wrong Answer
time: 74ms
memory: 3596kb

input:

100000
8 4
5 3
5 1
6 1
3 1
7 4
5 0
4 1
4 0
3 1
4 0
8 1
4 7
3 0
3 0
8 1
1 3
3 0
9 4
6 0
3 0
3 1
5 0
7 0
6 2
4 2
0 4
7 3
0 3
0 4
1 3
5 1
3 0
10 4
6 8
5 2
1 5
5 3
5 1
1 4
3 0
9 3
5 0
8 6
6 0
3 0
5 2
1 3
1 4
9 0
6 1
4 2
8 1
1 3
5 0
8 2
3 1
6 1
5 1
3 0
8 3
3 0
7 4
7 5
7 2
5 3
1 3
10 3
8 0
0 3
8 5
9 4
3 0...

output:

RRBBBBRB
RRBBBRB
RRRB
RRBBRRBB
RRB
RRB
RRBBBBRB
RRB
RRBBBRBBR
RRBBBRB
RRRBBR
RRBBRRB
RRRBR
RRBBBBBBRB
RRRBB
RRB
RRBBRBRBB
RRB
RRBBB
RRBBBBBRB
RRBBRB
RRBBBBRB
RRBRB
RRBBBBRB
RRRBR
RRRBBRBR
RRBBBRB
RRRBBBBRRB
RRRBRRBRB
RRBRBBBRB
RRBBRB
RRBBRRB
RRB
RRBBBBBBRB
RRBBBR
RRBBBBBRB
RRBRB
RRBBBBBBRB
RRBRR
RRB...

result:

wrong answer cycle detected (test case 1)