| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1004469 |
2024-06-21T09:16:38 Z |
julian |
Fliper (COCI22_fliper) |
C++ |
|
355 ms |
84268 KB |
#include <bits/stdc++.h>
struct Obstacle {
size_t x, y;
char c;
size_t toL = std::numeric_limits<size_t>::max(), toR = std::numeric_limits<size_t>::max(), toT = std::numeric_limits<size_t>::max(), toB = std::numeric_limits<size_t>::max();
};
std::vector<long> uf_init(long n) {
std::vector<long> uf(n);
for (long i = 0; i < n; i++) {
uf[i] = i;
}
return uf;
}
long uf_find(std::vector<long>& uf, long i) {
if (uf[i] == i) return i;
return uf[i] = uf_find(uf, uf[i]);
}
void uf_union(std::vector<long>& uf, long a, long b) {
long aa = uf_find(uf, a);
long bb = uf_find(uf, b);
uf[aa] = bb;
}
void uf_converge(std::vector<long>& uf) {
for (size_t i = 0; i < uf.size(); i++) {
uf_find(uf, i);
}
}
int main() {
size_t n;
std::cin >> n;
std::vector<Obstacle> obstacles(n);
for (size_t i = 0; i < n; i++) {
size_t x, y;
char c;
std::cin >> x >> y >> c;
obstacles[i] = {x, y, c};
}
std::vector<long> uf = uf_init(2 * n + 1);
std::vector<size_t> xsort(n), ysort(n);
for (size_t i = 0; i < n; i++) {
xsort[i] = ysort[i] = i;
}
std::sort(xsort.begin(), xsort.end(), [&](size_t a, size_t b) {
return obstacles[a].x < obstacles[b].x;
});
std::sort(ysort.begin(), ysort.end(), [&](size_t a, size_t b) {
return obstacles[a].y < obstacles[b].y;
});
std::unordered_map<size_t, std::vector<size_t>> ymap, xmap;
for (size_t i = 0; i < n; i++) {
if (ymap.find(obstacles[xsort[i]].y) == ymap.end()) {
ymap[obstacles[xsort[i]].y] = std::vector<size_t>(1, xsort[i]);
} else {
ymap[obstacles[xsort[i]].y].push_back(xsort[i]);
}
if (xmap.find(obstacles[ysort[i]].x) == xmap.end()) {
xmap[obstacles[ysort[i]].x] = std::vector<size_t>(1, ysort[i]);
} else {
xmap[obstacles[ysort[i]].x].push_back(ysort[i]);
}
}
for (auto& [y, obst] : ymap) {
if (obstacles[obst[0]].c == '/') {
uf_union(uf, obst[0] * 2, 2 * n);
} else {
uf_union(uf, obst[0] * 2 + 1, 2 * n);
}
if (obstacles[obst[obst.size() - 1]].c == '/') {
uf_union(uf, obst[obst.size() - 1] * 2 + 1, 2 * n);
} else {
uf_union(uf, obst[obst.size() - 1] * 2, 2 * n);
}
for (size_t i = 0; i < obst.size() - 1; i++) {
if (obstacles[obst[i]].c == '/') {
if (obstacles[obst[i + 1]].c == '/') {
uf_union(uf, obst[i] * 2 + 1, obst[i + 1] * 2);
} else {
uf_union(uf, obst[i] * 2 + 1, obst[i + 1] * 2 + 1);
}
} else {
if (obstacles[obst[i + 1]].c == '/') {
uf_union(uf, obst[i] * 2, obst[i + 1] * 2);
} else {
uf_union(uf, obst[i] * 2, obst[i + 1] * 2 + 1);
}
}
}
}
for (auto& [x, obst] : xmap) {
if (obstacles[obst[0]].c == '/') {
uf_union(uf, obst[0] * 2 + 1, 2 * n);
} else {
uf_union(uf, obst[0] * 2 + 1, 2 * n);
}
if (obstacles[obst[obst.size() - 1]].c == '/') {
uf_union(uf, obst[obst.size() - 1] * 2, 2 * n);
} else {
uf_union(uf, obst[obst.size() - 1] * 2, 2 * n);
}
for (size_t i = 0; i < obst.size() - 1; i++) {
if (obstacles[obst[i]].c == '/') {
if (obstacles[obst[i + 1]].c == '/') {
uf_union(uf, obst[i] * 2, obst[i + 1] * 2 + 1);
} else {
uf_union(uf, obst[i] * 2, obst[i + 1] * 2 + 1);
}
} else {
if (obstacles[obst[i + 1]].c == '/') {
uf_union(uf, obst[i] * 2, obst[i + 1] * 2 + 1);
} else {
uf_union(uf, obst[i] * 2, obst[i + 1] * 2 + 1);
}
}
}
}
uf_converge(uf);
std::unordered_map<long, std::vector<std::pair<long, long>>> adj;
for (size_t i = 0; i < uf.size() - 1; i += 2) {
if (!(uf[i] == 2 * n && uf[i + 1] == 2 * n)) {
adj[uf[i]].push_back({uf[i + 1], i / 2});
adj[uf[i + 1]].push_back({uf[i], i / 2});
}
}
for (auto [k, v] : adj) {
if (k != 2 * n && v.size() % 8) {
std::cout << -1 << std::endl;
return 0;
}
}
std::stack<long> s;
s.push(2 * n);
long color = 0;
std::unordered_map<long, std::pair<std::vector<std::pair<long, long>>, std::vector<std::pair<long, long>>>> adj2;
// First coloring
while (!s.empty()) {
long v = s.top();
if (adj[v].empty()) {
s.pop();
} else {
auto [u, obstI] = adj[v][adj[v].size() - 1];
adj[v].erase(adj[v].end() - 1);
adj[u].erase(std::find(adj[u].begin(), adj[u].end(), std::pair<long, long>(v, obstI)));
s.push(u);
if (color == 0) {
adj2[v].first.push_back({u, obstI});
adj2[u].first.push_back({v, obstI});
} else {
adj2[v].second.push_back({u, obstI});
adj2[u].second.push_back({v, obstI});
}
color = (color + 1) % 2;
//std::cout << v << " " << u << " " << obstI << std::endl;
}
}
std::vector<long> colors(n, 9);
color = 0;
while (!s.empty()) s.pop();
s.push(n * 2);
// Second coloring (1)
while (!s.empty()) {
long v = s.top();
if (adj2[v].first.empty()) {
s.pop();
} else {
auto [u, obstI] = adj2[v].first[adj2[v].first.size() - 1];
adj2[v].first.erase(adj2[v].first.end() - 1);
adj2[u].first.erase(std::find(adj2[u].first.begin(), adj2[u].first.end(), std::pair<long, long>(v, obstI)));
s.push(u);
colors[obstI] = color + 1;
color = (color + 1) % 2;
//std::cout << v << " " << u << " " << obstI << std::endl;
}
}
color = 0;
while (!s.empty()) s.pop();
s.push(n * 2);
// Second coloring (2)
while (!s.empty()) {
long v = s.top();
if (adj2[v].second.empty()) {
s.pop();
} else {
auto [u, obstI] = adj2[v].second[adj2[v].second.size() - 1];
adj2[v].second.erase(adj2[v].second.end() - 1);
adj2[u].second.erase(std::find(adj2[u].second.begin(), adj2[u].second.end(), std::pair<long, long>(v, obstI)));
s.push(u);
colors[obstI] = color + 3;
color = (color + 1) % 2;
//std::cout << v << " " << u << " " << obstI << std::endl;
}
}
color = 0;
for (auto& c : colors) {
if (c == 9) {
c = color + 1;
color = (color + 1) % 4;
}
}
//std::cout << "COLORS" << std::endl;
for (auto c : colors) {
std::cout << c << " ";
}
std::cout << std::endl;
}
Compilation message
Main.cpp: In function 'int main()':
Main.cpp:82:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
82 | for (auto& [y, obst] : ymap) {
| ^
Main.cpp:112:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
112 | for (auto& [x, obst] : xmap) {
| ^
Main.cpp:147:15: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<long int>, long int>::value_type' {aka 'long int'} and 'size_t' {aka 'long unsigned int'} [-Wsign-compare]
147 | if (!(uf[i] == 2 * n && uf[i + 1] == 2 * n)) {
Main.cpp:147:37: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<long int>, long int>::value_type' {aka 'long int'} and 'size_t' {aka 'long unsigned int'} [-Wsign-compare]
147 | if (!(uf[i] == 2 * n && uf[i + 1] == 2 * n)) {
Main.cpp:153:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
153 | for (auto [k, v] : adj) {
| ^
Main.cpp:154:9: warning: comparison of integer expressions of different signedness: 'std::tuple_element<0, std::pair<const long int, std::vector<std::pair<long int, long int> > > >::type' {aka 'const long int'} and 'size_t' {aka 'long unsigned int'} [-Wsign-compare]
154 | if (k != 2 * n && v.size() % 8) {
| ~~^~~~~~~~
Main.cpp:176:9: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
176 | auto [u, obstI] = adj[v][adj[v].size() - 1];
| ^
Main.cpp:208:9: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
208 | auto [u, obstI] = adj2[v].first[adj2[v].first.size() - 1];
| ^
Main.cpp:232:9: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
232 | auto [u, obstI] = adj2[v].second[adj2[v].second.size() - 1];
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Color doesn't appear even times |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
355 ms |
84268 KB |
Color doesn't appear the same times |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Color doesn't appear even times |
| 2 |
Halted |
0 ms |
0 KB |
- |
