Submission #1193167

#	Time	Username	Problem	Language	Result	Execution time	Memory
1193167		alexdd	Fountain Parks (IOI21_parks)	C++20	0 / 100	8 ms	12868 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;
    }
};

struct BIPARTIT
{
    vector<int> con[400005];
    int parte[400005];
    void add_edge(int x, int y)
    {
        con[x].push_back(y);
        con[y].push_back(x);
    }
    void dfs(int nod)
    {
        for(int adj:con[nod])
        {
            if(parte[adj]==0)
            {
                parte[adj] = 3 - parte[nod];
                dfs(adj);
            }
        }
    }
    bool solve()
    {
        for(int i=0;i<2*n;i++)
            parte[i]=0;
        for(int i=0;i<2*n;i++)
            if(parte[i]==0)
                dfs(i);
        for(int i=0;i<2*n;i++)
            for(int adj:con[i])
                if(parte[i]==parte[adj])
                    return 0;
        return 1;
    }
};

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


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());
    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])
        {
            int pas=0;
            for(int newx:{x[u]-1, x[u]+1})
            {
                pair<int,int> cur = {newx, (y[u]+y[v])/2};
                used[cur].push_back(2*i + pas);
                pas++;
            }
        }
        else
        {
            assert(y[u] == y[v]);
            int pas=0;
            for(int newy:{y[u]-1, y[u]+1})
            {
                pair<int,int> cur = {(x[u]+x[v])/2, newy};
                used[cur].push_back(2*i + pas);
                pas++;
            }
        }
    }
    BIPARTIT bipartit;
    for(auto it:used)
    {
        if(it.second.size() >= 2)
        {
            for(int i=0;i<it.second.size();i++)
                for(int j=i+1;j,it.second.size();j++)
                    bipartit.add_edge(it.second[i], it.second[j]);
        }
    }
    if(!bipartit.solve())
        return 0;
    for(int i=0;i<solu.size();i++)
    {
        int u = solu[i], v = solv[i];
        pair<int,int> banca = {-1,-1};
        sola[i] = solb[i] = -1;
        if(x[u] == x[v])
        {
            int pas=0;
            for(int newx:{x[u]-1, x[u]+1})
            {
                pair<int,int> cur = {newx, (y[u]+y[v])/2};
                if(bipartit.parte[2*i+pas] == 1)
                {
                    sola[i] = cur.first;
                    solb[i] = cur.second;
                }
                pas++;
            }
        }
        else
        {
            assert(y[u] == y[v]);
            int pas=0;
            for(int newy:{y[u]-1, y[u]+1})
            {
                pair<int,int> cur = {(x[u]+x[v])/2, newy};
                if(bipartit.parte[2*i+pas] == 1)
                {
                    sola[i] = cur.first;
                    solb[i] = cur.second;
                }
                pas++;
            }
        }
        if(sola[i]==-1)
            return 0;
        assert(sola[i]!=-1);
    }
    build(solu, solv, sola, solb);
    return 1;
}

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