Submission #1058752

#	Time	Username	Problem	Language	Result	Execution time	Memory
1058752		LittleOrange	Fountain Parks (IOI21_parks)	C++17	5 / 100	184 ms	56880 KiB

parks

#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) {
    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};
    }
    sort(a.begin(),a.end());
    dsu d(n);
    vector<pair<pos,pos>> cons;
    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;
            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;
        }
    }
    build(ans_u,ans_v,ans_a,ans_b);
    return 1;
}

Compilation message (stderr)

parks.cpp: In function 'int construct_roads(std::vector<int>, std::vector<int>)':
parks.cpp:82:19: 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]
   82 |     if(cons.size()<n-1)return 0;
      |        ~~~~~~~~~~~^~~~

• Subtask 1: 5 / 5
• Subtask 2: 0 / 10
• Subtask 3: 0 / 15
• Subtask 4: 0 / 20
• Subtask 5: 0 / 20
• Subtask 6: 0 / 30