QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#387853#8544. Colorful Graph 2ucup-team027#TL 2874ms10460kbC++203.0kb2024-04-12 22:02:382024-04-12 22:02:38

Judging History

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

  • [2024-04-12 22:02:38]
  • 评测
  • 测评结果:TL
  • 用时:2874ms
  • 内存:10460kb
  • [2024-04-12 22:02:38]
  • 提交

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...

result: