Submission #796297

#TimeUsernameProblemLanguageResultExecution timeMemory
796297t6twotwoFountain Parks (IOI21_parks)C++17
5 / 100
44 ms15916 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; } }; int construct_roads(vector<int> X, vector<int> Y) { int N = X.size(); vector f(5, vector(200003, -1)); for (int i = 0; i < N; i++) { f[X[i]][Y[i]] = i; } dsu uf(N); vector<int> u, v, a, b; for (int y = 2; y <= 200000; y++) { for (int x = 2; x <= 4; x++) { if (f[x][y] != -1 && f[x][y + 2] != -1) { u.push_back(f[x][y]); v.push_back(f[x][y + 2]); a.push_back(2 * x - 3); b.push_back(y + 1); uf.unite(f[x][y], f[x][y + 2]); } } if (f[2][y] != -1 && f[4][y] != -1) { u.push_back(f[2][y]); v.push_back(f[4][y]); a.push_back(3); b.push_back(y - 1); } } if (uf.size(0) != N) { 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...