Submission #797135

#TimeUsernameProblemLanguageResultExecution timeMemory
797135t6twotwoFountain Parks (IOI21_parks)C++17
70 / 100
675 ms94136 KiB
#include "parks.h" #include <bits/stdc++.h> using namespace std; using ll = long long; struct dsu { int n; vector<int> p, s; dsu(int n) : n(n), p(n), s(n, 1) { iota(p.begin(), p.end(), 0); } int find(int x) { return x == p[x] ? x : p[x] = find(p[x]); } int size(int x) { return s[find(x)]; } bool same(int x, int y) { return find(x) == find(y); } bool unite(int x, int y) { x = find(x); y = find(y); if (x == y) { return 0; } if (s[x] > s[y]) { swap(x, y); } p[x] = y; s[y] += s[x]; return 1; } }; constexpr int A = 200000; struct road { int a, b, c; pair<int, int> t[2]; road() { } road(int A, int B, int C, pair<int, int> U, pair<int, int> V) { a = A, b = B, c = C, t[0] = U, t[1] = V; } }; int construct_roads(vector<int> X, vector<int> Y) { int N = X.size(); if (*max_element(X.begin(), X.end()) <= 6) { vector f(7, vector(A + 3, -1)); for (int i = 0; i < N; i++) { f[X[i]][Y[i]] = i; } dsu uf(N); vector<int> u, v, a, b, m(A + 1, -1), l(A + 1, -1), r(A + 1, -1); for (int y = 2; y <= A; y += 2) { for (int x = 2; x <= 6; x += 2) { if (f[x][y] != -1 && f[x][y + 2] != -1) { if (x == 4) { m[y + 1] = u.size(); } u.push_back(f[x][y]); v.push_back(f[x][y + 2]); a.push_back(x == 2 ? 1 : 7); b.push_back(y + 1); uf.unite(f[x][y], f[x][y + 2]); } if (x != 6 && f[x][y] != -1 && f[x + 2][y] != -1) { if (x == 2 && l[y - 2] == -1) { l[y] = u.size(); u.push_back(f[x][y]); v.push_back(f[x + 2][y]); a.push_back(3); b.push_back(-1); uf.unite(f[x][y], f[x + 2][y]); } if (x == 4 && r[y - 2] == -1) { r[y] = u.size(); u.push_back(f[x][y]); v.push_back(f[x + 2][y]); a.push_back(5); b.push_back(-1); uf.unite(f[x][y], f[x + 2][y]); } } } } if (uf.size(0) != N) { return 0; } vector<int> q(A, -1), s(A, -1), t(A, -1); for (int i = 1; i <= A; i++) { if (i % 2 == 1 && m[i] != -1) { if (s[i - 1] != 1) { a[m[i]] = 3; q[i] = 0; } else { assert(t[i - 1] != 1); a[m[i]] = 5; q[i] = 1; } } if (i % 2 == 0) { if (l[i] != -1) { if (q[i - 1] == 0) { b[l[i]] = i + 1; s[i] = 1; } else { b[l[i]] = i - 1; s[i] = 0; } } if (r[i] != -1) { if (q[i - 1] == 1) { b[r[i]] = i + 1; t[i] = 1; } else { b[r[i]] = i - 1; t[i] = 0; } } } } build(u, v, a, b); return 1; } map<int, int> mp[A + 1]; for (int i = 0; i < N; i++) { mp[X[i]][Y[i]] = i; } dsu uf(N); vector<road> roads; for (int i = 0; i < N; i++) { for (int dx = -2; dx <= 2; dx += 4) { if (X[i] + dx < 0 || X[i] + dx > A) { continue; } if (mp[X[i] + dx].count(Y[i])) { int j = mp[X[i] + dx][Y[i]]; if (!uf.same(i, j)) { uf.unite(i, j); roads.push_back(road(i, j, -1, pair{X[i] + dx / 2, Y[i] + 1}, pair{X[i] + dx / 2, Y[i] - 1})); } } } for (int dy = -2; dy <= 2; dy += 4) { if (Y[i] + dy < 0 || Y[i] + dy > A) { continue; } if (mp[X[i]].count(Y[i] + dy)) { int j = mp[X[i]][Y[i] + dy]; if (!uf.same(i, j)) { uf.unite(i, j); roads.push_back(road(i, j, -1, pair{X[i] - 1, Y[i] + dy / 2}, pair{X[i] + 1, Y[i] + dy / 2})); } } } } if (uf.size(0) != N) { return 0; } map<int, vector<pair<int, int>>> f[A + 3]; for (int z = 0; z < roads.size(); z++) { auto r = roads[z]; for (int i = 0; i < 2; i++) { auto [x, y] = r.t[i]; f[x][y].emplace_back(z, i); } } for (int z = 0; z < roads.size(); z++) { if (roads[z].c != -1) { continue; } for (int d = 0; d < 2; d++) { bool ok = 1; vector<int> q; roads[z].c = d; q.push_back(z); for (int i = 0; ok && i < q.size(); i++) { int u = q[i]; int color = roads[u].c; auto [x, y] = roads[u].t[color]; for (auto [v, w] : f[x][y]) { if (roads[v].c == -1) { roads[v].c = 1 - w; q.push_back(v); } if (v != u && roads[v].c == w) { ok = 0; break; } } } if (ok) { break; } if (!ok) { if (d == 1) { return 0; } for (int x : q) { roads[x].c = -1; } } } } vector<int> u, v, a, b; for (auto r : roads) { u.push_back(r.a); v.push_back(r.b); auto [x, y] = r.t[r.c]; a.push_back(x); b.push_back(y); } build(u, v, a, b); return 1; }

Compilation message (stderr)

parks.cpp: In function 'int construct_roads(std::vector<int>, std::vector<int>)':
parks.cpp:160:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<road>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  160 |     for (int z = 0; z < roads.size(); z++) {
      |                     ~~^~~~~~~~~~~~~~
parks.cpp:167:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<road>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  167 |     for (int z = 0; z < roads.size(); z++) {
      |                     ~~^~~~~~~~~~~~~~
parks.cpp:176:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  176 |             for (int i = 0; ok && i < q.size(); i++) {
      |                                   ~~^~~~~~~~~~
#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...