QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#876700#8544. Colorful Graph 2JEdwardTL 685ms3712kbC++202.1kb2025-01-31 11:17:452025-01-31 11:17:47

Judging History

This is the latest submission verdict.

  • [2025-01-31 11:17:47]
  • Judged
  • Verdict: TL
  • Time: 685ms
  • Memory: 3712kb
  • [2025-01-31 11:17:45]
  • Submitted

answer

#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(0), cin.tie(0)
#define int long long
#define endl '\n'
#define lowbit(x) (x & -x)
#define all(s) s.begin(), s.end()
#define pii pair<int,int>
#define ls(x) (x<<1)
#define rs(x) (x<<1|1)
#define here system("pause")
using namespace std;
template <class T>
inline void read(T &x){
	x = 0;
	char c = getchar();
	bool f = 0;
	for (; !isdigit(c); c = getchar()) f ^= (c == '-');
	for (; isdigit(c); c = getchar()) x = (x << 3) + (x << 1) + (c ^ 48);
	x = f ? -x : x;
}
template <class T>
inline void write(T x){
	if (x < 0) putchar('-'), x = -x;
	if (x < 10) putchar(x + 48);
	else write(x / 10), putchar(x % 10 + 48);
}
template<typename T> void chkmin(T& lhs, const T& rhs) { lhs = lhs > rhs ? rhs : lhs; }
template<typename T> void chkmax(T& lhs, const T& rhs) { lhs = lhs < rhs ? rhs : lhs; }

