Submission #153406

#	Time	Username	Problem	Language	Result	Execution time	Memory
153406		mhy908	Dango Maker (JOI18_dango_maker)	C++14	13 / 100	80 ms	71032 KiB

dango_maker

#include <bits/stdc++.h>
#define F first
#define S second
#define pb push_back
#define llinf 987654321987654321
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
typedef pair<LL, LL> pll;
int n, m, x;
char str[3010][3010];
int col[3010][3010][3], re[3010][3010];
int par[3000010], num[3000010], ans;
int arr[3010][3010];
vector<int> link[3000010];
int findpar(int num)
{
    if(num==par[num])return num;
    return par[num]=findpar(par[num]);
}
void mergepar(int a, int b)
{
    a=findpar(a);
    b=findpar(b);
    par[a]=par[b];
}
int main()
{
    scanf("%d%d", &n, &m);
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            scanf(" %c", &str[i][j]);
        }
    }
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            if(str[i][j]=='R'&&str[i][j+1]=='G'&&str[i][j+2]=='W'){
                arr[i][j]++;
                ++x;
                col[i][j][++re[i][j]]=x;
                col[i][j+1][++re[i][j+1]]=x;
                col[i][j+2][++re[i][j+2]]=x;
            }
            if(str[i][j]=='R'&&str[i+1][j]=='G'&&str[i+2][j]=='W'){
                arr[i][j]+=2;
                ++x;
                col[i][j][++re[i][j]]=x;
                col[i+1][j][++re[i+1][j]]=x;
                col[i+2][j][++re[i+2][j]]=x;
            }
        }
    }
    for(int i=1; i<=n-2; i++){
        for(int j=1; j<=m-2; j++){
            if(arr[i][j+2]==3&&arr[i+1][j+1]==1&&arr[i+2][j]==1)ans++;
            if(arr[i][j+2]==2&&arr[i+1][j+1]==2&&arr[i+2][j]==3)ans++;
        }
    }
    for(int i=1; i<=x; i++)par[i]=i;
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            if(re[i][j]==2){
                mergepar(col[i][j][1], col[i][j][2]);
            }
        }
    }
    for(int i=1; i<=x; i++){
        int temp=findpar(i);
        num[temp]++;
    }
    for(int i=1; i<=x; i++){
        ans+=(num[i]+1)/2;
    }
    printf("%d", ans);
}

Compilation message (stderr)

dango_maker.cpp: In function 'int main()':
dango_maker.cpp:29:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &n, &m);
     ~~~~~^~~~~~~~~~~~~~~~
dango_maker.cpp:32:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf(" %c", &str[i][j]);
             ~~~~~^~~~~~~~~~~~~~~~~~~

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