Submission #884965

#	Time	Username	Problem	Language	Result	Execution time	Memory
884965		maxFedorchuk	Dango Maker (JOI18_dango_maker)	C++17	33 / 100	205 ms	243004 KiB

dango_maker

#include <bits/stdc++.h>

#pragma GCC target("avx2,sse4,popcnt,bmi")
#pragma GCC optimize("Ofast,unroll-loops")

using namespace std;

const int MX=3020;

int mtr[MX][MX];
char ch[MX][MX];

const int MXK=(MX*MX)/6;
vector < int > mas[2*MXK];
int usea[2*MXK];
int pr[2*MXK];

int timer=0,koma,komb;

bool khuna(int zar)
{
    if(usea[zar])
    {
        return 0;
    }

    usea[zar]=1;

    for(auto u:mas[zar])
    {
        if(pr[u]==0)
        {
            pr[zar]=u;
            pr[u]=zar;
            return 1;
        }
    }

    for(auto u:mas[zar])
    {
        if(khuna(pr[u]))
        {
            pr[zar]=u;
            pr[u]=zar;
            return 1;
        }
    }

    return 0;
}
void kntkhuna()
{
    while(true)
    {
        fill(usea+1,usea+1+timer,0);

        bool p=0;

        for(int i=1;i<=koma;i++)
        {
            if(pr[i]==0)
            {
                if(khuna(i))
                {
                    p=1;
                }
            }
        }

        if(!p)
        {
            return;
        }
    }

    return;
}

void DFS(int zar)
{
    usea[zar]=1;

    if(zar<=koma)
    {
        for(auto u:mas[zar])
        {
            if(pr[u]!=zar && usea[u]==0)
            {
                DFS(u);
            }
        }
    }
    else
    {
        if(usea[pr[zar]]==0)
        {
            DFS(pr[zar]);
        }
    }

    return;
}
int main()
{
    cin.tie(0);
    ios_base::sync_with_stdio(0);

    int n,m;
    cin>>n>>m;

    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            cin>>ch[i][j];
        }
    }

    for(int i=1;i<=n;i++)
    {
        for(int j=1;(j+2)<=m;j++)
        {
            if(ch[i][j]=='R' && ch[i][j+1]=='G' && ch[i][j+2]=='W')
            {
                timer++;
                mtr[i][j]=timer;
            }
        }
    }
    koma=timer;


    for(int i=1;(i+2)<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(ch[i][j]=='R' && ch[i+1][j]=='G' && ch[i+2][j]=='W')
            {
                timer++;

                for(int corx=i;corx<=(i+2);corx++)
                {
                    for(int cory=max(1,j-2);cory<=j;cory++)
                    {
                        if(mtr[corx][cory])
                        {
                            mas[mtr[corx][cory]].push_back(timer);
                            mas[timer].push_back(mtr[corx][cory]);
                        }
                    }
                }
            }
        }
    }
    komb=timer-koma;

    if(timer>=MXK)
    {
        while(true)
        {
            n=0;
        }
        return 0;
    }

    if(koma==0)
    {
        cout<<komb<<"\n";
        return 0;
    }

    if(komb==0)
    {
        cout<<koma<<"\n";
        return 0;
    }

    kntkhuna();
    fill(usea+1,usea+koma+komb+1,0);

    for(int i=1;i<=koma;i++)
    {
        if(pr[i]==0)
        {
            DFS(i);
        }
    }

    int res=0;
    for(int i=1;i<=koma;i++)
    {
        res+=(usea[i]==1);
    }

    for(int i=(koma+1);i<=(koma+komb);i++)
    {
        res+=(usea[i]==0);
    }

    cout<<res<<"\n";
    return 0;
}

• Subtask 1: 13 / 13
• Subtask 2: 20 / 20
• Subtask 3: 0 / 67