QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#387853 | #8544. Colorful Graph 2 | ucup-team027# | TL | 2874ms | 10460kb | C++20 | 3.0kb | 2024-04-12 22:02:38 | 2024-04-12 22:02:38 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
void solve() {
int n, m; cin >> n >> m;
vector<vector<int>> g(n);
set<pair<int, int>> edges;
for (int i = 0; i < m; i++) {
int x, y; cin >> x >> y;
g[x].push_back(y);
g[y].push_back(x);
edges.insert({x, y});
edges.insert({y, x});
}
for (int i = 0; i < n; i++) {
g[i].push_back((i+1) % n);
}
map<pair<int, int>, int> nxt;
for (int piv = 0; piv < n; piv++) {
sort(g[piv].begin(), g[piv].end(), [&](int x, int y){
if (x < piv && y < piv) return x < y;
if (x > piv && y > piv) return x < y;
if (x > piv) return true;
return false;
});
for (int i = 1; i < g[piv].size(); i++) {
nxt[{g[piv][i-1], piv}] = g[piv][i];
}
nxt[{g[piv].back(), piv}] = (piv-1+n) % n;
}
/*
for (auto [p, nn]: nxt) {
cout << p.first << ' ' << p.second << ' ' << nn << '\n';
}
*/
vector<vector<int>> pols;
set<pair<int, int>> vis;
for (auto [pp, nxx]: nxt) {
auto [x, y] = pp;
if (vis.count({x, y})) continue;
vector<int> pol; pol.push_back(x);
int curx = x, cury = y;
while (!vis.count({curx, cury})) {
vis.insert({curx, cury});
pol.push_back(cury);
int nx = nxt[{curx, cury}];
curx = cury;
cury = nx;
}
/*
cout << "POLYGON\n";
for (int i: pol) cout << i << ' ';
cout << '\n';
*/
pols.push_back(pol);
}
map<pair<int, int>, vector<int>> mpe;
for (int j = 0; j < pols.size(); j++) {
auto &pol = pols[j];
for (int i = 1; i < pol.size(); i++) {
int x = pol[i], y = pol[i-1];
if (x > y) swap(x, y);
if (edges.count({x, y})) {
mpe[{x, y}].push_back(j);
}
}
}
int sz = pols.size();
vector<vector<int>> g2(sz);
for (auto [pp, ed]: mpe) {
g2[ed[0]].push_back(ed[1]);
g2[ed[1]].push_back(ed[0]);
}
vector<int> ans(n, -1);
stack<int> st;
st.push(0);
vector<int> vis2(sz);
while (st.size()) {
int u = st.top(); st.pop();
vis2[u] = 1;
int has0 = 0, has1 = 0;
for (int i: pols[u]) {
if (ans[i] == 0) has0 = 1;
if (ans[i] == 1) has1 = 1;
}
int col;
if (has0 == 0) col = 0;
else col = 1;
for (int i: pols[u]) {
if (ans[i] != -1) continue;
ans[i] = col;
col ^= 1;
}
for (int v: g2[u]) {
if (vis2[v]) continue;
st.push(v);
}
}
for (int i: ans) if (i) cout << "R"; else cout << "B";
cout << '\n';
}
signed main(){
ios::sync_with_stdio(0), cin.tie(0);
int t; cin >> t;
while (t--) {
solve();
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3632kb
input:
3 3 0 4 1 1 3 6 3 0 2 2 4 4 0
output:
BBR BBRR BBRBRR
result:
ok ok (3 test cases)
Test #2:
score: 0
Accepted
time: 566ms
memory: 3888kb
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:
BBRBRBRRR BBR BBRBR BBRBRR BBRRBRRBR BBR BBRRRBR BBRRRRR BBRR BBRBRR BBRRBR BBRBRRR BBRRRRBR BBR BBRRRBRR BBRRRRBR BBR BBRBRRRRBR BBRRBRRR BBRBRBRRRR BBRRBRRBRR BBRRRBRBRR BBR BBRBRBR BBRRRR BBRRBRBR BBRR BBRBRRR BBRRRRBRBR BBRRRBR BBRBRBRR BBRRRR BBRBRR BBR BBR BBRRRRBRR BBRBRBR BBRRR BBRBRRBRRR BB...
result:
ok ok (100000 test cases)
Test #3:
score: 0
Accepted
time: 374ms
memory: 3656kb
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:
BRRBRRBR BBRRRRR BRBR BRBRBBRR BBR BBR BBRRBRBR BBR BBRRBRRBR BBRBRBR BRBRRR BBRRRBR BRBRR BRRRRBRRBR BBBRR BBR BRBRBRRBR BBR BBRRR BBRBRBRBR BBRRBR BBRRBRBR BBRBR BRBRBRBR BRBRR BRBRBRBR BBRRRBR BRBRRBBRRR BRBRRRBRR BBRRRBRBR BRBRBR BBRRRBR BBR BBRBRBRRBR BBRRRR BBRBRRRBR BBRBR BRRBBRRRBR BBRBR BBR...
result:
ok ok (100000 test cases)
Test #4:
score: 0
Accepted
time: 2254ms
memory: 3948kb
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:
BBRBRBRBRBRBRRBRBRBRRBRBRRRRRRBRBRRRBRRBRRBRRRBRBRBRRBRBRRBRBRRBRBRBRRRBRRRRRR BBRRRRBRRBRRRBRBRBRBRRBRRRBRRRBRRBRRBRBRBRBRBRRRRRBRRRRRBRRBRBRRBRRBRRRRBRBRRRRRRBRRRRBR BBRBRRBRRBRBRBRRBRBRRBRBRBRRRBRRBRRBRRRRBRRRRBRRRBRBRRBRBRRBRBRRBRBRRBRBRRBR BBRRBRRRBRBRBRBRRRRRBRRBRBRRBRBRRRBRRRBRRRBRBRRBRBRRBRB...
result:
ok ok (19452 test cases)
Test #5:
score: 0
Accepted
time: 1348ms
memory: 3912kb
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:
BBRRRBRRRBRBRBRBRBRRBRBRRRRBRBRRBRRBRRRRRBRRBRBRRRBRBRBRBRBRBRBRBRRRRBRR BRRBRBRBRBBRRBRBRBBRRBRBRBBRRBBRBRRBRBRBRBR BBRBRBRBRBRBRBRBBRRBRRRRBRBRBRBRBRBRBRRRBRBRBRRBRRBRBRBRBRBRBRBRBRBRRRBR BRBRRBRRBRBRRRBRRBRBBRBRRBRBRBRBRBBBRRBRRBRBRBRBBRBRBRBRBRBBRRBRBBRRRRBRRRRBRRBRRRBRBRR BRRBRRBRRRBRRBRRBRBRBR...
result:
ok ok (19457 test cases)
Test #6:
score: 0
Accepted
time: 2651ms
memory: 4356kb
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:
BBRRBRRBRRBRBRRRRBRRRRBRBRBRRBRRRBRBRRRBRRRBRRBRBRBRRRBRRRBRBRRBRBRRBRRRBRRRBRBRBRRBRBRRBRRRRBRRBRRRBRRRBRBRBRRBRBRRBRRRBRBRRRBRBRRRBRRBRRRRRBRBRRBRBRBRRBRRRRBRBRRBRBRRBRBRBRRRBRBRRBRBRRRBRBRRRRBRRBRRRBRRRBRRRRBRBRRRBRRRRRRBRBRRBRBRRBRBRRRRBRRBRBRBRRBRBRBRRBRRRBRRBRBRRRBRRRBRBRBRRBRRRRRRRBRRBRBRRBRR...
result:
ok ok (2011 test cases)
Test #7:
score: 0
Accepted
time: 1561ms
memory: 4312kb
input:
1958 908 775 369 374 638 644 308 310 686 758 596 593 432 410 730 732 556 476 356 354 711 742 149 144 582 609 714 716 895 667 831 837 37 10 17 13 880 882 453 457 266 269 297 301 577 113 114 576 115 166 716 727 130 163 708 745 337 317 250 303 712 714 893 668 344 351 319 322 276 264 107 109 567 466 415...
output:
BBRRRBRBRBRBRRRBRBRBRRRBRRBRBRRBRBRRRBRBRBRBRRBRRBRBRRBRBRRBRRRBRRRRBRBRBRBRBRBRRBRBRRRBRRBRRRBRRBRRRBRBRBRRBRRBRRBRRBRRRBRBRRRBRRBRRBRRBBRRRBRBRBRBRBRBRBRRBRRBRBRRRBRBRRBRRBRRBRBRBRRBRBRBRBRBBRRRRRBBRRRBRRRBRBRRBRRBRBRRBRBRRRBRBRRRBRBRRRRBRRRRRBRRRBRBRRBRBBRRRBRBRRRBRBRRRBRBRBRBRBRRBRRRBRBRBRBRRBRR...
result:
ok ok (1958 test cases)
Test #8:
score: 0
Accepted
time: 2874ms
memory: 10460kb
input:
204 1066 1063 466 462 569 566 239 241 125 134 418 422 147 142 99 103 380 305 100 103 589 585 336 315 126 134 176 1042 995 431 966 975 857 854 112 110 841 862 1018 1015 202 266 860 853 86 94 254 252 454 448 523 675 864 867 221 216 710 707 184 286 984 931 70 65 165 31 634 642 557 555 763 770 537 529 4...
output:
BBRRBRRBRRBRBRRBRBRRBRRBRRBRRBRBRRRBRRBRRBRBRBRRBRRBRBRBRBRRBRRRRRRBRBRBRBRBRBRBRRRBRRBRRBRBRBRRBRRBRRBRRBRRBRBRRBRRRBRRRBRRRRRRRRBRRRBRRRBRRBRRBRBRBRBRBRBRRBRBRRRBRRRBRBRBRBRBRRBRRRBRRRRBRBRBRBRBRBRBRRRRRRBRBRRRRBRRRRBRBRRBRBRBRRBRBRBRBRBRBRRBRBRRRBRBRRBRBRBRBRRRRRBRBRBRBRBRBRBRRBRRRBRBRRRRRBRRRBRB...
result:
ok ok (204 test cases)
Test #9:
score: 0
Accepted
time: 1729ms
memory: 10216kb
input:
203 2148 1719 1557 1562 1834 1826 661 646 1733 1747 668 670 1449 1497 256 254 1571 1569 1726 1701 142 135 1981 1979 1966 1992 2107 2104 1209 1196 752 895 2035 2033 621 618 3 6 2093 2110 437 479 641 643 566 519 640 628 626 678 1694 1726 1520 1522 1434 1430 1127 1130 2021 2014 1349 1347 378 383 1475 1...
output:
BBRRRBRRBBBRRBRBRRRRRBRBRRRBRBRRRRBRBRBRBRRRRRBBBRRRRRBBRRBBRRRBRRBRRRRRBRRRRRBRRBBRRBRRBRBBRBRRBRBRBRRRBRBRRBRBRRRBRRBRRRRBRBRRRBRBRBRBRRRRBRRBRBRBRRBRRRBRBRRBRRRBRBRBRBRRRRRRBRRBRRBRRRBRBRRRBRBRBRBRBRBRBRRRRBRBRRRBRBBBRRRRBRBRBRBRRRBRBBRRBRBRRBRBRBRBRRBRRRBRBRBBRBRBRBRRBRBRRBRRBBRRRBRBRBRBRBRBRRRR...
result:
ok ok (203 test cases)
Test #10:
score: -100
Time Limit Exceeded
input:
28 75972 75969 72982 72984 57195 57198 62938 62906 8473 8556 37842 37858 33380 33354 1503 1501 6490 6468 3231 3212 66806 66785 66178 66191 16644 16646 28283 28285 7797 7805 27304 50764 62274 62338 70175 70182 37760 37762 10872 10845 2554 2552 22131 22129 25754 25685 30543 30473 48058 48056 49029 490...
output:
BBRRRBRBRBRRRRBRBRRBRRRBRBRRRRBRBRRBRBRRBRBRRRBRBRRRBRBRRBRRBRBRBRRBRRBRBRRRRBRRRRBRBRRBRRBRBRRRBRRRRBRRRRRRBRBRRBRBRRRBRRRRRBRRRRRBRBRRBRBRRBRRBRRBRBRRRBRBRBRBRRRBRRRBRRRRBRRBRBRBRBRBRRBRRRRRBRBRBRRRRBRRBRRRBRRRRRBRBRBRRBRBRRRRBRBRRBRRBRRRRRRRBRBRRBRRRRBRBRRBRRBRRRBRRRRBRBRBRBRBRBRRBRBRRRRBRRRBRBRR...