ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#206865 | #3695. 染色 3 | 1024i | 100 | 1071ms | 11612kb | C++11 | 2.0kb | 2024-07-25 19:49:49 | 2024-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;
}
Details
小提示:点击横条可展开更详细的信息
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.