UOJ Logo

NOI.AC

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#206865#3695. 染色 31024i1001071ms11612kbC++112.0kb2024-07-25 19:49:492024-07-25 20:17:34

answer

#include <iostream>
#include <vector>
#include <cstring>
#include <functional>

class GraphColorizer {
private:
    static const int MAX_POINTS = 200010;
    
    struct Edge {
        int to, next;
    };

    int n;
    std::vector<int> head;
    std::vector<Edge> edges;
    std::vector<std::vector<int>> last;
    std::vector<int> color;

    void add_edge(int u, int v) {
        edges.push_back({v, head[u]});
        head[u] = edges.size() - 1;
    }

    void dfs_color(int v) {
        for (int i = head[v]; i != -1; i = edges[i].next) {
            int u = edges[i].to;
            if (color[u] == -1) {
                color[u] = color[v] ^ 1;
                dfs_color(u);
            }
        }
    }

public:
    GraphColorizer() : head(MAX_POINTS, -1), last(2, std::vector<int>(MAX_POINTS)), color(MAX_POINTS, -1) {}

    void read_input() {
        std::cin >> n;
        for (int i = 1; i <= n; ++i) {
            int x, y;
            std::cin >> x >> y;
            
            auto connect = [&](int dim, int coord) {
                if (last[dim][coord]) {
                    add_edge(last[dim][coord], i);
                    add_edge(i, last[dim][coord]);
                    last[dim][coord] = 0;
                } else {
                    last[dim][coord] = i;
                }
            };

            connect(0, x);
            connect(1, y);
        }
    }

    void solve() {
        for (int i = 1; i <= n; ++i) {
            if (color[i] == -1) {
                color[i] = 0;
                dfs_color(i);
            }
        }
    }

    void print_result() {
        for (int i = 1; i <= n; ++i) {
            std::cout << (color[i] ? 'r' : 'b');
        }
        std::cout << std::endl;
    }
};

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    GraphColorizer colorizer;
    colorizer.read_input();
    colorizer.solve();
    colorizer.print_result();

    return 0;
}

详细

小提示:点击横条可展开更详细的信息

Test #1:

score: 5
Accepted
time: 0ms
memory: 4296kb

input:

5
1 1
1 2
2 1
2 2
2 3

output:

brrbb

result:

ok Correct.

Test #2:

score: 5
Accepted
time: 4ms
memory: 4292kb

input:

11
1 1
1 2
1 3
1 4
1 5
1 6
2 1
3 1
4 1
5 1
6 1

output:

brbrbrrbrbr

result:

ok Correct.

Test #3:

score: 5
Accepted
time: 0ms
memory: 4296kb

input:

20
35292 11764
188224 35292
82348 129404
188224 129404
199988 105876
47056 47056
70584 129404
23528 ...

output:

bbbrbrbbbbrbrbbbbbbr

result:

ok Correct.

Test #4:

score: 5
Accepted
time: 0ms
memory: 4296kb

input:

20
152932 152932
152932 199988
82348 47056
11764 70584
58820 129404
35292 70584
152932 11764
164696 ...

output:

brbrbbbbrrrbbrrbrrbb

result:

ok Correct.

Test #5:

score: 5
Accepted
time: 104ms
memory: 11072kb

input:

200000
143301 121101
146298 83139
156732 102897
16872 151848
88134 109890
444 60495
170718 198357
76...

output:

bbbbbbrrbrbrrrrbbrbbrbbbrrrrbbbrbrrbbrrbrrrbbrbbbrrbrbbbrbrbrbrbrbrrbbrrrrrbbrrrbrrrbrrrbbrbbrrrbrrr...

result:

ok Correct.

Test #6:

score: 5
Accepted
time: 98ms
memory: 10080kb

input:

200000
116550 40071
8769 14652
73815 165501
182817 1110
44844 63159
149517 10434
139305 110223
65601...

output:

bbbbbbbbbbbrrrbbbbrbbrbrbrrrbbbrbrrrrbrbrrrbrbrbrbbbrbrrbrrrrrbbrbbbrbbbbrbrbrbrrrrbrrbrrbrbbrrrbrbr...

result:

ok Correct.

Test #7:

score: 5
Accepted
time: 94ms
memory: 9828kb

input:

200000
125763 6771
136530 23088
77256 180819
138417 24864
173604 56499
71928 29304
158508 87801
1022...

output:

brbbbbrbrbrbbbbbbbbbrrrbbrbbrbrrrbrbbrbrbbbrbbbrbrrbrrrbrrrbrbbbbrrrbbrbbrbrbbrbrbbrbrbrbrrrrrbbrrbr...

result:

ok Correct.

Test #8:

score: 5
Accepted
time: 109ms
memory: 11612kb

input:

200000
7326 184815
133200 173493
57609 182595
157287 72261
181707 26640
138972 24420
175158 39294
47...

output:

brrbbbrrrbbbrrbbbbrrbrbbbrrbbrbbbrbrrbbrbbrbbbrbrrbrbrrrbbrrbbrrrbrrrbbrbbbbrbbrrrrrbbbbrbrrbrrbrrbb...

result:

ok Correct.

Test #9:

