제출 #1242889

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1242889		Muhammad_Aneeq	분수 공원 (IOI21_parks)	C++17	15 / 100	677 ms	65380 KiB

parks

#include "parks.h"
#include <vector>
#include <map>
#include <algorithm>
#include <set>
using namespace std;
int const N=2e5+10;
int par[N]={};
int root(int n)
{
    return (par[n]==n?n:par[n]=root(par[n]));
}
void merge(int u,int v)
{
    u=root(u);
    v=root(v);
    if (u==v) return;
    par[v]=u;
}
int dx[4]={-2,2,0,0},dy[4]={0,0,2,-2};
int construct_roads(vector<int> x, vector<int> y) 
{
    int n=x.size();
    map<pair<int,int>,int>ind;
    map<int,vector<int>>ver;
    map<int,vector<pair<int,int>>>hor;
    for (int i=0;i<n;i++)
    {
        ind[{x[i],y[i]}]=i;
        par[i]=i;
    }
    set<int>s;
    vector<int>ex,ey,bx,by;
    for (int i=0;i<n;i++)
    {
        s.insert(x[i]);
        for (int j=0;j<4;j++)
        {
            int x1=x[i]+dx[j],y1=y[i]+dy[j];
            if (ind.find({x1,y1})!=ind.end())
            {
                int z=ind[{x1,y1}];
                if (root(z)==root(i)) continue;
                merge(i,z);
                ex.push_back(i);
                ey.push_back(z);
                if (x1<x[i])
                    swap(ex.back(),ey.back());
                if (x1==x[i])
                    if (y1<y[i])
                        swap(ex.back(),ey.back());
                if (j<2)
                {
                    hor[min(x[i],x1)].push_back({y[i],ex.size()-1});
                }
                else
                    ver[min(x[i],x1)].push_back(ex.size()-1);
            }
        }
    }
    for (int i=0;i<n;i++)
    {
        if (root(i)!=root(0))
            return 0;
    }
    bx.resize(n-1);
    by.resize(n-1);
    map<pair<int,int>,bool>vis;
    for (auto i:s)
    {
        for (auto j:ver[i])
        {
            if (vis.find({i-1,y[ex[j]]+1})==vis.end())
            {
                vis[{i-1,y[ex[j]]+1}]=1;
                bx[j]=i-1;
                by[j]=y[ex[j]]+1;
            }
            else if (vis.find({i+1,y[ex[j]]+1})==vis.end())
            {
                vis[{i+1,y[ex[j]]+1}]=1;
                bx[j]=i+1;
                by[j]=y[ex[j]]+1;
            }
            else
                return 0;
        }
        sort(rbegin(hor[i]),rend(hor[i]));
        for(auto [k,j]:hor[i])
        {
            if (vis.find({i+1,y[ex[j]]+1})==vis.end())
            {
                vis[{i+1,y[ex[j]]+1}]=1;
                bx[j]=i+1;
                by[j]=y[ex[j]]+1;
            }
            else if (vis.find({i+1,y[ex[j]]-1})==vis.end())
            {
                vis[{i+1,y[ex[j]]-1}]=1;
                bx[j]=i+1;
                by[j]=y[ex[j]]-1;
            }
            else return 0;
        }
    }
    build(ex,ey,bx,by);
    return 1;
}

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