QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#609067#8544. Colorful Graph 2lottle1212RE 2ms22716kbC++142.0kb2024-10-04 10:29:392024-10-04 10:29:39

Judging History

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

  • [2024-10-04 10:29:39]
  • 评测
  • 测评结果:RE
  • 用时:2ms
  • 内存:22716kb
  • [2024-10-04 10:29:39]
  • 提交

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=2e5;
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;
		if (T<=5) 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;
		}
		if (T<=5) 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: 2ms
memory: 22716kb

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:

BBBBBBBBB
BBB
BBBBB
BBBBBB
BBBBBBBBB
BBB
BBBBBBB
BBBBBBB
BBBB
BBBBBB
BBBBBB
BBBBBBB
BBBBBBBB
BBB
BBBBBBBB
BBBBBBBB
BBB
BBBBBBBBBB
BBBBBBBB
BBBBBBBBBB
BBBBBBBBBB
BBBBBBBBBB
BBB
BBBBBBB
BBBBBB
BBBBBBBB
BBBB
BBBBBBB
BBBBBBBBBB
BBBBBBB
BBBBBBBB
BBBBBB
BBBBBB
BBB
BBB
BBBBBBBBB
BBBBBBB
BBBBB
BBBBBBBBBB
BB...

result: