제출 #704525

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
704525		KenIsGenius	Dango Maker (JOI18_dango_maker)	C++17	33 / 100	451 ms	262144 KiB

dango_maker

#include <bits/stdc++.h>
#define F first
#define S second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define ll long long
using namespace std;

#ifdef LOCAL
#define WOSAOJI freopen("in.txt", "r", stdin);
#else
#define WOSAOJI ios_base::sync_with_stdio(0), cin.tie(0);
#endif

#define chmax(a, b) (a) = (a) > (b) ? (a) : (b)
#define chmin(a, b) (a) = (a) < (b) ? (a) : (b)

int n, m, cnt;
char c[3005][3005];
int a[3005][3005];
vector<int> adj[5000005];

void add_edge(int a, int b) {
    adj[a].pb(b);
    adj[b].pb(a);
}
bool crow(int i, int j) {
    int ok = 1;
    ok &= (c[i][j - 2] == 'R');
    ok &= (c[i][j - 1] == 'G');
    ok &= (c[i][j    ] == 'W');
    return ok;
}
bool col(int i, int j) {
    int ok = 1;
    ok &= (c[i - 2][j] == 'R');
    ok &= (c[i - 1][j] == 'G');
    ok &= (c[i    ][j] == 'W');
    return ok;
}
int match[5000005];
void dfs(int x, int v) {
    match[x] = v;
    for (int i : adj[x]) {
        if (match[i] == v) {
            dfs(i, v ^ 1);
            return;
        }
    }
}
signed main() {
    WOSAOJI
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> c[i][j];
            if (j >= 3 and crow(i, j)) {
                cnt++;
                a[i][j] = a[i][j - 1] = a[i][j - 2] = cnt;
            }
        }
    }
    for (int i = 3; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (col(i, j)) {
                cnt++;
                if (a[i - 2][j]) ;
                    add_edge(a[i - 2][j], cnt);
                if (a[i - 1][j]) ;
                    add_edge(a[i - 1][j], cnt);
                if (a[i    ][j]) ;
                    add_edge(a[i    ][j], cnt);
            }
        }
    }
    for (int i = 1; i <= cnt; i++) {
        if (!match[i]) dfs(i, 1);
    }
    int ans = 0;
    for (int i = 1; i <= cnt; i++) {
        ans += match[i];
    }
    cout << ans << '\n';
}

컴파일 시 표준 에러 (stderr) 메시지

dango_maker.cpp: In function 'int main()':
dango_maker.cpp:67:17: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   67 |                 if (a[i - 2][j]) ;
      |                 ^~
dango_maker.cpp:68:21: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   68 |                     add_edge(a[i - 2][j], cnt);
      |                     ^~~~~~~~
dango_maker.cpp:69:17: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   69 |                 if (a[i - 1][j]) ;
      |                 ^~
dango_maker.cpp:70:21: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   70 |                     add_edge(a[i - 1][j], cnt);
      |                     ^~~~~~~~
dango_maker.cpp:71:17: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   71 |                 if (a[i    ][j]) ;
      |                 ^~
dango_maker.cpp:72:21: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   72 |                     add_edge(a[i    ][j], cnt);
      |                     ^~~~~~~~

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