Submission #588151

#TimeUsernameProblemLanguageResultExecution timeMemory
588151Clan328Fountain Parks (IOI21_parks)C++17
30 / 100
214 ms33488 KiB
#include "parks.h" #include <bits/stdc++.h> using namespace std; #define pb push_back struct Coord { int x, y, i; bool operator<(Coord other) const { if (y == other.y) { return x < other.x; } return y < other.y; } }; int n; vector<Coord> coords; std::vector<int> u, v, a, b; vector<int> link; int find(int x) { if (link[x] != x) link[x] = find(link[x]); return link[x]; } void unite(int a, int b) { int x = find(a), y = find(b); link[x] = y; } bool same(int a, int b) { return find(a) == find(b); } void connect(int i, int j) { if (coords[i].x == coords[j].x) { u.pb(coords[i].i); v.pb(coords[j].i); if (coords[i].x == 4) a.pb(coords[i].x+1); else a.pb(coords[i].x-1); b.pb(coords[i].y+1); } else if (coords[i].y == coords[j].y) { u.pb(coords[i].i); v.pb(coords[j].i); a.pb(coords[i].x+1); b.pb(coords[i].y-1); } } int construct_roads(std::vector<int> x, std::vector<int> y) { if (x.size() == 1) { build({}, {}, {}, {}); return 1; } n = x.size(); int maxX = 0; for (int i = 0; i < n; i++) maxX = max(maxX, x[i]); bool res = true; if (maxX <= 4) { coords = vector<Coord>(n); for (int i = 0; i < n; i++) { coords[i] = {x[i], y[i], i}; } sort(coords.begin(), coords.end()); link = vector<int>(n); iota(link.begin(), link.end(), 0); for (int i = 0; i < n-1; i++) { if ((coords[i].y+2 == coords[i+1].y && coords[i].x == coords[i+1].x) || (coords[i].y == coords[i+1].y && abs(coords[i+1].x-coords[i].x) == 2)) { connect(i, i+1); unite(i, i+1); } if (i+2 < n && ((coords[i].y+2 == coords[i+2].y && coords[i].x == coords[i+2].x) || (coords[i].y == coords[i+2].y && abs(coords[i+2].x-coords[i].x) == 2))) { connect(i, i+2); unite(i, i+2); } } for (int i = 0; i < n-1; i++) { res &= find(i) == find(i+1); } } else { int maxY = 0; for (int i = 0; i < n; i++) maxY = max(maxY, y[i]); link = vector<int>(n); iota(link.begin(), link.end(), 0); vector<vector<int>> mat(maxY/2, vector<int>(3)), matIdx(maxY/2, vector<int>(3)); for (int i = 0; i < n; i++) { mat[y[i]/2-1][x[i]/2-1] = 1; matIdx[y[i]/2-1][x[i]/2-1] = i; } map<int, map<int, int>> bench; for (int i = 0; i < maxY/2; i++) { if (mat[i][0] && mat[i][1]) { if (bench[3][2*i+1]) { if (!same(matIdx[i][0], matIdx[i][1])) { if (bench[3][2*i+3]) res = false; u.pb(matIdx[i][0]); v.pb(matIdx[i][1]); a.pb(3); b.pb(2*i+3); unite(matIdx[i][0], matIdx[i][1]); } } else { u.pb(matIdx[i][0]); v.pb(matIdx[i][1]); a.pb(3); b.pb(2*i+1); unite(matIdx[i][0], matIdx[i][1]); } if (a.size()) { bench[a[a.size()-1]][b[b.size()-1]] = true; } } if (mat[i][1] && mat[i][2]) { if (bench[5][2*i+1]) { if (!same(matIdx[i][1], matIdx[i][2])) { if (bench[5][2*i+3]) res = false; u.pb(matIdx[i][1]); v.pb(matIdx[i][2]); a.pb(5); b.pb(2*i+3); unite(matIdx[i][1], matIdx[i][2]); } } else { u.pb(matIdx[i][1]); v.pb(matIdx[i][2]); a.pb(5); b.pb(2*i+1); unite(matIdx[i][1], matIdx[i][2]); } if (a.size()) { bench[a[a.size()-1]][b[b.size()-1]] = true; } } if (i == maxY/2-1) continue; bool isValid = false; if (mat[i][0] && mat[i+1][0]) { u.pb(matIdx[i][0]); v.pb(matIdx[i+1][0]); a.pb(1); b.pb(2*i+3); unite(matIdx[i][0], matIdx[i+1][0]); isValid = true; if (a.size()) { bench[a[a.size()-1]][b[b.size()-1]] = true; } } if (mat[i][2] && mat[i+1][2]) { u.pb(matIdx[i][2]); v.pb(matIdx[i+1][2]); a.pb(7); b.pb(2*i+3); unite(matIdx[i][2], matIdx[i+1][2]); isValid = true; if (a.size()) { bench[a[a.size()-1]][b[b.size()-1]] = true; } } if (!isValid && mat[i][1] && mat[i+1][1]) { u.pb(matIdx[i][1]); v.pb(matIdx[i+1][1]); if (!bench[3][2*i+3]) a.pb(3); else if (!bench[5][2*i+3]) a.pb(5); else res = false; b.pb(2*i+3); unite(matIdx[i][1], matIdx[i+1][1]); if (a.size()) { bench[a[a.size()-1]][b[b.size()-1]] = true; } } } for (int i = 0; i < n-1; i++) { res &= find(i) == find(i+1); } } if (!res) return 0; 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...