Submission #1230216

#	Time	Username	Problem	Language	Result	Execution time	Memory
1230216		Ludissey	Fountain Parks (IOI21_parks)	C++20	5 / 100	628 ms	49728 KiB

parks

#include "parks.h"
#include <bits/stdc++.h>
 
using namespace std;
 
#define all(a) a.begin(), a.end()
#define sz(a) (int)a.size()

vector<int> sz,parent;

int getParent(int a){
    if(parent[a]==a) return a;
    return parent[a]=getParent(parent[a]);
}

bool same(int a, int b){
    a=getParent(a);
    b=getParent(b);
    return (a==b);
}

void unite(int a, int b){
    a=getParent(a);
    b=getParent(b);
    if(a==b) return;
    if(sz[a]<sz[b]){
        swap(a,b);
    } 
    sz[a]+=sz[b];
    parent[b]=a;
}

int construct_roads(std::vector<int> x, std::vector<int> y) {
    int n=sz(x);
    vector<vector<pair<int,int>>> neigh(n);
    sz.resize(n,1);
    parent.resize(n);
    for (int i = 0; i < n; i++) parent[i]=i;
    vector<pair<pair<int,int>,int>> f(n);
    for (int i = 0; i < n; i++) f[i]={{x[i],y[i]},i};
    map<pair<int,int>, int> mp;
    for (int i = 0; i < n; i++) mp[{x[i],y[i]}]=i;
    vector<int> u, v, a, b;
    vector<pair<int,int>> moves={{-2,0},{0,-2},{0,2},{2,0}};
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < sz(moves); j++)
        {
            pair<int,int> nxt={f[i].first.first+moves[j].first,f[i].first.second+moves[j].second};
            if(mp.find(nxt)!=mp.end()){
                if(!same(f[i].second,mp[nxt])){
                    unite(f[i].second,mp[nxt]);
                    neigh[f[i].second].push_back({sz(u),j});
                    neigh[mp[nxt]].push_back({sz(u),3-j});
                    u.push_back(f[i].second);
                    v.push_back(mp[nxt]);
                    a.push_back(-1);
                    b.push_back(-1);
                }
            }
        }
    }
    set<pair<int,int>> st;
    for (int i = 0; i < n; i++)
    {
        int _x=x[i];
        int _y=y[i];
        if(sz(neigh[i])==4){
            for (auto u : neigh[i])
            {
                if(u.second==0){
                    a[u.first]=_x-1;
                    b[u.first]=_y-1;
                }else if(u.second==1){
                    a[u.first]=_x+1;
                    b[u.first]=_y-1;
                }else if(u.second==2){
                    a[u.first]=_x-1;
                    b[u.first]=_y+1;
                }else{
                    a[u.first]=_x+1;
                    b[u.first]=_y+1;
                }
            }
        }else if(sz(neigh[i])==3){
            set<int> rem;
            rem.insert(0); rem.insert(1); rem.insert(2); rem.insert(3);
            for (auto u : neigh[i]) rem.erase(u.second);
            int indx=*(rem.begin());

            for (auto u : neigh[i])
            {
                if(u.second==0){
                    if(indx==2){
                        a[u.first]=_x-1;
                        b[u.first]=_y-1;
                    }else{
                        a[u.first]=_x-1;
                        b[u.first]=_y+1;
                    }
                }else if(u.second==1){
                    if(indx==3){
                        a[u.first]=_x-1;
                        b[u.first]=_y-1;
                    }else{
                        a[u.first]=_x+1;
                        b[u.first]=_y-1;
                    }
                }else if(u.second==2){
                    if(indx==0){
                        a[u.first]=_x-1;
                        b[u.first]=_y+1;
                    }else{
                        a[u.first]=_x+1;
                        b[u.first]=_y+1;
                    }
                }else{
                    if(indx==1){
                        a[u.first]=_x+1;
                        b[u.first]=_y-1;
                    }else{
                        a[u.first]=_x+1;
                        b[u.first]=_y+1;
                    }
                }
            }
        }
    }

    for (int i = 0; i < sz(a); i++)
    {
        if(a[i]>=0) st.insert({a[i],b[i]});
    }
    for (int i = 0; i < n; i++)
    {
        int _x=x[i];
        int _y=y[i];
        for (auto u : neigh[i])
        {
            if(a[u.first]>=0) continue;

            if(u.second==0){
                if(st.find({_x-1,_y-1})==st.end()&&st.find({_x-1,_y+1})==st.end()) continue;
                if(st.find({_x-1,_y-1})==st.end()){
                    st.insert({_x-1,_y-1});
                    a[u.first]=_x-1;
                    b[u.first]=_y-1;
                }else{
                    st.insert({_x-1,_y+1});
                    a[u.first]=_x-1;
                    b[u.first]=_y+1;
                }
            }else if(u.second==1){
                if(st.find({_x-1,_y-1})==st.end()&&st.find({_x+1,_y-1})==st.end()) continue;

                if(st.find({_x-1,_y-1})==st.end()){
                    st.insert({_x-1,_y-1});
                    a[u.first]=_x-1;
                    b[u.first]=_y-1;
                }else{
                    st.insert({_x+1,_y-1});
                    a[u.first]=_x+1;
                    b[u.first]=_y-1;
                }
            }else if(u.second==2){
                if(st.find({_x-1,_y+1})==st.end()&&st.find({_x+1,_y+1})==st.end()) continue;


                if(st.find({_x-1,_y+1})==st.end()){
                    st.insert({_x-1,_y+1});
                    a[u.first]=_x-1;
                    b[u.first]=_y+1;
                }else{
                    st.insert({_x+1,_y+1});
                    a[u.first]=_x+1;
                    b[u.first]=_y+1;
                }
            }else{
                if(st.find({_x-1,_y-1})==st.end()&&st.find({_x+1,_y+1})==st.end()) continue;


                if(st.find({_x+1,_y-1})==st.end()){
                    st.insert({_x+1,_y-1});
                    a[u.first]=_x+1;
                    b[u.first]=_y-1;
                }else{
                    st.insert({_x+1,_y+1});
                    a[u.first]=_x+1;
                    b[u.first]=_y+1;
                }
            }
        }
    } 
    for (int i = 0; i < n; i++)
    {
        int _x=x[i];
        int _y=y[i];
        for (auto u : neigh[i])
        {
            if(a[u.first]>=0) continue;

            if(u.second==0){
                if(st.find({_x-1,_y-1})==st.end()){
                    st.insert({_x-1,_y-1});
                    a[u.first]=_x-1;
                    b[u.first]=_y-1;
                }else{
                    st.insert({_x-1,_y+1});
                    a[u.first]=_x-1;
                    b[u.first]=_y+1;
                }
            }else if(u.second==1){
                if(st.find({_x-1,_y-1})==st.end()){
                    st.insert({_x-1,_y-1});
                    a[u.first]=_x-1;
                    b[u.first]=_y-1;
                }else{
                    st.insert({_x+1,_y-1});
                    a[u.first]=_x+1;
                    b[u.first]=_y-1;
                }
            }else if(u.second==2){
                if(st.find({_x-1,_y+1})==st.end()){
                    st.insert({_x-1,_y+1});
                    a[u.first]=_x-1;
                    b[u.first]=_y+1;
                }else{
                    st.insert({_x+1,_y+1});
                    a[u.first]=_x+1;
                    b[u.first]=_y+1;
                }
            }else{
                if(st.find({_x+1,_y-1})==st.end()){
                    st.insert({_x+1,_y-1});
                    a[u.first]=_x+1;
                    b[u.first]=_y-1;
                }else{
                    st.insert({_x+1,_y+1});
                    a[u.first]=_x+1;
                    b[u.first]=_y+1;
                }
            }
        }
    } 
    if (sz[getParent(0)] != n) {
        return 0;
    }
    build(u, v, a, b);
    return 1;
}

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