Submission #1061745

#TimeUsernameProblemLanguageResultExecution timeMemory
1061745mc061Fountain Parks (IOI21_parks)C++17
25 / 100
3601 ms66464 KiB
#pragma GCC optimize("Ofast") #include <bits/stdc++.h> using namespace std; map<pair<int, int>, int> vid; int di[2] = {2, 0}; int dj[2] = {0, 2}; struct edge { int i1, j1, i2, j2; }; vector<edge> edges; const int N = 2e5+6; struct DSU { int p[N]={}; int sz[N]; DSU() { iota(p, p+N, 0); fill(sz, sz+N, 1); } int get(int a) { return p[a] = (a == p[a] ? a : get(p[a])); } void merge(int a, int b) { int x = get(a), y = get(b); if (x == y) return; if (sz[x] > sz[y]) swap(x, y); p[x] = y; sz[y] += sz[x]; } }; vector<edge> horizontal, vertical; void build(vector<int> u, vector<int> v, vector<int> a, vector<int> b); bool try_build() { // srand(69420); //0 - up(hor) (from road: -1;+1) //1 - down(hor) (from road: +1;+1) //2 - left(ver) (from road: +1;-1) //3 - right(ver)(from road: +1;+1) vector<int> tlx = {-1, 1, 1, 1}; vector<int> tly = {1, 1, -1, 1}; vector<int> dx = {0, 0, 2, 2}; vector<int> dy = {2, 2, 0, 0}; map<pair<int, int>, int> bench_dir; for (const auto& e : horizontal) { bench_dir[{e.i1-1, e.j1+1}] = 0; } auto sieve_down = [&] (int bi, int bj) -> void { bench_dir.erase({bi, bj}); bi += 2; while (bench_dir.count({bi, bj})) { bench_dir[{bi, bj}] = 1; bi += 2; } bench_dir[{bi, bj}] = 1; }; for (const auto& e : vertical) { int wi_left = e.i1+1; int wj_left = e.j1-1; int wi_right = e.i1+1; int wj_right = e.j1+1; if (bench_dir.count({wi_left, wj_left})) { if (!bench_dir.count({wi_right, wj_right})) { bench_dir[{wi_right, wj_right}] = 3; continue; } int prev_dir = bench_dir[{wi_left, wj_left}]; if (prev_dir == 0) { sieve_down(wi_left, wj_left); bench_dir[{wi_left, wj_left}] = 2; continue; } if (prev_dir == 1) { int prev_dir2 = bench_dir[{wi_right, wj_right}]; if (prev_dir2 == 1) { return false; } sieve_down(wi_right, wj_right); bench_dir[{wi_right, wj_right}] = 3; } else if (prev_dir == 3) return false; } else { bench_dir[{wi_left, wj_left}] = 2; } } map<array<int, 4>, pair<int, int>> road_to_bench; for (const auto& [x, y] : bench_dir) { int tx = x.first-tlx[y]; int ty = x.second-tly[y]; int bx = tx+dx[y]; int by = ty+dy[y]; road_to_bench[{tx, ty, bx, by}] = {x.first, x.second}; } vector<int> u, v, a, b; for (const auto& e : horizontal) { u.push_back(vid[{e.i1, e.j1}]); v.push_back(vid[{e.i2, e.j2}]); a.push_back(road_to_bench[{e.i1, e.j1, e.i2, e.j2}].first); b.push_back(road_to_bench[{e.i1, e.j1, e.i2, e.j2}].second); } for (const auto& e : vertical) { u.push_back(vid[{e.i1, e.j1}]); v.push_back(vid[{e.i2, e.j2}]); a.push_back(road_to_bench[{e.i1, e.j1, e.i2, e.j2}].first); b.push_back(road_to_bench[{e.i1, e.j1, e.i2, e.j2}].second); } build(u, v, a, b); return true; } int construct_roads(vector<int> x, vector<int> y) { const int n = x.size(); for (int i = 0; i < n; ++i) { vid[{x[i], y[i]}] = i; } vector<edge> all_vert; vector<edge> all_hor; for (int i = 0; i < n; ++i) { for (int j = 0; j < 2; ++j) { int ni = x[i] + di[j]; int nj = y[i] + dj[j]; auto it = vid.find({ni, nj}); if (it == vid.end()) continue; edges.push_back({x[i], y[i], ni, nj}); bool hor = ni == x[i]; if (!hor) all_vert.push_back({x[i], y[i], ni, nj}); else all_hor.push_back({x[i], y[i], ni, nj}); } } for (int z = 0; z < 30; ++z) { random_shuffle(all_hor.begin(), all_hor.end()); random_shuffle(all_vert.begin(), all_vert.end()); vertical.clear(); horizontal.clear(); DSU d; for (const edge& e : all_vert) { int id1 = vid[{e.i1, e.j1}]; int id2 = vid[{e.i2, e.j2}]; if (d.get(id1) == d.get(id2)) continue; d.merge(id1, id2); vertical.push_back(e); } for (const edge& e : all_hor) { bool hor = e.i1 == e.i2; int id1 = vid[{e.i1, e.j1}]; int id2 = vid[{e.i2, e.j2}]; if (d.get(id1) == d.get(id2)) continue; d.merge(id1, id2); horizontal.push_back(e); } if (d.sz[d.get(0)] != n) return 0; sort(vertical.begin(), vertical.end(), [&](const edge& a, const edge& b) { if (a.i1 != b.i1) return a.i1 < b.i1; return a.j1 < b.j1; }); int j = try_build(); if (j == 1) return true; } return false; }

Compilation message (stderr)

parks.cpp: In function 'int construct_roads(std::vector<int>, std::vector<int>)':
parks.cpp:160:18: warning: unused variable 'hor' [-Wunused-variable]
  160 |             bool hor = e.i1 == e.i2;
      |                  ^~~
#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...