| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 970322 | mychecksedad | Fountain Parks (IOI21_parks) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "parks.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define all(x) x.begin(), x.end()
#define en cout << '\n';
#define ll long long int
const int N = 3e5+10;
struct Dsu{
vector<int> s, p;
Dsu(int n){
s.resize(n, 1);
p.resize(n);
for(int i = 0; i < n; ++i) p[i] = i;
}
int find(int v){
if(p[v] == v) return v;
return p[v] = find(p[v]);
}
void merge(int a, int b){
a = find(a);
b = find(b);
if(a != b){
if(s[a] > s[b]) swap(a, b);
p[a] = b;
s[b] += s[a];
}
}
};
int construct_roads(std::vector<int> x, std::vector<int> y) {
if (x.size() == 1) {
build({}, {}, {}, {});
return 1;
}
int n = x.size();
vector<int> u, v, a, b;
Dsu d(n);
bool other = 0;
vector<pair<int, int>> L, R, M;
for(int i = 0; i < n; ++i){
if(x[i] == 2) L.pb({y[i], i});
else if(x[i] == 6) R.pb({y[i], i});
else if(x[i] == 4) M.pb({y[i], i});
else{
other = 1;
}
}
if(other){
map<pair<int, int>, int> m;
map<pair<int, int>, bool> used;
for(int i = 0; i < n; ++i) m[{x[i], y[i]}] = i + 1;
array<array<int, 2>, 4> A = {{2, 0}, {0, 2}, {-2, 0}, {0, -2}};
for(int i = 0; i < n; ++i){
for(int j = 0; j < 2; ++j){
int nx = A[j][0] + x[i], ny = A[j][1] + y[i];
int val = m[{nx, ny}];
if(val != 0){
d.merge(val - 1, i);
u.pb(i);
d.pb(val - 1);
int fx = A[j][0] == 0 ? x[i] + 1 : x[i] + A[j][0] / 2;
int fy = A[j][1] == 0 ? y[i] + 1 : y[i] + A[j][1] / 2;
if(used[{fx, fy}]){
if(A[j][0] == 0) fx = x[i] - 1;
else fy = y[i] - 1;
}
a.pb(fx);
b.pb(fy);
used[{fx, fy}] = 1;
}
}
}
}else{
sort(all(L));
sort(all(R));
sort(all(M));
for(int i = 0; i + 1 < L.size(); ++i){
if(L[i].first < L[i + 1].first - 2) continue;
u.pb(L[i].second);
v.pb(L[i + 1].second);
a.pb(1);
b.pb(L[i + 1].first + L[i].first>>1);
d.merge(L[i].second, L[i + 1].second);
}
for(int i = 0; i + 1 < R.size(); ++i){
if(R[i].first < R[i + 1].first - 2) continue;
u.pb(R[i].second);
v.pb(R[i + 1].second);
a.pb(7);
b.pb(R[i + 1].first + R[i].first>>1);
d.merge(R[i].second, R[i + 1].second);
}
for(int i = 0; i + 1 < M.size(); ++i){
if(M[i].first < M[i + 1].first - 2) continue;
u.pb(M[i].second);
v.pb(M[i + 1].second);
a.pb((M[i].first/2)%2 == 0 ? 5 : 3);
b.pb(M[i + 1].first + M[i].first>>1);
d.merge(M[i].second, M[i + 1].second);
}
int p = 0, last = -5;
for(int i = 0; i < M.size(); ++i){
while(p < R.size() && R[p].first < M[i].first) ++p;
if(p < R.size() && R[p].first == M[i].first){
if(last + 2 == M[i].first) continue;
last = M[i].first;
u.pb(R[p].second);
v.pb(M[i].second);
a.pb(5);
b.pb(M[i].first + ((M[i].first/2) % 2 == 0 ? -1 : 1));
d.merge(R[p].second, M[i].second);
}
}
p = 0, last = -5;
for(int i = 0; i < M.size(); ++i){
while(p < L.size() && L[p].first < M[i].first) ++p;
if(p < L.size() && L[p].first == M[i].first){
if(last + 2 == M[i].first) continue;
last = M[i].first;
u.pb(L[p].second);
v.pb(M[i].second);
a.pb(3);
b.pb(M[i].first + ((M[i].first/2) % 2 == 0 ? 1 : -1));
d.merge(L[p].second, M[i].second);
}
}
}
if(d.s[d.find(0)] < n) return 0;
build(u, v, a, b);
return 1;
}