QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#876699 | #8544. Colorful Graph 2 | JEdward | TL | 694ms | 3712kb | C++20 | 2.1kb | 2025-01-31 11:17:12 | 2025-01-31 11:17:21 |
Judging History
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: 96ms
memory: 3456kb
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: 72ms
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: 694ms
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: 433ms
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...