Submission #755314

#	Time	Username	Problem	Language	Result	Execution time	Memory
755314		Rafi22	Fountain Parks (IOI21_parks)	C++17	70 / 100	2052 ms	123740 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]);
}

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;
}

vector<int>x,y,U,V,A,B;
vector<pair<int,int>>Q;


int cnt,it;

void Union(int u,int v)
{
    r[Find(u)]=Find(v);
    cnt++;
    U.pb(u-1);
    V.pb(v-1);
    int X=min(x[u-1],x[v-1]),Y=min(y[u-1],y[v-1]);
    if(x[u-1]==x[v-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);
    }

}

/*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>xx,vector<int>yy)
{
    x=xx;
    y=yy;
    int n=sz(x);
    for(int i=0;i<n;i++)
    {
        id[x[i]][y[i]]=i+1;
        r[i+1]=i+1;
    }
    it=n-1;
    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))
            {
                int u=id[nx][ny],v=i+1,c=0;
                int X=min(x[u-1],x[v-1]),Y=min(y[u-1],y[v-1]);
                if(x[u-1]==x[v-1])
                {
                    if(id[X-2][Y]>0&&id[X-2][Y+2]>0) c++;
                    if(id[X+2][Y]>0&&id[X+2][Y+2]>0) c++;
                }
                else
                {
                    if(id[X][Y-2]>0&&id[X+2][Y-2]>0) c++;
                    if(id[X][Y+2]>0&&id[X+2][Y+2]>0) c++;
                }
                if(c==1) Union(u,v);
            }
        }
    }
    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))
            {
                Union(id[nx][ny],i+1);
            }
        }
    }
    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++)
    {
        if(Pair[i]==0) return 0;
        A.pb(Q[Pair[i]-n].st);
        B.pb(Q[Pair[i]-n].nd);
    }
    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: 15 / 15
• Subtask 4: 20 / 20
• Subtask 5: 20 / 20
• Subtask 6: 0 / 30