Submission #331775

#	Time	Username	Problem	Language	Result	Execution time	Memory
331775		daniel920712	Dango Maker (JOI18_dango_maker)	C++14	33 / 100	2091 ms	70888 KiB

dango_maker

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <set>

using namespace std;
char all[3005][3005];
vector < pair < int , int > > tt;
vector < int > temp;
set < pair < int , int > > vis;
set < pair < int , int > > vis2;
map < pair < int , int > , vector < int > > is;
map < pair < int , int > , int > nxt;

int ans=0,a,b;
void F(int x,int y)
{
    if(vis2.find(make_pair(x,y))!=vis2.end()) return ;
    a++;
    vis2.insert(make_pair(x,y));
    tt.push_back(make_pair(x,y));
    for(auto i:is[make_pair(x,y)]) F(1-x,i);
}
bool F2(int x,int y,int fx,int fy,int deg)
{
    if(vis.find(make_pair(x,y))!=vis.end()) return 0;
    vis.insert(make_pair(x,y));
    if(nxt[make_pair(x,y)]==-1&&deg==1)
    {
        nxt[make_pair(x,y)]=fy;
        return 1;
    }
    if(deg==1)
    {
        if(F2(1-x,nxt[make_pair(x,y)],x,y,1-deg))
        {
            nxt[make_pair(x,y)]=fy;
            return 1;
        }
    }
    else
    {
        for(auto i:is[make_pair(x,y)])
        {
            if(F2(1-x,i,x,y,1-deg))
            {
                nxt[make_pair(x,y)]=i;
                return 1;
            }
        }
    }
    return 0;

}
int main()
{
    int N,M,i,j;
    scanf("%d %d",&N,&M);
    for(i=0;i<N;i++) scanf("%s",all[i]);
    for(i=0;i<N;i++) for(j=0;j<M-2;j++) if(all[i][j]=='R'&&all[i][j+1]=='G'&&all[i][j+2]=='W') is[make_pair(0,i*M+j)]=temp;
    for(i=0;i<N-2;i++) for(j=0;j<M;j++) if(all[i][j]=='R'&&all[i+1][j]=='G'&&all[i+2][j]=='W') is[make_pair(1,i*M+j)]=temp;

    for(i=0;i<N;i++)
    {
        for(j=0;j<M;j++)
        {
            if(is.find(make_pair(0,i*M+j))!=is.end()&&is.find(make_pair(1,i*M+j))!=is.end())
            {
                is[make_pair(0,i*M+j)].push_back(i*M+j);
                is[make_pair(1,i*M+j)].push_back(i*M+j);
            }
            if(i>=1&&j+1<M&&is.find(make_pair(0,i*M+j))!=is.end()&&is.find(make_pair(1,(i-1)*M+j+1))!=is.end())
            {
                is[make_pair(0,i*M+j)].push_back((i-1)*M+j+1);
                is[make_pair(1,(i-1)*M+j+1)].push_back(i*M+j);
            }
            if(i>=2&&j+2<M&&is.find(make_pair(0,i*M+j))!=is.end()&&is.find(make_pair(1,(i-2)*M+j+2))!=is.end())
            {
                is[make_pair(0,i*M+j)].push_back((i-2)*M+j+2);
                is[make_pair(1,(i-2)*M+j+2)].push_back(i*M+j);
            }
        }
    }
    for(auto i:is)
    {
        if(vis2.find(i.first)==vis2.end())
        {
            tt.clear();
            a=0;
            F(i.first.first,i.first.second);
            ans+=a;
            for(auto i:tt) nxt[i]=-1;
            for(auto i:tt)
            {
                if(nxt[i]==-1)
                {
                    vis.clear();
                    if(F2(i.first,i.second,-1,-1,0)) ans--;
                }

            }

        }

    }
    printf("%d\n",ans);
    //printf("aa\n");
    return 0;
}

Compilation message (stderr)

dango_maker.cpp: In function 'int main()':
dango_maker.cpp:62:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   62 |     scanf("%d %d",&N,&M);
      |     ~~~~~^~~~~~~~~~~~~~~
dango_maker.cpp:63:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   63 |     for(i=0;i<N;i++) scanf("%s",all[i]);
      |                      ~~~~~^~~~~~~~~~~~~

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