Submission #975579

#	Time	Username	Problem	Language	Result	Execution time	Memory
975579		onlk97	Fountain Parks (IOI21_parks)	C++17	100 / 100	452 ms	55536 KiB

parks

#include "parks.h"
#include <bits/stdc++.h>
using namespace std;
int dsu[200010],L,R;
vector <int> g[200010],match1,match2,dist;
int prt(int n){
    if (dsu[n]==n) return n;
    return dsu[n]=prt(dsu[n]);
}
void unn(int u,int v){
    dsu[prt(u)]=dsu[prt(v)];
}
bool cmp(pair <pair <int,int>,int> u,pair <pair <int,int>,int> v){
    if (u.first.second!=v.first.second) return u.first.second<v.first.second;
    return u.first.first<v.first.first;
}
map <pair <int,int>,int> mp;
int gt(int x,int y){
    if (mp.find({x,y})==mp.end()) return -1;
    return mp[{x,y}];
}
int construct_roads(vector <int> x,vector <int> y){
    int n=x.size();
    pair <pair <int,int>,int> a[n];
    for (int i=0; i<n; i++) a[i]={{x[i],y[i]},i};
    for (int i=0; i<n; i++) mp[{x[i],y[i]}]=i;
    sort(a,a+n);
    for (int i=0; i<n; i++) dsu[i]=i;
    set <pair <int,int> > s;
    for (int i=1; i<n; i++){
        if (a[i-1].first.first==a[i].first.first&&a[i-1].first.second+2==a[i].first.second){
            s.insert({a[i-1].first.first-1,a[i].first.second-1});
            s.insert({a[i-1].first.first+1,a[i].first.second-1});
        }
    }
    sort(a,a+n,cmp);
    for (int i=1; i<n; i++){
        if (a[i-1].first.first+2==a[i].first.first&&a[i-1].first.second==a[i].first.second){
            s.insert({a[i].first.first-1,a[i].first.second-1});
            s.insert({a[i].first.first-1,a[i].first.second+1});
        }
    }
    vector <int> u,v,A,B;
    for (auto i:s){
        if ((i.first+i.second)%4==0){
            int tx=gt(i.first-1,i.second+1),ty=gt(i.first+1,i.second+1);
            if (tx!=-1&&ty!=-1){
                u.push_back(tx); v.push_back(ty); A.push_back(i.first); B.push_back(i.second);
                unn(tx,ty);
            } else {
                tx=gt(i.first-1,i.second-1),ty=gt(i.first+1,i.second-1);
                if (tx!=-1&&ty!=-1){
                    u.push_back(tx); v.push_back(ty); A.push_back(i.first); B.push_back(i.second);
                    unn(tx,ty);
                }
            }
        } else {
            int tx=gt(i.first-1,i.second+1),ty=gt(i.first-1,i.second-1);
            if (tx!=-1&&ty!=-1){
                u.push_back(tx); v.push_back(ty); A.push_back(i.first); B.push_back(i.second);
                unn(tx,ty);
            } else {
                tx=gt(i.first+1,i.second+1),ty=gt(i.first+1,i.second-1);
                if (tx!=-1&&ty!=-1){
                    u.push_back(tx); v.push_back(ty); A.push_back(i.first); B.push_back(i.second);
                    unn(tx,ty);
                }
            }
        }
    }
    for (int i=0; i<n; i++){
        if (prt(i)!=prt(0)) return 0;
    }
    build(u,v,A,B);
    return 1;
}

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