const int N = 2e3 + 4;
const int mod = 998244353;
const int INF = 8e18 + 9;
const double eps = 1e-9;
const double Pi = acos(-1);
inline int pow(int a, int b, int p){ int res = 1%p; while(b){ if(b&1) res=res*a%p; a=a*a%p, b>>=1;} return res;}
inline int inv(int a, int p){ return pow(a,p-2,p)%p;}
mt19937 rnd(chrono::duration_cast<chrono::nanoseconds>(chrono::system_clock::now().time_since_epoch()).count());
int randint(int L, int R) {
	uniform_int_distribution<int> dist(L, R);
	return dist(rnd);
}
inline void sol() {
	int n, k;
	cin >> n >> k;
	vector<vector<int>> adj(n);
	vector<int> dis(n, INF);
	for(int i = 0; i < n; i++) {
		int u = i, v = i + 1 >= n ? i + 1 - n : i + 1;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	for(int i = 0; i < k; i++) {
		int u, v;
		cin >> u >> v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	auto dfs = [&](auto dfs, int u, int fa) -> void {
		for(auto v : adj[u]) {
			if(v == fa) continue;
			if(dis[u] + 1 < dis[v]) {
				dis[v] = dis[u] + 1;
				dfs(dfs, v, u);
			}
		}
	};
	dis[0] = 0;
	dfs(dfs, 0, -1);
	for(int i = 0; i < n; i++) {
		cout << (dis[i] & 1 ? 'R' : 'B');
	}
	cout << endl;
}

signed main(){
	IOS;
	int tc = 1;
	cin >> tc;
	cout << fixed << setprecision(10);
	while(tc--){
		sol();
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3584kb

input:

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

output:

BRR
BRBR
BRRBRR

result:

ok ok (3 test cases)

Test #2:

score: 0
Accepted
time: 93ms
memory: 3584kb

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:

BRRBBBRRR
BRR
BRRBR
BRBRBR
BRBBRRBBR
BRR
BRBRRBR
BRBBBRR
BRBR
BRRBRR
BRBRBR
BRBBBRR
BRBBBRBR
BRR
BRRRRBRR
BRBBBRBR
BRR
BRRBBRRRBR
BRBBRRBR
BRBBRRBRBR
BRBRBRBRBR
BRRRBRRBBR
BRR
BRBRBBR
BRBBBR
BRRBBBBR
BRBR
BRRBRBR
BRBRBBRRBR
BRBRRBR
BRBRBRBR
BRBBBR
BRRBRR
BRR
BRR
BRBBBRRBR
BRBBRBR
BRBRR
BRBRRBBRBR
BR...

result:

ok ok (100000 test cases)

Test #3:

score: 0
Accepted
time: 71ms
memory: 3584kb

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:

BRBBRBBR
BRBBRRR
BRBR
BRBRBRBR
BRR
BRR
BRBBRRBR
BRR
BRBRBRRBR
BRBRRBR
BRBBRR
BRBRRBR
BRBRR
BRBRRBRRBR
BRBBR
BRR
BRBRBRRBR
BRR
BRBBR
BRBRBBRBR
BRBRBR
BRBBRRBR
BRBBR
BRBBRRBR
BRBRR
BRBRBBBR
BRBBRBR
BRBRBBRBRR
BRBRRBBBR
BRBRBBRBR
BRBRBR
BRBRRBR
BRR
BRBRBBRBBR
BRBBRR
BRBRBBRBR
BRBBR
BRBRBRBRBR
BRRBR
BRR...

result:

ok ok (100000 test cases)

Test #4:

score: 0
Accepted
time: 685ms
memory: 3712kb

input:

19452
78 75
50 52
61 64
19 21
21 27
52 54
75 5
47 58
15 13
47 66
69 71
66 68
33 36
27 32
15 17
66 60
74 7
63 61
41 13
45 71
30 28
68 71
18 13
13 42
47 55
76 1
19 32
61 66
5 2
22 24
74 71
42 44
59 47
66 46
26 21
49 52
56 58
54 47
52 48
21 25
19 41
10 42
45 74
48 54
39 41
41 18
75 6
39 33
33 37
31 28
...

output:

BRBRRBRRBRRBBBRRBBRRBBRBRRRBRBBRBBRBRBBRRBRRBBRBRBRRBBRRRBRRBBRRRBRBRRRBRBRBRR
BRRRBRBRBRBBRRBBBRBRBRBRBRBRBRBRRRRBRBRRRBRRBBRRRRBRBBBBRRBBRBBBRBBRBBRBRBRBBBBBBRBBBRBR
BRRBRBRBRBRRRRRBRBBRBRRBBRBBBRBRBBRBRBRRBRBRRBBRBRRRBRRRBRBRBBBRBRBRRBRRBRBR
BRBRBRBRBBBBBBBBRRRRBRBRBBRBBBRBBRRBBRRBBRBRBBRBRBBRBRB...

result:

ok ok (19452 test cases)

Test #5:

score: 0
Accepted
time: 434ms
memory: 3712kb

input:

19457
72 56
1 70
0 70
2 70
19 69
64 42
34 32
55 57
22 68
54 48
26 28
41 23
13 10
68 21
62 59
29 26
53 51
30 41
41 38
15 7
66 64
3 15
23 42
47 54
9 7
6 4
47 42
64 22
67 22
17 3
37 35
23 64
30 38
59 61
24 41
70 17
19 70
30 32
17 19
19 21
14 7
2 17
29 24
6 15
69 21
62 55
9 14
16 3
25 29
15 4
53 50
35 3...

output:

BRBRBRRRBBBRRBRBRBRBRRBRBRBRBRRBBRRBRBRRRBBRBRBRBRRRRBRBRRBBRBRBRBRBRBRR
BRBBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBRBR
BRBRBRBRBRRBRBRBRBRBRBRBBRBRBRRBRBRBRRBBRBRBRBRRRBRBRRBRBRBRBRBRBRBRBRBR
BRBRRBRBBRBRBRRBRBRRBRRRBRRBRBRBRRBRBRBRBRBRBRRBRBRBRBBRBBRBBRBRBRBRRRBBRBRBBRBRBBRBRBR
BRBRBRRBRBBRBRRBRRRBRB...

result:

ok ok (19457 test cases)

Test #6:

score: -100
Time Limit Exceeded

input:

2011
404 401
326 324
85 82
297 38
198 201
196 205
299 8
206 188
326 329
280 277
378 5
155 153
367 360
282 277
378 6
375 377
315 317
92 81
227 229
174 176
141 145
276 272
218 216
43 45
205 188
163 221
205 193
223 226
307 317
387 383
23 33
52 50
199 201
367 358
394 396
177 179
170 167
104 102
263 265
...

output:

BRBBRRBRBRBRRBRBBRBRBBRBRBBRRBRBRRBBRBBRBBRRBRBRBBBBRRBRBRBRBRBRRRRBRRBRRBBRBRRRBBRBBRBRRBRBRBRBRBBRRBBRBBBRRRRBRBBRBBRBBBRBRBRRBBRBBRRBRBRBRBRBRRRBRRBRRBRRRBRBRRBRRRRBRBRBRRBRBRBRBBRRBRBBBRRRRRBRRBBRRBBRRBRBRRBBBRBBRRBBRBBRBRBBBRRBRRBRBRBBRRBRRBRRRBBBBRBRBBRBRBBBRBRBRRBBRBBBBRBRBBRRRRRBBRBRBBRRBRRB...

result: