Submission #1242914

#	Time	Username	Problem	Language	Result	Execution time	Memory
1242914		Muhammad_Aneeq	Fountain Parks (IOI21_parks)	C++17	55 / 100	1638 ms	151140 KiB

parks

#include "parks.h"
#include <vector>
#include <map>
#include <algorithm>
#include <set>
#include <iostream>
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<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(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=vector<int>(n-1,-1);
    by=bx;
    map<pair<int,int>,set<int>>cont;
    map<int,set<pair<int,int>>>pos;
    for (auto i:s)
    {
        for (auto j:hor[i])
        {
            cont[{i+1,y[ex[j]]-1}].insert(j);
            cont[{i+1,y[ex[j]]+1}].insert(j);
            pos[j].insert({i+1,y[ex[j]]-1});
            pos[j].insert({i+1,y[ex[j]]+1});
        }   
        for (auto j:ver[i])
        {
            cont[{i-1,y[ex[j]]+1}].insert(j);
            cont[{i+1,y[ex[j]]+1}].insert(j);
            pos[j].insert({i+1,y[ex[j]]+1});
            pos[j].insert({i-1,y[ex[j]]+1});
        }   
    }
    set<pair<int,pair<int,int>>>s1;
    for (auto [i,j]:cont)
        s1.insert({j.size(),i});
    while (s1.size())
    {
        auto z=*begin(s1);
        s1.erase(z);
        if (z.first==0) continue;
        int mn=*rbegin(cont[z.second]);
        for (auto i:cont[z.second])
        {
            if(pos[i].size()<pos[mn].size())
                mn=i;
        }
        bx[mn]=z.second.first,by[mn]=z.second.second;
        for (auto t:cont[z.second])
            pos[t].erase(z.second);
        for (auto i:pos[mn])
        {
            s1.erase({cont[i].size(),i});
            cont[i].erase(mn);
            s1.insert({cont[i].size(),i});
        }
    }
    build(ex,ey,bx,by);
    return 1;
}

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