oj.uz

Submission #357621

# Submission time Handle Problem Language Result Execution time Memory
357621 2021-01-24T09:12:18 Z cute_hater Dango Maker (JOI18_dango_maker) C++17
0 / 100
 169 ms 248556 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], used[N * N], mtr[N * N], mtl[N * N];

bool kun(int v, int c) {
    used[v] = c;
    for (int i = 0; i < 3 && g[i][v] != -1; ++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 < 3 && g[i][v] != -1; ++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] = g[0][i] = g[1][i] = g[2][i] = -1;
        f[i / N][i % N] = usedl[i] = usedr[i] = g[0][i] = g[1][i] = g[2][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) {
                    loop(k, 3)
                        if (g[k][v] == -1) {
                            g[k][v] = (i - 2) * m + (j - 2); break;
                        }
                }
                if (f[i - 1][j + 1] == 1 && f[i + 1][j + 1] == 3) {
                    loop(k, 3)
                        if (g[k][v] == -1) {
                            g[k][v] = (i - 3) * m + (j - 1); break;
                        }
                }
                if (f[i - 2][j + 2] == 1 && f[i - 1][j + 2] == 2) {
                    loop(k, 3)
                        if (g[k][v] == -1) {
                            g[k][v] = (i - 4) * m + j; break;
                        }
                }
            }
        }
    }
    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] = 0;
      |                                                 ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 165 ms 248556 KB Output is correct
2 Correct 163 ms 248556 KB Output is correct
3 Correct 167 ms 248556 KB Output is correct
4 Correct 169 ms 248556 KB Output is correct
5 Correct 163 ms 248556 KB Output is correct
6 Incorrect 165 ms 248556 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 165 ms 248556 KB Output is correct
2 Correct 163 ms 248556 KB Output is correct
3 Correct 167 ms 248556 KB Output is correct
4 Correct 169 ms 248556 KB Output is correct
5 Correct 163 ms 248556 KB Output is correct
6 Incorrect 165 ms 248556 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 165 ms 248556 KB Output is correct
2 Correct 163 ms 248556 KB Output is correct
3 Correct 167 ms 248556 KB Output is correct
4 Correct 169 ms 248556 KB Output is correct
5 Correct 163 ms 248556 KB Output is correct
6 Incorrect 165 ms 248556 KB Output isn't correct
7 Halted 0 ms 0 KB -