Submission #796346

#TimeUsernameProblemLanguageResultExecution timeMemory
796346t6twotwoFountain Parks (IOI21_parks)C++17
30 / 100
106 ms29416 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; int construct_roads(vector<int> X, vector<int> Y) { int N = X.size(); 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; }
#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...