Submission #1193164

#	Time	Username	Problem	Language	Result	Execution time	Memory
1193164		alexdd	Fountain Parks (IOI21_parks)	C++20	5 / 100	990 ms	77064 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 dx[4] = {-2,+2,0,0};
int dy[4] = {0,0,-2,+2};

map<pair<int,int>,bool> used;

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

    map<pair<int,int>,pair<int,bool>> mp;
    for(int i=0;i<n;i++)
    {
        mp[{x[i],y[i]}] = {i,1};
    }
    DSU dsu;
    dsu.init();
    for(int i=0;i<n;i++)
    {
        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());
    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};
                if(!used[cur])
                    banca = cur;
            }
        }
        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};
                if(!used[cur])
                    banca = cur;
            }
        }
        if(banca.first==-1)
            return 0;
        assert(!used[banca]);
        used[banca] = 1;
        sola[i] = banca.first;
        solb[i] = banca.second;
    }
    build(solu, solv, sola, solb);
    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