score: 5
Accepted
time: 3ms
memory: 4296kb

input:

500
87633 35952
51681 38199
107856 85386
173019 11235
182007 105609
56175 20223
85386 179760
173019 ...

output:

bbbbbbbrrbbrbrbbbrrrbrbrbbrrbrbrrrrrrbrbrbrrrrrbbbbbbrrbrbrbrbrrrbbbrrbbrrbbrrbbbbrrbbrrbrbbbbrrrrrb...

result:

ok Correct.

Test #10:

score: 5
Accepted
time: 0ms
memory: 4292kb

input:

500
159537 11235
103362 80892
168525 188748
197736 137067
31458 193242
6741 51681
15729 42693
103362...

output:

bbbbbbbrbrbrrrbrbbbrbrbbbbrrrbrrrbbrrbrrrbbbrrbbrrrbrbrrrrrrbbbrbrbrrrbrrrbrbrrrrbbrbrrrrbbrbbbrrbrr...

result:

ok Correct.

Test #11:

score: 5
Accepted
time: 2ms
memory: 4296kb

input:

500
4494 71904
13482 134820
4494 125832
173019 125832
197736 6741
53928 116844
125832 51681
170772 1...

output:

brrbbbbbrbrbbrbbrbbbrbrbbrbbbbrbbrrrrbbrbrrrrrrbrbbbrrrbbbbbbbrrrrbrbrrrbrbrrbrrbbrbbbbrrrrbrrbrrrrr...

result:

ok Correct.

Test #12:

score: 5
Accepted
time: 0ms
memory: 4296kb

input:

500
157290 29211
184254 26964
164031 137067
114597 157290
51681 74151
31458 159537
101115 121338
166...

output:

bbbrrbrbbbbbbbbbbbrrbbbrbbbrrrbbrbrrrrrrrbrrbrrbbrrbbbrrrbbrrrrrbrbbbrbrbbrbbbrrbrbrrbbrbbbrbbrrrrrr...

result:

ok Correct.

Test #13:

score: 5
Accepted
time: 60ms
memory: 9752kb

input:

200000
170718 158841
20202 169053
80364 115329
95238 38739
106560 135753
142080 78810
103896 142746
...

output:

bbrbbbbbbbbbbbrbbbbbbrbbrbbbbbbbrbbbbrrrbrrrrbrrbbrbbbbrbrbrrbbbrbbrrbrrrbrbrbrbrbrbrrbrrbbrbbbbrrrb...

result:

ok Correct.

Test #14:

score: 5
Accepted
time: 85ms
memory: 9752kb

input:

200000
81696 38406
177711 132756
26418 42180
197469 45843
123210 56721
60939 102453
142080 93240
892...

output:

brbbbbbbbrbbrbrbrrbbrrbbbrbbrbbrbrbbbbrrbrbbbbbrrrrrrbrrrrbbrbrbrbrbbbbbbrrbbbbbrbbbbbrrbbrbrrbrrbbr...

result:

ok Correct.

Test #15:

score: 5
Accepted
time: 95ms
memory: 10276kb

input:

200000
3570 199910
154750 137090
45050 135480
130650 78810
129810 54230
145330 62800
26120 80
21720 ...

output:

bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbrbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbrbbbbbbbbbbbbbbbrbrbbbbb...

result:

ok Correct.

Test #16:

score: 5
Accepted
time: 103ms
memory: 10804kb

input:

200000
2720 197690
140230 114140
40270 59060
117880 103080
153440 130950
68850 156160
157850 84770
8...

output:

bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbrbbbbbbbbbbbrbbbbbbbbbbbbbbbbbbbbb...

result:

ok Correct.

Test #17:

score: 5
Accepted
time: 89ms
memory: 7200kb

input:

200000
102535 149291
147682 51025
105695 115025
70806 196246
91546 77282
91631 149960
154689 21039
5...

output:

bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb...

result:

ok Correct.

Test #18:

score: 5
Accepted
time: 93ms
memory: 7200kb

input:

200000
176231 84342
116928 36840
113351 197968
158833 117226
21212 27293
185052 56398
56661 5475
180...

output:

bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbrb...

result:

ok Correct.

Test #19:

score: 5
Accepted
time: 63ms
memory: 7200kb

input:

199999
1 81950
12005 50000
1 7923
1 60166
8153 50000
1 51300
90570 50000
1 40683
31361 50000
46700 5...

output:

bbrbrrbbrbrbrrbrbrbrbbrbrbrrbbrrbbrrbrbbrbrrbbrrbrbrbbrrbbrrbrbbrrbbrbrbrrbrbrbrbbrbrbrrbbrbrbrbrrbr...

result:

ok Correct.

Test #20:

score: 5
Accepted
time: 69ms
memory: 7196kb

input:

199999
1 20395
1 160357
1 187184
1 129893
1 182796
1 165315
1 196432
1 70628
1 2891
1 90447
1 158806...

output:

brbrbrbrbrbrbrbrbrbrbrbrbrbrbrbrbrbrbrbrbrbrbrbrbrbrbrbrbrbrbrbrbrbrbrbrbrbrbrbrbrbrbrbrbrbrbrbrbrbr...

result:

ok Correct.