QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#405412#8544. Colorful Graph 2AkagishigeruWA 15ms3760kbC++141.9kb2024-05-05 21:02:532024-05-05 21:02:55

Judging History

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

  • [2024-05-05 21:02:55]
  • 评测
  • 测评结果:WA
  • 用时:15ms
  • 内存:3760kb
  • [2024-05-05 21:02:53]
  • 提交

answer

// #pragma GCC optimize(2)
// #pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;
namespace zzx{
	typedef long long ll;
	typedef unsigned long long ull;
	typedef long double ld;
	// typedef __int128 lll;
    #define pc putchar
    #define gc getchar
    #define et pc('\n')
    #define spc pc(' ')
    #define pb push_back
    #define eb emplace_back
    #define lb lower_bound
    #define pii pair<int,int>
    #define pll pair<ll,ll>
    #define tii tuple<int,int,int>
    #define tll tuple<ll,ll,ll>
    #define mk make_pair
    #define pp pop_back
    mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
    template<class T>
    void read(T &num){
        T x=0,f=1;
        char c=gc();
        while(!isdigit(c)){
            if(c=='-') f=-1;
            c=gc();
        }
        while(isdigit(c)){
            x=(x<<3)+(x<<1)+c-48;
            c=gc();
        }
        num=f*x;
    }
    template<class T>
    void write(T x){
        static char buf[40];
        static int len=-1;
        if(x<0) pc('-'),x=-x;
        do{
            buf[++len]=x%10+48;
            x/=10;
        }while(x);
        while(len>=0) pc(buf[len--]);
    }
}
using namespace zzx;
const int maxn=2e5+10;
int n,m,col[maxn],head[maxn],tot;
struct edge{
	int t,nxt;
}e[maxn<<2];
void add(int st,int ed){
	e[++tot]={ed,head[st]};
	head[st]=tot;
}
queue<int> q;
void solve(){
	read(n),read(m);
	for(int i=1;i<=n;i++) col[i]=-1,head[i]=0;
	tot=0;
	for(int i=1;i<n;i++) add(i,i+1),add(i+1,i);
	for(int i=1,u,v;i<=m;i++){
		read(u),read(v);
		add(u,v),add(v,u);
	}
	q.push(1);
	col[1]=0;
	while(!q.empty()){
		int u=q.front();
		q.pop();
		for(int i=head[u];i;i=e[i].nxt){
			if(col[e[i].t]==-1){
				col[e[i].t]=col[u]^1;
				q.push(e[i].t);
			}
		}
	}
	for(int i=1;i<=n;i++){
		if(col[i]) pc('R');
		else pc('B');
	}
	et;
}
int main(){
	int t=1;
	read(t);
	while(t--) solve();
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3760kb

input:

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

output:

BRB
BRRB
BRBBRB

result:

ok ok (3 test cases)

Test #2:

score: -100
Wrong Answer
time: 15ms
memory: 3684kb

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:

BRBRRBRBR
BRB
BRBBR
BRBRRB
BRRBBRBRB
BRB
BRRBRRB
BRRRRBR
BRRB
BRBBRB
BRRBBR
BRBBRBR
BRRRRBBR
BRB
BRBRBBRB
BRRRRBBR
BRB
BRBRBBBRBR
BRRBBRRB
BRBRRBRBRB
BRBRBRBRRB
BRBRBBRBRB
BRB
BRBRBRB
BRRRRB
BRBBBBBR
BRRB
BRBRRBR
BRBRRBBBRB
BRBRBRB
BRBRBRRB
BRRRRB
BRBBRB
BRB
BRB
BRRRBBRRB
BRBRBBR
BRRBR
BRBBRBRBRB
BR...

result:

wrong answer cycle detected (test case 1)