Submission #467469

#	Time	Username	Problem	Language	Result	Execution time	Memory
467469		JvThunder	Fountain Parks (IOI21_parks)	C++17	100 / 100	576 ms	43600 KiB

parks

#include "parks.h"
#include <bits/stdc++.h>
#define fir first
#define sec second
#define pb push_back
typedef long long ll;
using namespace std;

map<pair<int,int>,int> c;
set<pair<int,int>> taken;
vector<pair<int,int>> coor;

//DSU
int par[200005] = {0};
int find(int x)
{
    if(par[x]==x) return x;
    return par[x] = find(par[x]);
}
void join(int a,int b)
{
    if(find(a)==find(b)) assert(false);
    par[find(a)] = par[find(b)];
}

int cnt = 0;
vector<int> u,v,a,b;
void addline(int ax,int ay,int bx,int by,int inda,int indb)
{
    if(find(c[{ax,ay}])==find(c[{bx,by}])) return;

    pair<int,int> bench = {-1,-1};
    if(ax==bx)
    {
        pair<int,int> tmp = {ax-1,(ay+by)/2};
        if(taken.find(tmp)==taken.end() && (tmp.fir-tmp.sec)%4==0) bench = tmp;
        tmp = {ax+1,(ay+by)/2};
        if(taken.find(tmp)==taken.end() && (tmp.fir-tmp.sec)%4==0) bench = tmp;
    }
    if(ay==by)
    {
        pair<int,int> tmp = {(ax+bx)/2,ay-1};
        if(taken.find(tmp)==taken.end() && (tmp.fir-tmp.sec)%4!=0) bench = tmp;
        tmp = {(ax+bx)/2,ay+1};
        if(taken.find(tmp)==taken.end() && (tmp.fir-tmp.sec)%4!=0) bench = tmp;
    }

    if(bench != make_pair(-1,-1))
    {
        join(inda,indb);
        taken.insert(bench);
        u.pb(inda);
        v.pb(indb);
        a.pb(bench.fir);
        b.pb(bench.sec);
        cnt++;
    }
}

int construct_roads(vector<int> x, vector<int> y) 
{
    int n = x.size();
    for(int i=0;i<n;i++) par[i] = i;
    for(int i=0;i<n;i++) c[{x[i],y[i]}] = i;
    for(int i=0;i<n;i++) coor.pb({x[i],y[i]});
    sort(coor.begin(),coor.end());
    

    vector<pair< pair<int,int>,pair<int,int> >> ret;
    for(int i=0;i<n;i++)
    {
        int tx = coor[i].fir;
        int ty = coor[i].sec;
        if(c.count({tx,ty-2})) addline(tx,ty-2,tx,ty,c[{tx,ty}],c[{tx,ty-2}]);
        if(c.count({tx-2,ty})) addline(tx-2,ty,tx,ty,c[{tx,ty}],c[{tx-2,ty}]);
    }

    if(cnt==n-1) 
    {
        build(u,v,a,b); 
        return 1;
    }
    else return 0;
}

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