Submission #1277408

#TimeUsernameProblemLanguageResultExecution timeMemory
1277408MisterReaperBuilding Skyscrapers (CEOI19_skyscrapers)C++20
0 / 100
1924 ms21680 KiB
// File skyscrapers.cpp created on 09.10.2025 at 09:27:26 #include <bits/stdc++.h> using i64 = long long; #ifdef DEBUG #include "/home/ahmetalp/Desktop/Workplace/debug.h" #else #define debug(...) void(23) #endif constexpr int dxa[] = {+1, 0, -1, 0}; constexpr int dya[] = {0, +1, 0, -1}; int N, T; std::vector<std::pair<int, int>> A; std::set<std::pair<int, int>> blacks; std::map<std::pair<int, int>, int> id; std::map<std::pair<int, int>, bool> reached; void dfs(int x, int y) { if (!id.contains({x, y}) || reached[{x, y}]) { return; } reached[{x, y}] = true; for (int dx = -1; dx <= 1; ++dx) { for (int dy = -1; dy <= 1; ++dy) { int nx = x + dx; int ny = y + dy; dfs(nx, ny); } } } struct DSU { std::vector<int> f, siz; void init(int n) { f.assign(n, 0); siz.assign(n, 1); std::iota(f.begin(), f.end(), 0); } int get(int x) { while (x != f[x]) { x = f[x] = f[f[x]]; } return x; } bool unite(int a, int b) { a = get(a), b = get(b); if (a == b) { return false; } else if (siz[a] > siz[b]) { std::swap(a, b); } f[a] = b; siz[b] += siz[a]; return true; } bool same(int a, int b) { return get(a) == get(b); } int size(int x) { return siz[get(x)]; } } dsu; std::vector<int> vis; std::vector<int> onpq; std::priority_queue<std::tuple<int, int, int>> pq; bool is_black(int x, int y) { if (blacks.contains({x, y}) && vis[id[{x, y}]] != 2) { return true; } return false; } bool check(int x, int y) { if (!is_black(x, y)) { return false; } debug("check", x, y); for (int d = 0; d < 2; ++d) { int nx0 = x + dxa[(1 + d)]; int ny0 = y + dya[(1 + d)]; int nx1 = x + dxa[(3 + d) % 4]; int ny1 = y + dya[(3 + d) % 4]; // debug(nx0, ny0, nx1, ny1); // debug(x + dxa[d], y + dya[d]); // debug(x + dxa[2 + d], y + dya[2 + d]); // debug(is_black(x + dxa[d], y + dya[d])); // debug(is_black(x + dxa[2 + d], y + dya[2 + d])); // debug(dsu.get(id[{nx0, ny0}]), dsu.get(id[{nx1, ny1}])); // debug(dsu.same(id[{nx0, ny0}], id[{nx1, ny1}])); if (is_black(x + dxa[d], y + dya[d]) && is_black(x + dxa[2 + d], y + dya[2 + d]) && dsu.same(id[{nx0, ny0}], id[{nx1, ny1}])) { return false; } } for (int d = 0; d < 4; ++d) { int nx0 = x + dxa[d]; int ny0 = y + dya[d]; int nx1 = x + dxa[(1 + d) % 4]; int ny1 = y + dya[(1 + d) % 4]; int nx2 = x + dxa[d] + dxa[(1 + d) % 4]; int ny2 = y + dya[d] + dya[(1 + d) % 4]; if (!is_black(nx0, ny0) && !is_black(nx1, ny1) && is_black(nx2, ny2)) { int cnt = 0; for (int dx = -1; dx <= 1; ++dx) { for (int dy = -1; dy <= 1; ++dy) { if (dx == 0 && dy == 0) { continue; } int nx = x + dx; int ny = y + dy; if (nx == nx0 && nx == ny0) { continue; } if (nx == nx1 && nx == ny1) { continue; } if (nx == nx2 && nx == ny2) { continue; } cnt += is_black(nx, ny); } } if (cnt > 0) { return false; } } } return true; } void domerge(int x, int y) { assert(id.contains({x, y}) && !is_black(x, y)); for (int d = 0; d < 4; ++d) { int nx = x + dxa[d]; int ny = y + dya[d]; if (!id.contains({nx, ny}) || is_black(nx, ny)) { continue; } if (dsu.unite(id[{x, y}], id[{nx, ny}])) { debug("dsu", x, y, nx, ny); } } } void fill(int x, int y) { if (!id.contains({x, y})) { return; } if (vis[id[{x, y}]] == 0) { vis[id[{x, y}]] = 1; } if (!is_black(x, y)) { domerge(x, y); } for (int dx = -1; dx <= 1; ++dx) { for (int dy = -1; dy <= 1; ++dy) { int nx = x + dx; int ny = y + dy; if (!id.contains({nx, ny})) { continue; } if (!is_black(nx, ny)) { continue; } if (check(nx, ny)) { if (onpq[id[{nx, ny}]] == 0) { onpq[id[{nx, ny}]] = 1; pq.emplace(id[{nx, ny}], nx, ny); } } } } if (is_black(x, y)) { return; } for (int dx = -1; dx <= 1; ++dx) { for (int dy = -1; dy <= 1; ++dy) { int nx = x + dx; int ny = y + dy; if (!id.contains({nx, ny}) || vis[id[{nx, ny}]] != 0) { continue; } fill(nx, ny); } } } int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); std::cin >> N >> T; A.resize(N); for (int i = 0; i < N; ++i) { std::cin >> A[i].first >> A[i].second; id[A[i]] = i; blacks.emplace(A[i]); } dfs(A[0].first, A[0].second); if (reached.size() != id.size()) { std::cout << "NO\n"; return 0; } int cnt = N; for (auto[x, y] : A) { for (int dx = -1; dx <= 1; ++dx) { for (int dy = -1; dy <= 1; ++dy) { int nx = x + dx; int ny = y + dy; if (!id.contains({nx, ny})) { id[{nx, ny}] = cnt; cnt++; } } } } std::pair<int, int> pnt = A[0]; for (auto[x, _] : id) { pnt = std::min(pnt, x); } vis.assign(id.size(), 0); onpq.assign(id.size(), 0); dsu.init(id.size()); fill(pnt.first, pnt.second); std::vector<int> ans; while (!pq.empty()) { debug(pq); auto[val, x, y] = pq.top(); pq.pop(); onpq[id[{x, y}]] = 0; if (!check(x, y)) { continue; } debug("black", x, y); debug(); debug(); debug(); debug(); vis[id[{x, y}]] = 2; fill(x, y); domerge(x, y); ans.emplace_back(id[{x, y}]); } debug(ans); assert(int(ans.size()) == N); std::reverse(ans.begin(), ans.end()); std::cout << "YES\n"; for (auto i : ans) { std::cout << i + 1 << " \n"[i == ans.back()]; } return 0; }
#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...
#Verdict Execution timeMemoryGrader output
Fetching results...