| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1058795 | 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};
}
};
struct pr{
ll i,c;
bool operator<(const pr &o) const{
return c>o.c;
}
};
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;
}
ll t0 = time();
while(time()<t0+3){
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};
}
//shuffle(ord.begin(),ord.end(),mt);
sort(a.begin(),a.end());
dsu d(n);
vector<pair<pos,pos>> cons;
vector<pair<pos,pos>> ord;
for(pos u : a){
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;
ord.push_back({u,v});
}
}
shuffle(ord.begin(),ord.end(),mt);
for(auto [u,v] : ord){
if(d.m(u.i,v.i)){
//cerr << "con " << u << " " << v << "\n";
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])};
//cerr << "ops " << op.first << " " << op.second << "\n";
ops.push_back(op);
con[i].push_back(j);
con[j].push_back(i);
}
sort(ops.begin(),ops.end());
vector<ll> um(m,0);
//shuffle(idl.begin(),idl.end(),mt);
priority_queue<pr> q;
for(ll i = 0;i<m;i++) q.push({i,con[i].size()});
while(!q.empty()){
auto [i,_] = q.top();q.pop();
if (um[i]) continue;
shuffle(con[i].begin(),con[i].end(),mt);
for(ll j : con[i]){
pair<pos,pos> op = {min(v[i],v[j]),max(v[i],v[j])};
//cerr << "test " << op.first << " " << op.second << "\n";
auto it = lower_bound(ops.begin(),ops.end(),op);
if (it==ops.end()) {
//cerr << "error 1\n";
continue;
}
//cerr << "got " << (*it).first << " " << (*it).second << "\n";
if ((*it)!=op) {
//cerr << "error 2\n";
continue;
}
ll idx = it-ops.begin();
//cerr << "idx= " << idx << "\n";
if(u[idx]) {
//cerr << "error 3\n";
continue;
}
u[idx] = 1;
um[i] = 1;
for(ll z = 0;z<con[j].size();z++) if(con[j][z]==i){
con[j].erase(con[j].begin()+z);
break;
}
q.push({j,con[j].size()});
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) continue;
build(ans_u,ans_v,ans_a,ans_b);
return 1;
}
return 0;
}