QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#609006#8544. Colorful Graph 2lottle1212RE 4ms98364kbC++142.0kb2024-10-04 10:12:112024-10-04 10:12:13

Judging History

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

  • [2024-10-04 10:12:13]
  • 评测
  • 测评结果:RE
  • 用时:4ms
  • 内存:98364kb
  • [2024-10-04 10:12:11]
  • 提交

answer

#include <iostream>
#include <bitset>
#include <algorithm>
#include <string.h>
#include <iomanip>
#include <math.h>
#include <string>
#include <vector>
#include <queue>
#include <set>
#include <map>
#define fst first
#define scd second
#define ll long long
#define db double
#define L(i, j, k) for (int i=(j); i<=(k); ++i)
#define R(i, j, k) for (int i=(j); i>=(k); --i)
#define mp make_pair
#define pii pair <int, int>
#define pll pair <ll, ll>
#define vi vector <int>
#define vl vector <ll>
#define eb emplace_back
#define pb push_back
#define sz(x) ((int) x.size())
#define ms(f, x) memset(f, x, sizeof (f))
#define ACN(i, h_u) for (int i=h_u; i; i=e[i].nxt)
using namespace std;
template <typename INT> void rd(INT &res) {
	res=0; bool f=false; char ch=getchar();
	while (ch<'0'||ch>'9') f|=(ch=='-'), ch=getchar();
	while (ch>='0'&&ch<='9') res=(res<<1)+(res<<3)+(ch^48), ch=getchar();
	res=(f?-res:res);
}
template <typename INT, typename ...Args>
void rd(INT &res, Args &..._res) { rd(res), rd(_res...); }
//dfs
const int maxn=1e6;
const int N=maxn+10;
set <int> e[N], s[N]; bool col[N]; int n, m, stk[N];
//wmr

//incra

//lottle
signed main() {
//	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
//	freopen("8544.in", "r", stdin);
//	freopen("8544.out", "w", stdout);
	int T; rd(T);
	while (T--) {
		rd(n, m);
		L(i, 0, n) set <int> ().swap(e[i]), set <int> ().swap(s[i]);
		L(i, 2, n) e[i].insert(i-1), e[i].insert(i+1);
		e[1].insert(n), e[1].insert(2); e[n].insert(n-1), e[n].insert(1);
		while (m--) { int u, v; rd(u, v); e[u+1].insert(v+1); e[v+1].insert(u+1); }
		L(i, 1, n) s[sz(e[i])].insert(i); int top=0;
		while (true) {
			int sign=!s[2].empty()?2:!s[1].empty()?1:0;
			if (sign) {
				int u=*s[sign].begin(); s[sign].erase(u); stk[++top]=u;
				for (int v: e[u]) s[sz(e[v])].erase(v), e[v].erase(u), s[sz(e[v])].insert(v);
			} else break;
		}
		while (top) col[stk[top]]=!col[*e[stk[top]].begin()], --top;
		L(i, 1, n) putchar(col[i]?'R':'B');
		puts("");
	} 
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 4ms
memory: 98364kb

input:

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

output:

RBR
RBRB
RBBRBR

result:

ok ok (3 test cases)

Test #2:

score: -100
Runtime Error

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:


result: