Submission #1193182

#	Time	Username	Problem	Language	Result	Execution time	Memory
1193182		alexdd	Fountain Parks (IOI21_parks)	C++20	70 / 100	506 ms	115444 KiB

parks

#include "parks.h"
#include<bits/stdc++.h>
using namespace std;

int n;
struct DSU
{
    int father[200005],siz[200005];
    void init()
    {
        for(int i=0;i<n;i++)
            father[i]=i, siz[i]=1;
    }
    int get(int x)
    {
        if(father[x]!=x)
            father[x]=get(father[x]);
        return father[x];
    }
    void unite(int x, int y)
    {
        x = get(x);
        y = get(y);
        if(x==y)
            return;
        if(siz[x] < siz[y])
            swap(x,y);
        siz[x] += siz[y];
        father[y] = x;
    }
};

int cate=0;
struct CUPLAJ
{
    vector<int> con[200005];
    int tori[200005],tole[400005];
    void add_edge(int x, int y)
    {
        con[x].push_back(y);
    }
    int visited[200005],pas;
    bool cupleaza(int x)
    {
        if(visited[x]==pas)
            return 0;
        visited[x] = pas;
        for(int adj:con[x])
        {
            if(tole[adj]==-1)
            {
                tori[x] = adj;
                tole[adj] = x;
                return 1;
            }
        }
        for(int adj:con[x])
        {
            if(cupleaza(tole[adj]))
            {
                tori[x] = adj;
                tole[adj] = x;
                return 1;
            }
        }
        return 0;
    }
    bool solve()
    {
        //for(int i=0;i<n;i++) random_shuffle(con[i].begin(),con[i].end());

        for(int i=0;i<n-1;i++)
        {
            tori[i] = -1;
            visited[i] = 0;
        }
        for(int i=0;i<cate;i++)
            tole[i] = -1;

        pas=0;
        while(1)
        {
            pas++;
            bool bl=0;
            for(int i=0;i<n-1;i++)
                if(tori[i]==-1)
                    bl |= cupleaza(i);
            if(!bl)
                break;
        }
        for(int i=0;i<n-1;i++)
            if(tori[i]==-1)
                return 0;
        return 1;
    }
};

int dx[4] = {-2,+2,0,0};
int dy[4] = {0,0,-2,+2};

pair<int,int> inv[400005];

CUPLAJ cuplaj;

vector<int> x,y;

bool cmp_points(int a, int b)
{
    if(x[a] != x[b])
        return x[a] < x[b];
    return y[a] < y[b];
    if((x[a]/2)%2==0)
    {

    }
}

int construct_roads(std::vector<int> copx, std::vector<int> cpy)
{
    x = copx;
    y = cpy;
    n = x.size();
    if (n == 1)
    {
	    build({}, {}, {}, {});
        return 1;
    }
    std::vector<int> solu, solv, sola, solb;

    map<pair<int,int>,pair<int,bool>> mp;
    vector<int> ord;
    for(int i=0;i<n;i++)
    {
        mp[{x[i],y[i]}] = {i,1};
        ord.push_back(i);
    }
    sort(ord.begin(),ord.end(),cmp_points);

    DSU dsu;
    dsu.init();
    for(int i:ord)
    {
        for(int v=0;v<4;v++)
        {
            int newx = x[i]+dx[v], newy = y[i]+dy[v];
            if(mp[{newx,newy}].second)
            {
                int j = mp[{newx,newy}].first;
                if(dsu.get(i) != dsu.get(j))
                {
                    dsu.unite(i,j);
                    solu.push_back(i);
                    solv.push_back(j);
                }
            }
        }
    }
    if(dsu.siz[dsu.get(1)] != n)
        return 0;

    sola.resize(solu.size());
    solb.resize(solu.size());
    map<pair<int,int>,vector<int>> used;
    for(int i=0;i<solu.size();i++)
    {
        int u = solu[i], v = solv[i];
        pair<int,int> banca = {-1,-1};
        if(x[u] == x[v])
        {
            for(int newx:{x[u]-1, x[u]+1})
            {
                pair<int,int> cur = {newx, (y[u]+y[v])/2};
                used[cur].push_back(i);
            }
        }
        else
        {
            assert(y[u] == y[v]);
            for(int newy:{y[u]-1, y[u]+1})
            {
                pair<int,int> cur = {(x[u]+x[v])/2, newy};
                used[cur].push_back(i);
            }
        }
    }
    cate=0;
    for(auto it:used)
    {
        if(!it.second.empty())
        {
            inv[cate] = it.first;
            for(int i:it.second)
                cuplaj.add_edge(i,cate);
            cate++;
        }
    }
    if(!cuplaj.solve())
        return 0;
    for(int i=0;i<solu.size();i++)
    {
        sola[i] = inv[cuplaj.tori[i]].first;
        solb[i] = inv[cuplaj.tori[i]].second;
    }
    build(solu, solv, sola, solb);
    return 1;
}

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