Submission #1240601

#TimeUsernameProblemLanguageResultExecution timeMemory
1240601trimkusFountain Parks (IOI21_parks)C++20
5 / 100
220 ms38156 KiB
#include "parks.h" #include <bits/stdc++.h> using namespace std; struct DSU { vector<int> e; DSU (int n) { e = vector<int>(n, -1); } int get(int x) { return e[x] < 0 ? x : e[x] = get(e[x]); } void unite(int x, int y) { x = get(x); y = get(y); if (x == y) return; if (e[x] > e[y]) swap(x, y); e[x] += e[y]; e[y] = x; } }; int construct_roads(std::vector<int> x, std::vector<int> y) { if (x.size() == 1) { build({}, {}, {}, {}); return 1; } vector<array<int, 3>> st; int N = x.size(); for (int i = 0; i < N; ++i) { st.push_back({x[i], y[i], i}); } sort(begin(st), end(st)); vector<array<int, 2>> con; for (int i = 1; i < N; ++i) { if (st[i][0] == st[i - 1][0] && st[i][1] - st[i - 1][1] == 2) { con.push_back({st[i][2], st[i - 1][2]}); } } st.clear(); for (int i = 0; i < N; ++i) { st.push_back({y[i], x[i], i}); } sort(begin(st), end(st)); for (int i = 1; i < N; ++i) { if (st[i][0] == st[i - 1][0] && st[i][1] - st[i - 1][1] == 2) { con.push_back({st[i][2], st[i - 1][2]}); } } for (int i = 0; i < (int)con.size(); ++i) { if (con[i][0] > con[i][1]) swap(con[i][0], con[i][1]); } sort(begin(con), end(con)); con.erase(unique(begin(con), end(con)), end(con)); DSU dsu(N); for (auto& [x, y] : con) { dsu.unite(x, y); } if (-dsu.e[dsu.get(0)] != N) return 0; vector<vector<int>> adj(N); for (auto& [i, j] : con) { adj[i].push_back(j); adj[j].push_back(i); } int M = con.size(); set<array<int, 2>> vis_edge, vis_cord; queue<int> q; for (int i = 0; i < N; ++i) { if (adj[i].size() == 3) q.push(i); assert(adj[i].size() <= 3); } vector<int> v, u, a, b; auto ok = [&](int X, int Y, vector<array<int, 2>>& now) -> bool { for (auto [f, g] : now) { if (X == f && g == Y) return false; } return !vis_cord.count({X, Y}); }; auto dfs = [&](auto& dfs, int i, int idx, vector<array<int, 2>>& now) -> bool { // cerr << idx << " -> "; // cerr << adj[i].size() << "\n"; if (idx == adj[i].size()) return true; int j = adj[i][idx]; if (x[i] == x[j]) { int ny = min(y[i], y[j]) + 1; int nx = x[i] + 1; if (ok(nx, ny, now)) { now.push_back({nx, ny}); if (dfs(dfs, i, idx + 1, now)) { // cerr << "Done!\n"; return true; } now.pop_back(); } nx = x[i] - 1; if (ok(nx, ny, now)) { now.push_back({nx, ny}); if (dfs(dfs, i, idx + 1, now)) return true; now.pop_back(); } assert(false); } else { assert(y[i] == y[j]); int nx = min(x[i], x[j]) + 1; int ny = y[i] + 1; if (ok(nx, ny, now)) { now.push_back({nx, ny}); if (dfs(dfs, i, idx + 1, now)) return true; now.pop_back(); } ny = y[i] - 1; if (ok(nx, ny, now)) { now.push_back({nx, ny}); if (dfs(dfs, i, idx + 1, now)) return true; now.pop_back(); } assert(false); } return false; }; while (q.size()) { int i = q.front(); q.pop(); // cerr << i << endl; bool can = true; for (auto& j : adj[i]) { if (vis_edge.count({min(i, j), max(i, j)})) { can = false; } } if (!can) continue; vector<array<int, 2>> now; assert(dfs(dfs, i, 0, now)); // cerr << "Here!\n"; for (int _ = 0; _ < 3; ++_) { int j = adj[i][_]; u.push_back(i); v.push_back(j); a.push_back(now[_][0]); b.push_back(now[_][1]); } for (auto& [X, Y] : now) { vis_cord.insert({X, Y}); } for (auto& j : adj[i]) { vis_edge.insert({min(i, j), max(i, j)}); } } for (int it = 0; it < M; ++it) { int i = con[it][0]; int j = con[it][1]; if (i > j) swap(i, j); if (vis_edge.count({i, j})) continue; v.push_back(i); u.push_back(j); if (x[i] == x[j]) { int ny = min(y[i], y[j]) + 1; b.push_back(ny); int nx = x[i] + 1; if (!vis_cord.count({nx, ny})) { a.push_back(nx); } else { nx = x[i] - 1; assert(!vis_cord.count({nx, ny})); a.push_back(nx); } vis_cord.insert({nx, ny}); } else { int nx = min(x[i], x[j]) + 1; a.push_back(nx); int ny = y[i] + 1; if (!vis_cord.count({nx, ny})) { b.push_back(ny); } else { ny = y[i] - 1; assert(!vis_cord.count({nx, ny})); b.push_back(ny); } vis_cord.insert({nx, ny}); } } build(v, u, a, b); return 1; }
#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...