Submission #582138

#	Time	Username	Problem	Language	Result	Execution time	Memory
582138		hibiki	Dango Maker (JOI18_dango_maker)	C++11	13 / 100	1 ms	340 KiB

dango_maker

#include<bits/stdc++.h>
using namespace std;

#define pb push_back
#define f first
#define s second
#define sz(x) (int)x.size()
#define all(x) x.begin(),x.end()

int n,m,cnt = 1;
char wd[3005][3005],l[1000005],r[1000005],c[1000005];
map<pair<int,int>, int> mp;

int fi(int idx)
{
    if(l[idx] == idx) return idx;
    return l[idx] = fi(l[idx]);
}

int main()
{
    scanf("%d %d",&n,&m);
    for(int i = 0; i < n; i++)
    {
        scanf("%s",wd[i]);
        for(int j = 0; j < m - 2; j++)
        {
            if(wd[i][j] == 'R' && wd[i][j + 1] == 'G' && wd[i][j + 2] == 'W')
                mp[{i,j}] = cnt++;
        }
    }
    for(int i = 1; i < cnt; i++)
    {
        l[i] = i;
        r[i] = 1;
    }
    int ans = 0;
    for(int i = 0; i < n - 2; i++)
    {
        for(int j = 0; j < m; j++)
        {
            if(wd[i][j] == 'R' && wd[i + 1][j] == 'G' && wd[i + 2][j] == 'W')
            {
                int curl = -1;
                for(int k = 0; k < 3; k++)
                {
                    int ni = i + k;
                    int nj = j - k;
                    if(nj < 0) break;
                    if(mp[{ni,nj}])
                    {
                        if(curl == -1)
                        {
                            curl = fi(mp[{ni,nj}]);
                            c[curl]++;
                        }
                        else
                        {
                            int ol = fi(mp[{ni,nj}]);
                            r[curl] += r[ol];
                            c[curl] += c[ol];
                            l[ol] = curl;
                        }
                    }
                }
                if(curl == -1)
                    ans++;
            }
        }
    }
    for(int i = 1; i < cnt; i++)
        if(fi(i) == i) ans += max(r[i], c[i]);
    printf("%d\n",ans);
}

Compilation message (stderr)

dango_maker.cpp: In function 'int main()':
dango_maker.cpp:22:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   22 |     scanf("%d %d",&n,&m);
      |     ~~~~~^~~~~~~~~~~~~~~
dango_maker.cpp:25:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |         scanf("%s",wd[i]);
      |         ~~~~~^~~~~~~~~~~~

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