#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;
}
Compilation message
parks.cpp: In function 'int construct_roads(std::vector<int>, std::vector<int>)':
parks.cpp:70:18: error: too few arguments to function 'time_t time(time_t*)'
70 | ll t0 = time();
| ^
In file included from /usr/include/c++/10/ctime:42,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:49,
from parks.cpp:2:
/usr/include/time.h:75:15: note: declared here
75 | extern time_t time (time_t *__timer) __THROW;
| ^~~~
parks.cpp:71:16: error: too few arguments to function 'time_t time(time_t*)'
71 | while(time()<t0+3){
| ^
In file included from /usr/include/c++/10/ctime:42,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:49,
from parks.cpp:2:
/usr/include/time.h:75:15: note: declared here
75 | extern time_t time (time_t *__timer) __THROW;
| ^~~~
parks.cpp:98:23: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<obj, obj> >::size_type' {aka 'long unsigned int'} and 'll' {aka 'int'} [-Wsign-compare]
98 | if(cons.size()<n-1) return 0;
| ~~~~~~~~~~~^~~~
parks.cpp:123:52: warning: narrowing conversion of '(& con.std::vector<std::vector<int> >::operator[](((std::vector<std::vector<int> >::size_type)i)))->std::vector<int>::size()' from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'll' {aka 'int'} [-Wnarrowing]
123 | for(ll i = 0;i<m;i++) q.push({i,con[i].size()});
| ~~~~~~~~~~~^~
parks.cpp:149:31: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
149 | for(ll z = 0;z<con[j].size();z++) if(con[j][z]==i){
| ~^~~~~~~~~~~~~~
parks.cpp:153:38: warning: narrowing conversion of '(& con.std::vector<std::vector<int> >::operator[](((std::vector<std::vector<int> >::size_type)j)))->std::vector<int>::size()' from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'll' {aka 'int'} [-Wnarrowing]
153 | q.push({j,con[j].size()});
| ~~~~~~~~~~~^~
parks.cpp:166:24: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'int'} [-Wsign-compare]
166 | if(ans_u.size()<n-1) continue;
| ~~~~~~~~~~~~^~~~
