QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#389032 | #8544. Colorful Graph 2 | ucup-team159# | WA | 94ms | 3876kb | C++23 | 4.4kb | 2024-04-14 00:03:06 | 2024-04-14 00:03:06 |
Judging History
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();
}
詳細信息
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)