Submission #443432

#TimeUsernameProblemLanguageResultExecution timeMemory
443432mjhmjh1104Fountain Parks (IOI21_parks)C++17
5 / 100
758 ms42828 KiB
#include "parks.h" #include <map> #include <set> #include <vector> #include <utility> #include <algorithm> using namespace std; int uf[200006]; int _find(int x) { if (uf[x] == -1) return x; return uf[x] = _find(uf[x]); } void _merge(int x, int y) { x = _find(x), y = _find(y); if (x != y) uf[x] = y; } map<pair<int, int>, int> m; set<pair<int, int>> s; int construct_roads(vector<int> x, vector<int> y) { if ((int)x.size() == 1) return build({}, {}, {}, {}), 1; int n = (int)x.size(); for (int i = 0; i < n; i++) uf[i] = -1; vector<int> u, v, a, b; vector<pair<int, int>> edges, n_edges; vector<int> points; for (int i = 0; i < n; i++) m[{ x[i], y[i] }] = i; for (int i = 0; i < n; i++) if (m.count({ x[i], y[i] - 2 })) { edges.push_back({ m[{ x[i], y[i] - 2 }], i }); _merge(edges.back().first, edges.back().second); } for (int i = 0; i < n; i++) points.push_back(i); sort(points.begin(), points.end(), [&](const int &a, const int &b) { return y[a] < y[b]; }); for (int t = 0; t < n; t++) { int i = points[t]; if (m.count({ x[i] - 2, y[i] })) { int t = m[{ x[i] - 2, y[i] }]; if (_find(t) != _find(i)) { edges.push_back({ t, i }); _merge(t, i); } } if (m.count({ x[i] + 2, y[i] })) { int t = m[{ x[i] + 2, y[i] }]; if (_find(t) != _find(i)) { edges.push_back({ t, i }); _merge(t, i); } } } for (int i = 1; i < n; i++) if (_find(0) != _find(i)) return 0; for (auto &i: edges) if (x[i.first] == 2 && x[i.first] == 2) { u.push_back(i.first); v.push_back(i.second); a.push_back(1); b.push_back((y[i.first] + y[i.second]) / 2); s.insert({ a.back(), b.back() }); } else if (x[i.first] == 6 && x[i.second] == 6) { u.push_back(i.first); v.push_back(i.second); a.push_back(7); b.push_back((y[i.first] + y[i.second]) / 2); s.insert({ a.back(), b.back() }); } else n_edges.push_back(i); sort(n_edges.begin(), n_edges.end(), [&](const pair<int, int> &a, const pair<int, int> &b) { return min(y[a.first], y[a.second]) < min(y[b.first], y[b.second]); }); for (auto &i: n_edges) { if (x[i.first] == x[i.second]) { if (!s.count({ x[i.first] - 1, (y[i.first] + y[i.second]) / 2 })) { s.insert({ x[i.first] - 1, (y[i.first] + y[i.second]) / 2 }); u.push_back(i.first); v.push_back(i.second); a.push_back(x[i.first] - 1); b.push_back((y[i.first] + y[i.second]) / 2); } else { s.insert({ x[i.first] + 1, (y[i.first] + y[i.second]) / 2 }); u.push_back(i.first); v.push_back(i.second); a.push_back(x[i.first] + 1); b.push_back((y[i.first] + y[i.second]) / 2); } } else { if (!s.count({ (x[i.first] + x[i.second]) / 2, y[i.first] - 1 })) { s.insert({ (x[i.first] + x[i.second]) / 2, y[i.first] - 1 }); u.push_back(i.first); v.push_back(i.second); a.push_back((x[i.first] + x[i.second]) / 2); b.push_back(y[i.first] - 1); } else { s.insert({ (x[i.first] + x[i.second]) / 2, y[i.first] + 1 }); u.push_back(i.first); v.push_back(i.second); a.push_back((x[i.first] + x[i.second]) / 2); b.push_back(y[i.first] + 1); } } } 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...