Submission #465882

#TimeUsernameProblemLanguageResultExecution timeMemory
465882alexxela12345Fountain Parks (IOI21_parks)C++17
100 / 100
1632 ms68636 KiB
#include "parks.h" #include <bits/stdc++.h> using namespace std; vector<vector<int>> g; vector<int> used; void dfs(int v) { used[v] = 1; for (int u : g[v]) { if (!used[u]) { dfs(u); } } } int construct_roads(std::vector<int> x, std::vector<int> y) { if (x.size() == 1) { build({}, {}, {}, {}); return 1; } map<pair<int, int>, int> byc; int n = x.size(); for (int i = 0; i < n; i++) { byc[{x[i], y[i]}] = i; } g.clear(); g.resize(n); map<pair<int, int>, int> cnt; auto add = [&](int i, int j) { if (i < j) { g[i].push_back(j); g[j].push_back(i); if (x[i] == x[j]) { cnt[{x[i] + 1, (y[i] + y[j]) / 2}] += 1; cnt[{x[i] - 1, (y[i] + y[j]) / 2}] += 1; } else { cnt[{(x[i] + x[j]) / 2, y[i] + 1}] += 1; cnt[{(x[i] + x[j]) / 2, y[i] - 1}] += 1; } } }; for (int i = 0; i < n; i++) { pair<int, int> pp; pp = {x[i] + 2, y[i]}; if (byc.count(pp)) { add(i, byc[pp]); } pp = {x[i], y[i] + 2}; if (byc.count(pp)) { add(i, byc[pp]); } pp = {x[i] - 2, y[i]}; if (byc.count(pp)) { add(i, byc[pp]); } pp = {x[i], y[i] - 2}; if (byc.count(pp)) { add(i, byc[pp]); } } used.assign(n, 0); dfs(0); if (*min_element(used.begin(), used.end()) == 0) { return 0; } vector<int> u, v, a, b; for (auto [xy, _] : cnt) { pair<int, int> RU, RD, LD, LU; RU = RD = LD = LU = xy; RU.first++, RU.second++; RD.first++, RD.second--; LU.first--, LU.second++; LD.first--, LD.second--; if ((xy.first + xy.second) % 4) { // left right if (byc.count(RU) && byc.count(RD)) { u.push_back(byc[RU]); v.push_back(byc[RD]); a.push_back(xy.first); b.push_back(xy.second); } else if (byc.count(LU) && byc.count(LD)) { u.push_back(byc[LU]); v.push_back(byc[LD]); a.push_back(xy.first); b.push_back(xy.second); } } else { if (byc.count(RU) && byc.count(LU)) { u.push_back(byc[RU]); v.push_back(byc[LU]); a.push_back(xy.first); b.push_back(xy.second); } else if (byc.count(RD) && byc.count(LD)) { u.push_back(byc[RD]); v.push_back(byc[LD]); a.push_back(xy.first); b.push_back(xy.second); } } } build(u, v, 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...