Submission #582711

#	Time	Username	Problem	Language	Result	Execution time	Memory
582711		hibiki	Dango Maker (JOI18_dango_maker)	C++11	13 / 100	1 ms	352 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];
int l[100005],r[100005],c[100005];
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 = n - 3; i >= 0; 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}]);
                            if(ol != curl)
                            {
                                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:23:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |     scanf("%d %d",&n,&m);
      |     ~~~~~^~~~~~~~~~~~~~~
dango_maker.cpp:26:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   26 |         scanf("%s",wd[i]);
      |         ~~~~~^~~~~~~~~~~~

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