Submission #157584

#	Time	Username	Problem	Language	Result	Execution time	Memory
157584		vex	Dango Maker (JOI18_dango_maker)	C++14	13 / 100	382 ms	212684 KiB

dango_maker

#include<bits/stdc++.h>
#define maxn 3005
#define pb push_back
using namespace std;

int n,m;
string s[maxn];

int br[maxn][maxn][2];
vector<int>adj[maxn*maxn];

bool bio[maxn*maxn];

int t=0;
void dfs(int v)
{
    t++;

    for(auto x:adj[v])
    {
        if(!bio[x])
        {
            bio[x]=true;
            dfs(x);
        }
    }
}

bool in_x(int x)
{
    return x>=0 && x<n;
}

bool in_y(int y)
{
    return y>=0 && y<m;
}

bool moze(int x,int y,int type)
{
    if(type==0)
    {
        if(!in_x(x))return false;
        if(!in_y(y))return false;
        if(!in_y(y+1))return false;
        if(!in_y(y+2))return false;

        if(s[x][y]!='R')return false;
        if(s[x][y+1]!='G')return false;
        if(s[x][y+2]!='W')return false;

        return true;
    }

    if(type==1)
    {
        if(!in_y(y))return false;
        if(!in_x(x))return false;
        if(!in_x(x+1))return false;
        if(!in_x(x+2))return false;

        if(s[x][y]!='R')return false;
        if(s[x+1][y]!='G')return false;
        if(s[x+2][y]!='W')return false;

        return true;
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    cin>>n>>m;
    for(int i=0;i<n;i++)
    {
        cin>>s[i];
    }


    int uk=0;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            if(moze(i,j,0))
            {
                uk++;
                br[i][j][0]=uk;
            }

            if(moze(i,j,1))
            {
                uk++;
                br[i][j][1]=uk;
            }
        }
    }

    /*for(int i=0;i<n;i++)
    {
    	for(int j=0;j<m;j++)
    	{
    		cout<<br[i][j][0]<<","<<br[i][j][1]<<" ";
    	}
    	cout<<endl;
    }*/


    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            if(moze(i,j,0))
            {
                int tre=br[i][j][0];

                if(moze(i,j,1))
                {
                    int curr=br[i][j][1];
                    adj[tre].pb(curr);
                    adj[curr].pb(tre);
                }

                if(moze(i-1,j+1,1))
                {
                    int curr=br[i-1][j+1][1];
                    adj[tre].pb(curr);
                    adj[curr].pb(tre);
                }

                if(moze(i-2,j+2,1))
                {
                    int curr=br[i-2][j+2][1];
                    adj[tre].pb(curr);
                    adj[curr].pb(tre);
                }
            }
        }
    }


    for(int i=1;i<=uk;i++)bio[i]=false;

    int sol=0;
    for(int i=1;i<=uk;i++)
    {
        if(!bio[i])
        {
            t=0;
            bio[i]=true;
            dfs(i);
            sol+=(t+1)/2;
        }
    }

    cout<<sol<<endl;
    return 0;
}

Compilation message (stderr)

dango_maker.cpp: In function 'bool moze(int, int, int)':
dango_maker.cpp:68:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

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