| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1058760 | LittleOrange | 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;
using ll = int;
struct dsu{
ll n;
vector<ll> p;
dsu(ll N):n(N),p(N,-1){}
ll g(ll i){
return p[i]<0?i:p[i]=g(p[i]);
}
bool m(ll a, ll b){
a = g(a);
b = g(b);
if(a==b) return false;
if(p[a]>p[b]) swap(a,b);
p[a]+=p[b];
p[b]=a;
return true;
}
};
struct obj{
ll x,y,i;
bool operator<(const obj &o) const{
return x!=o.x?x<o.x:y<o.y;
}
obj operator+(const obj &o) const{
return {x+o.x,y+o.y,i};
}
obj operator-(const obj &o) const{
return {x-o.x,y-o.y,i};
}
bool operator==(const obj &o) const{
return x==o.x&&y==o.y;
}
bool operator!=(const obj &o) const{
return x!=o.x||y!=o.y;
}
obj turn() const{
return {y,-x,i};
}
};
using pos = obj;
ostream& operator<<(ostream& o, const pos &p){
return o << "(" << p.x << "," << p.y << ";" << p.i << ")";
}
pos mid(const pos &a, const pos &b){
return {(a.x+b.x)/2,(a.y+b.y)/2,0};
}
array<pos,2> mids(const pos &a, const pos &b){
pos m = mid(a,b);
array<pos,2> r = {m+(a-m).turn(),m+(b-m).turn()};
//cerr << "mids of " << a << " " << b << " -> " << r[0] << " " << r[1] << "\n";
return r;
}
int construct_roads(std::vector<int> x, std::vector<int> y) {
mt19937_64 mt(random_device{}());
ll n = x.size();
vector<obj> fs = {{0,2,0},{0,-2,0},{2,0,0},{-2,0,0}};
if (x.size() == 1) {
build({}, {}, {}, {});
return 1;
}
vector<ll> ans_u,ans_v,ans_a,ans_b;
vector<obj> a(n);
for(ll i = 0;i<n;i++){
a[i] = {x[i],y[i],i};
}
vector<obj> ord = a;
shuffle(ord.begin(),ord.end());
sort(a.begin(),a.end());
dsu d(n);
vector<pair<pos,pos>> cons;
for(pos u : ord){
for(pos f : fs){
pos v = u+f;
auto it = lower_bound(a.begin(),a.end(),v);
if (it==a.end()||*it!=v) continue;
v = *it;
if(d.m(u.i,v.i)){
cons.push_back({u,v});
}
}
}
if(cons.size()<n-1)return 0;
vector<pos> v;
for(auto [p0,p1] : cons){
for(pos p : mids(p0,p1)) v.push_back(p);
}
sort(v.begin(),v.end());
v.erase(unique(v.begin(),v.end()),v.end());
ll m = v.size();
vector<pair<pos,pos>> ops;
vector<vector<ll>> con(m);
vector<ll> u(n-1,0);
for(auto [p0,p1] : cons){
auto o = mids(p0,p1);
ll i = lower_bound(v.begin(),v.end(),o[0])-v.begin();
ll j = lower_bound(v.begin(),v.end(),o[1])-v.begin();
pair<pos,pos> op = {min(o[0],o[1]),max(o[0],o[1])};
ops.push_back(op);
con[i].push_back(j);
con[j].push_back(i);
}
vector<ll> idl(m);
iota(idl.begin(),idl.end(),0);
sort(idl.begin(),idl.end(),[&](ll i, ll j){return con[i].size()<con[j].size();});
for(ll i : idl){
for(ll j : con[i]){
pair<pos,pos> op = {min(v[i],v[j]),max(v[i],v[j])};
auto it = lower_bound(ops.begin(),ops.end(),op);
if (it==ops.end()) continue;
if (*it!=op) continue;
ll idx = it-ops.begin();
if(u[idx]) continue;
u[idx] = 1;
pos p = v[i];
ans_a.push_back(p.x);
ans_b.push_back(p.y);
auto os = mids(v[i],v[j]);
//cerr << "use " << p << " from " << os[0] << " " << os[1] << "\n";
ll idx1 = (*lower_bound(a.begin(),a.end(),os[0])).i;
ll idx2 = (*lower_bound(a.begin(),a.end(),os[1])).i;
ans_u.push_back(idx1);
ans_v.push_back(idx2);
break;
}
}
if(ans_u.size()<n-1) return 0;
build(ans_u,ans_v,ans_a,ans_b);
return 1;
}