oj.uz

답안 #357614

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
357614 2021-01-24T09:04:06 Z cute_hater Dango Maker (JOI18_dango_maker) C++17
0 / 100
 181 ms 248684 KB 
#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstdio>
#include <iomanip>
#include <fstream>
#include <cassert>
#include <cstring>
#include <numeric>
#include <ctime>
#include <complex>
#include <bitset>
#include <random>
#include <climits>
#include <stack>


/*#pragma GCC optimize("Ofast")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,sse4.1,sse4.2,popcnt,abm,mmx,avx,avx2,tune=native")*/

using namespace std;

typedef long long ll;
typedef long double ld;

//#define int ll
#define double ld
#define loop(i, n) for(int i = 0; i < (int)n; ++i)
#define loop1(i, n) for(int i = 1; i <= (int)n; ++i)
#define F first
#define S second
#define pb push_back
#define pi pair <int, int>
#define all(x) begin(x), end(x)
#define ti tuple <int, int, int>
#define Point Vect
#define no {cout << -1; return;}
#define yes {cout << "Yes"; return;}
#define mkp make_pair
#define mkt make_tuple
#define cerr if(0) cerr

const int N = 3010;

short f[N][N];
bool usedl[N * N], usedr[N * N];
int g[3][N * N], sz[N * N], used[N * N], mtr[N * N], mtl[N * N];

bool kun(int v, int c) {
    used[v] = c;
    for (int i = 0; i < sz[v]; ++i) {
        int u = g[i][v];
        if (mtr[u] == -1 || used[mtr[u]] != c && kun(mtr[u], c)) {
            mtr[u] = v;
            mtl[v] = u;
            return true;
        }
    }
    return false;
}

void dfs(int v) {
    if (v == -1 || usedl[v])
        return;
    usedl[v] = 1;
    for (int i = 0; i < sz[v]; ++i) {
        int u = g[i][v];
        if (!usedr[u]) {
            usedr[u] = 1;
            dfs(mtr[u]);
        }
    }
}

void solve() {
    loop(i, N * N) {
        mtr[i] = mtl[i] = -1;
        f[i / N][i % N] = usedl[i] = usedr[i] = g[0][i] = g[1][i] = g[2][i] = used[i] = mtr[i] = mtl[i] = used[i] = 0;
    }
    int n, m;
    cin >> n >> m;
    for (int i = 2; i <= n + 1; ++i) {
        for (int j = 2; j <= m + 1; ++j) {
            char c; cin >> c;
            f[i][j] = (c == 'R' ? 1 : (c == 'G' ? 2 : 3));
        }
    }
    for (int i = 2; i <= n + 1; ++i) {
        for (int j = 2; j <= m + 1; ++j) {
            if (f[i][j] == 1 && f[i][j + 1] == 2 && f[i][j + 2] == 3) {
                int v = (i - 2) * m + (j - 2);
                if (f[i + 1][j] == 2 && f[i + 2][j] == 3)
                    g[sz[v]++][v] = (i - 2) * m + (j - 2);
                if (f[i - 1][j + 1] == 1 && f[i + 1][j + 1] == 3)
                    g[sz[v]++][v] = (i - 3) * m + (j - 1);
                if (f[i - 2][j + 2] == 1 && f[i - 1][j + 2] == 2)
                    g[sz[v]++][v] = (i - 4) * m + j;
            }
        }
    }
    int cnt = 0;
    for (int i = 2; i <= n + 1; ++i)
        for (int j = 2; j <= m + 1; ++j)
            kun((i - 2) * m + (j - 2), ++cnt);
    for (int i = 2; i <= n + 1; ++i)
        for (int j = 2; j <= m + 1; ++j)
            if (mtl[(i - 2) * m + (j - 2)] == -1)
                dfs((i - 2) * m + (j - 2));
    int ans = 0;
    for (int i = 2; i <= n + 1; ++i)
        for (int j = 2; j <= m + 1; ++j)
            ans += (f[i][j] == 1 && f[i][j + 1] == 2 && f[i][j + 2] == 3 && usedl[(i - 2) * m + (j - 2)]) + (f[i][j] == 1 && f[i + 1][j] == 2 && f[i + 2][j] == 3 && !usedr[(i - 2) * m + (j - 2)]);
    cout << ans;
}

signed main() {
    //freopen("b2.txt", "r", stdin);
    //freopen("ans9.txt", "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    //int t; cin >> t; loop(i, t)
    solve();
    return 0;
}

Compilation message

dango_maker.cpp: In function 'bool kun(int, int)':
dango_maker.cpp:62:47: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   62 |         if (mtr[u] == -1 || used[mtr[u]] != c && kun(mtr[u], c)) {
      |                             ~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~
dango_maker.cpp: In function 'void solve()':
dango_maker.cpp:87:57: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   87 |         f[i / N][i % N] = usedl[i] = usedr[i] = g[0][i] = g[1][i] = g[2][i] = used[i] = mtr[i] = mtl[i] = used[i] = 0;
      |                                                 ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
dango_maker.cpp:87:87: warning: operation on 'used[i]' may be undefined [-Wsequence-point]
   87 |         f[i / N][i % N] = usedl[i] = usedr[i] = g[0][i] = g[1][i] = g[2][i] = used[i] = mtr[i] = mtl[i] = used[i] = 0;
      |                                                                               ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 181 ms 248556 KB Output is correct
2 Correct 171 ms 248684 KB Output is correct
3 Correct 167 ms 248556 KB Output is correct
4 Correct 179 ms 248556 KB Output is correct
5 Correct 167 ms 248556 KB Output is correct
6 Correct 166 ms 248556 KB Output is correct
7 Correct 177 ms 248556 KB Output is correct
8 Correct 167 ms 248556 KB Output is correct
9 Correct 163 ms 248556 KB Output is correct
10 Correct 170 ms 248684 KB Output is correct
11 Correct 166 ms 248556 KB Output is correct
12 Correct 164 ms 248684 KB Output is correct
13 Incorrect 166 ms 248556 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 181 ms 248556 KB Output is correct
2 Correct 171 ms 248684 KB Output is correct
3 Correct 167 ms 248556 KB Output is correct
4 Correct 179 ms 248556 KB Output is correct
5 Correct 167 ms 248556 KB Output is correct
6 Correct 166 ms 248556 KB Output is correct
7 Correct 177 ms 248556 KB Output is correct
8 Correct 167 ms 248556 KB Output is correct
9 Correct 163 ms 248556 KB Output is correct
10 Correct 170 ms 248684 KB Output is correct
11 Correct 166 ms 248556 KB Output is correct
12 Correct 164 ms 248684 KB Output is correct
13 Incorrect 166 ms 248556 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# 결과 실행 시간 메모리 Grader output
1 Correct 181 ms 248556 KB Output is correct
2 Correct 171 ms 248684 KB Output is correct
3 Correct 167 ms 248556 KB Output is correct
4 Correct 179 ms 248556 KB Output is correct
5 Correct 167 ms 248556 KB Output is correct
6 Correct 166 ms 248556 KB Output is correct
7 Correct 177 ms 248556 KB Output is correct
8 Correct 167 ms 248556 KB Output is correct
9 Correct 163 ms 248556 KB Output is correct
10 Correct 170 ms 248684 KB Output is correct
11 Correct 166 ms 248556 KB Output is correct
12 Correct 164 ms 248684 KB Output is correct
13 Incorrect 166 ms 248556 KB Output isn't correct
14 Halted 0 ms 0 KB -