Submission #755304

#	Time	Username	Problem	Language	Result	Execution time	Memory
755304		Rafi22	Fountain Parks (IOI21_parks)	C++17	55 / 100	1400 ms	165404 KiB

parks

#include <bits/stdc++.h>
#include "parks.h"

using namespace std;

#define endl '\n'
#define st first
#define nd second
#define pb push_back
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define ll long long
ll mod=1000000007;
int inf=1000000007;
ll infl=1000000000000000007;

const int N=200007;
map<int,int>id[N];
map<int,int>id1[N];
vector<int>G[3*N];
bool odw[3*N];
int Pair[3*N];

int r[N];

int Find(int v)
{
    if(r[v]==v) return v;
    return r[v]=Find(r[v]);
}
void Union(int u,int v)
{
    r[u]=v;
}

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

void edge(int u,int v)
{
    G[u].pb(v);
    G[v].pb(u);
}

bool match(int v)
{
    if(odw[v]) return 0;
    odw[v]=1;
    for(auto u:G[v])
    {
        if(!Pair[u]&&!odw[u])
        {
            Pair[u]=v;
            Pair[v]=u;
            return 1;
        }
    }
    for(auto u:G[v])
    {
        if(!odw[u]&&match(Pair[u]))
        {
            Pair[u]=v;
            Pair[v]=u;
            return 1;
        }
    }
    return 0;
}
/*
void build(vector<int>u,vector<int>v,vector<int>a,vector<int>b)
{
    for(int i=0;i<sz(u);i++)
    {
        cout<<u[i]<<" "<<v[i]<<" "<<a[i]<<" "<<b[i]<<endl;
    }
}
*/

int construct_roads(vector<int>x,vector<int>y)
{
    int n=sz(x);
    for(int i=0;i<n;i++)
    {
        id[x[i]][y[i]]=i+1;
        r[i+1]=i+1;
    }
    int cnt=0,it=n-1;
    vector<int>U,V,A,B;
    vector<pair<int,int>>Q;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<4;j++)
        {
            int nx=x[i]+dx[j],ny=y[i]+dy[j];
            if(id[nx][ny]>0&&Find(id[nx][ny])!=Find(i+1))
            {
                cnt++;
                U.pb(id[nx][ny]-1);
                V.pb(i);
                Union(Find(id[nx][ny]),Find(i+1));
                int X=min(x[i],x[id[nx][ny]-1]),Y=min(y[i],y[id[nx][ny]-1]);
                if(x[i]==x[id[nx][ny]-1])
                {
                    if(id1[X+1][Y+1]==0)
                    {
                        id1[X+1][Y+1]=++it;
                        Q.pb({X+1,Y+1});
                    }
                    if(id1[X-1][Y+1]==0)
                    {
                        id1[X-1][Y+1]=++it;
                        Q.pb({X-1,Y+1});
                    }
                    edge(id1[X+1][Y+1],cnt);
                    edge(id1[X-1][Y+1],cnt);
                }
                else
                {
                    if(id1[X+1][Y+1]==0)
                    {
                        id1[X+1][Y+1]=++it;
                        Q.pb({X+1,Y+1});
                    }
                    if(id1[X+1][Y-1]==0)
                    {
                        id1[X+1][Y-1]=++it;
                        Q.pb({X+1,Y-1});
                    }
                    edge(id1[X+1][Y+1],cnt);
                    edge(id1[X+1][Y-1],cnt);
                }
            }
        }

    }
    if(cnt!=n-1) return 0;
    while(true)
    {
        memset(odw,0,sizeof odw);
        bool xd=0;
        for(int i=1;i<=it;i++) if(!Pair[i]) xd|=match(i);
        if(!xd) break;
    }
    for(int i=1;i<=n-1;i++)
    {
        A.pb(Q[Pair[i]-n].st);
        B.pb(Q[Pair[i]-n].nd);
        if(Pair[i]==0) return 2137;
    }
    build(U,V,A,B);
    return 1;
}

/*
int main()
{
    construct_roads({2, 2, 4, 4}, {2, 4, 2, 4});
    return 0;
}
*/

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