Submission #591902

#	Time	Username	Problem	Language	Result	Execution time	Memory
591902		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;
char pic[3005][3005];
int mk[3005][3005], l[300005], cnt = 1;
pair<int,int> sum[300005];

bool chkrow(int i, int j)
{
    if(j + 2 > m) return false;
    if(pic[i][j] == 'R' && pic[i][j + 1] == 'G' && pic[i][j + 2] == 'W')
        return true;
    return false;
}

bool chkcol(int i, int j)
{
    if(i + 2 > n) return false;
    if(pic[i][j] == 'R' && pic[i + 1][j] == 'G' && pic[i + 2][j] == 'W')
        return true;
    return false;
}

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

void uni(int la, int lb)
{
    if(la == lb) return ;
    sum[lb].f += sum[la].f;
    sum[lb].s += sum[la].s;
    l[la] = lb;
}

int main()
{
    scanf("%d %d",&n,&m);
    for(int i = 0; i < n; i++)
        scanf("%s",pic[i]);
    for(int i = 0; i < n; i++)
        for(int j = 0; j < m; j++)
            if(chkrow(i, j))
            {
                l[cnt] = cnt;
                sum[cnt] = {1, 0};
                mk[i][j] = mk[i][j + 1] = mk[i][j + 2] = cnt;
                cnt++;
            }
    for(int i = 0; i < n; i++)
        for(int j = 0; j < m; j++)
            if(chkcol(i, j))
            {
                l[cnt] = cnt;
                sum[cnt] = {0, 1};
                if(mk[i][j])
                    uni(fi(cnt), fi(mk[i][j]));
                if(mk[i + 1][j])
                    uni(fi(cnt), fi(mk[i + 1][j]));
                if(mk[i + 2][j])
                    uni(fi(cnt), fi(mk[i + 2][j]));
                cnt++;
            }
    int ans = 0;
    for(int i = 1; i < cnt; i++)
    {
        if(fi(i) == i)
            ans += max(sum[i].f, sum[i].s);
    }
    printf("%d\n",ans);
    return 0;
}

Compilation message (stderr)

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

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