Submission #804131

#TimeUsernameProblemLanguageResultExecution timeMemory
804131finn__Fountain Parks (IOI21_parks)C++17
45 / 100
306 ms48424 KiB
#include "parks.h" #include <bits/stdc++.h> using namespace std; template <size_t N> struct dsu { int64_t p[N]; dsu() { fill(p, p + N, -1); } int64_t repr(int64_t u) { return p[u] < 0 ? u : p[u] = repr(p[u]); } bool merge(int64_t i, int64_t j) { i = repr(i); j = repr(j); if (i == j) return 0; if (p[i] > p[j]) swap(i, j); p[i] += p[j]; p[j] = i; return 1; } bool same_set(int64_t i, int64_t j) { return repr(i) == repr(j); } int64_t set_size(int64_t i) { return -p[repr(i)]; } void reset() { fill(p.begin(), p.end(), -1); } }; struct fountain { int x, y; size_t i; }; constexpr size_t N = 200000; fountain f[N]; vector<pair<size_t, size_t>> edges; vector<uint32_t> dual[N]; dsu<N> d; set<pair<int, int>> points, marked; set<tuple<int, int, uint32_t>> midpoints; pair<int, int> dual_coords[N]; bitset<N> visited; size_t l; void mark_cut_points(uint32_t u) { visited[u] = 1; for (auto const &v : dual[u]) if (!visited[v]) { if (u == l) { bool placed = 0; for (size_t i = 0; i < 4; ++i) { pair<int, int> cand = {dual_coords[v].first + (-2 + (i & 1) * 4) * !(i & 2), dual_coords[v].second + (-2 + (i & 1) * 4) * (bool)(i & 2)}; bool not_present = 1; for (auto const &w : dual[v]) if (w != u) not_present &= dual_coords[w] != cand; if (not_present) { marked.emplace((dual_coords[v].first + cand.first) >> 1, (dual_coords[v].second + cand.second) >> 1); placed = 1; break; } } assert(placed); } else { marked.emplace((dual_coords[u].first + dual_coords[v].first) >> 1, (dual_coords[u].second + dual_coords[v].second) >> 1); } mark_cut_points(v); } } int construct_roads(vector<int> x, vector<int> y) { size_t n = x.size(); for (size_t i = 0; i < n; ++i) points.emplace(x[i], y[i]); for (size_t i = 0; i < n; ++i) if (points.find({x[i] + 2, y[i]}) != points.end() && points.find({x[i], y[i] + 2}) != points.end() && points.find({x[i] + 2, y[i] + 2}) != points.end()) midpoints.emplace(x[i] + 1, y[i] + 1, l++), dual_coords[l - 1] = {x[i] + 1, y[i] + 1}; for (auto const &[x, y, i] : midpoints) { auto it = midpoints.lower_bound({x + 2, y, 0}); if (it != midpoints.end() && get<0>(*it) == x + 2 && get<1>(*it) == y) { if (((x & 3) == 1) ^ ((y & 3) == 3)) dual[get<2>(*it)].push_back(i); else dual[i].push_back(get<2>(*it)); } it = midpoints.lower_bound({x, y + 2, 0}); if (it != midpoints.end() && get<0>(*it) == x && get<1>(*it) == y + 2) { if (((y & 3) == 1) ^ ((x & 3) == 3)) dual[i].push_back(get<2>(*it)); else dual[get<2>(*it)].push_back(i); } } for (size_t i = 0; i < l; ++i) if (dual[i].size() < 4) { int x = dual_coords[i].first, y = dual_coords[i].second; for (size_t i = 0; i < 4; ++i) { pair<int, int> cand = {dual_coords[i].first + (-2 + (i & 1) * 4) * !(i & 2), dual_coords[i].second + (-2 + (i & 1) * 4) * (bool)(i & 2)}; bool not_present = 1; for (auto const &w : dual[i]) if (w != l) not_present &= dual_coords[w] != cand; if (not_present) { if (cand.second == y && ((min(x, cand.first) & 3) == 1) ^ ((y & 3) == 3) ^ x > cand.first) { dual[l].push_back(i); break; } if (cand.first == x && ((min(y, cand.second) & 3) == 1) ^ ((x & 3) == 3) ^ y > cand.second) { dual[l].push_back(i); break; } } } } mark_cut_points(l); for (size_t i = 0; i < x.size(); ++i) f[i].i = i, f[i].x = x[i], f[i].y = y[i]; sort(f, f + n, [](auto const &a, auto const &b) { return a.y == b.y ? a.x < b.x : a.y < b.y; }); for (size_t i = 0; i < n;) { size_t j = i; while (j < n && f[j].y == f[i].y) ++j; for (size_t k = i + 1; k < j; ++k) if (f[k - 1].x + 2 == f[k].x) if (marked.find({f[k - 1].x + 1, f[k - 1].y}) == marked.end() && d.merge(f[k - 1].i, f[k].i)) edges.emplace_back(f[k - 1].i, f[k].i); if (f[j].y == f[i].y + 2) { size_t k = j; while (i < j && k < n && f[k].y == f[j].y) { if (f[i].x < f[k].x) ++i; else if (f[k].x < f[i].x) ++k; else { if (marked.find({f[i].x, f[i].y + 1}) == marked.end() && d.merge(f[i].i, f[k].i)) edges.emplace_back(f[k].i, f[i].i); ++i; ++k; } } } i = j; } if (d.set_size(0) != n) return 0; vector<int> u, v, a, b; for (auto const &[i, j] : edges) { u.push_back(i); v.push_back(j); if (x[i] == x[j]) { b.push_back((y[i] + y[j]) >> 1); if (((x[i] & 3) == 2) ^ ((min(y[i], y[j]) & 3) == 2)) a.push_back(x[i] - 1); else a.push_back(x[i] + 1); } else { a.push_back((x[i] + x[j]) >> 1); if (((y[i] & 3) == 2) ^ ((min(x[i], x[j]) & 3) == 2)) b.push_back(y[i] + 1); else b.push_back(y[i] - 1); } } build(u, v, a, b); return 1; }

Compilation message (stderr)

parks.cpp: In function 'int construct_roads(std::vector<int>, std::vector<int>)':
parks.cpp:133:98: warning: suggest parentheses around comparison in operand of '^' [-Wparentheses]
  133 |                     if (cand.second == y && ((min(x, cand.first) & 3) == 1) ^ ((y & 3) == 3) ^ x > cand.first)
      |                                                                                                ~~^~~~~~~~~~~~
parks.cpp:138:98: warning: suggest parentheses around comparison in operand of '^' [-Wparentheses]
  138 |                     if (cand.first == x && ((min(y, cand.second) & 3) == 1) ^ ((x & 3) == 3) ^ y > cand.second)
      |                                                                                                ~~^~~~~~~~~~~~~
parks.cpp:188:23: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'size_t' {aka 'long unsigned int'} [-Wsign-compare]
  188 |     if (d.set_size(0) != n)
      |         ~~~~~~~~~~~~~~^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...