| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1049832 | nisanduu | 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;
typedef long long ll;
class Disjoint{
vector<int> parent,sz;
public:
Disjoint(int n){
parent.resize(n+1);
sz.resize(n+1,1);
for(int i=0;i<n+1;i++) parent[i]=i;
}
int findPar(int node){
if(parent[node]==node) return node;
return parent[node] = findPar(parent[node]);
}
void uz(int node1,int node2){
int p1 = findPar(node1);
int p2 = findPar(node2);
if(p1==p2) return;
if(sz[p1]>sz[p2]){
parent[p2]=parent[p1];
sz[p1] += sz[p2];
}else{
parent[p1]=parent[p2];
sz[p2] += sz[p1];
}
}
};
int construct_roads(std::vector<int> x, std::vector<int> y) {
ll n = x.size();
Disjoint ds(n+10);
map<ll,map<ll,ll>> hash1;
map<ll,pair<ll,ll>> hash2;
map<ll,ll> picked;
vector<pair<int,int>> arr(n);
int crInd = 0;
for(int i=0;i<n;i++){
hash1[x[i]][y[i]]=crInd;
hash2[crInd] = {x[i],y[i]};
}
vector<int> u, v, a, b;
for(int i=0;i<n;i++){
int crX = x[i];
int crY = y[i];
if(hash1[crX+2][crY]){
if(ds.findPar(i)!=ds.findPar(hash1[crX+2][crY])){
ds.uz(i,hash1[crX+2][crY]);
u.push_back(i);
v.push_back(hash1[crX+2][crY]);
}
}
if(hash1[crX-2][crY]){
if(ds.findPar(i)!=ds.findPar(hash1[crX-2][crY])){
ds.uz(i,hash1[crX-2][crY]);
u.push_back(i);
v.push_back(hash1[crX-2][crY]);
}
}
if(hash1[crX][crY+2]){
if(ds.findPar(i)!=ds.findPar(hash1[crX][crY+2])){
ds.uz(i,hash1[crX][crY+2]);
u.push_back(i);
v.push_back(hash1[crX][crY+2]);
}
}
if(hash1[crX][crY-2]){
if(ds.findPar(i)!=ds.findPar(hash1[crX][crY-2])){
ds.uz(i,hash1[crX][crY-2]);
u.push_back(i);
v.push_back(hash1[crX][crY-2]);
}
}
}
set<int> p;
for(int i=0;i<n;i++){
p.insert(ds.findPar(i));
}
if(p.size()!=1){
return 0;
}
map<ll,map<ll,ll>> oc;
for(int i=0;i<n-1;i++){
int crX = x[u[i]];
int crY = y[u[i]];
int nxX = x[v[i]];
int nxY = y[v[i]];
if(crX == nxX){
ll bv = (crY + nxY)/2;
if(oc[crX + 1][b]){
a.push_back(crX - 1);
b.push_back(bv);
oc[crX - 1][bv] = 1;
}else{
a.push_back(crX + 1);
b.push_back(bv);
oc[crX + 1][bv] = 1;
}
}else{
ll av = (crX + nxX) / 2;
if(oc[a][crY + 1]){
a.push_back(av);
b.push_back(crY - 1);
oc[av][crY - 1] = 1;
}else{
a.push_back(av);
b.push_back(crY + 1);
oc[av][crY + 1] = 1;
}
}
}
// bool f=1;
// for(ll i=0;i<n-1;i++){
// if((arr[i+1].first - arr[i].first) != 2){
// return 0;
// }
// u.push_back(arr[i+1].second);
// v.push_back(arr[i].second);
// a.push_back(1);
// b.push_back((arr[i+1].first+arr[i].first)/2);
// }
build(u, v, a, b);
return 1;
}