oj.uz

Submission #357623

# Submission time Handle Problem Language Result Execution time Memory
357623 2021-01-24T09:14:46 Z cute_hater Dango Maker (JOI18_dango_maker) C++17
0 / 100
 49 ms 71424 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;
    if (v < 0 || v >= N * N)
        while (1);
    usedl[v] = 1;
    for (int i = 0; i < sz[v]; ++i) {
        if (sz[v] > 3)
            while (1);
        int u = g[i][v];
        if (u < 0 || u >= N * N)
            while (1);
        if (!usedr[u]) {
            usedr[u] = 1;
            dfs(mtr[u]);
        }
    }
}

void solve() {
    loop(i, N * N)
        mtr[i] = mtl[i] = -1;
    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);
    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)) {
      |                             ~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 71424 KB Output is correct
2 Correct 49 ms 71276 KB Output is correct
3 Correct 45 ms 71316 KB Output is correct
4 Correct 45 ms 71276 KB Output is correct
5 Correct 46 ms 71276 KB Output is correct
6 Correct 45 ms 71276 KB Output is correct
7 Correct 45 ms 71276 KB Output is correct
8 Correct 45 ms 71276 KB Output is correct
9 Correct 46 ms 71276 KB Output is correct
10 Correct 46 ms 71276 KB Output is correct
11 Correct 46 ms 71276 KB Output is correct
12 Correct 49 ms 71276 KB Output is correct
13 Incorrect 44 ms 71276 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 71424 KB Output is correct
2 Correct 49 ms 71276 KB Output is correct
3 Correct 45 ms 71316 KB Output is correct
4 Correct 45 ms 71276 KB Output is correct
5 Correct 46 ms 71276 KB Output is correct
6 Correct 45 ms 71276 KB Output is correct
7 Correct 45 ms 71276 KB Output is correct
8 Correct 45 ms 71276 KB Output is correct
9 Correct 46 ms 71276 KB Output is correct
10 Correct 46 ms 71276 KB Output is correct
11 Correct 46 ms 71276 KB Output is correct
12 Correct 49 ms 71276 KB Output is correct
13 Incorrect 44 ms 71276 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 71424 KB Output is correct
2 Correct 49 ms 71276 KB Output is correct
3 Correct 45 ms 71316 KB Output is correct
4 Correct 45 ms 71276 KB Output is correct
5 Correct 46 ms 71276 KB Output is correct
6 Correct 45 ms 71276 KB Output is correct
7 Correct 45 ms 71276 KB Output is correct
8 Correct 45 ms 71276 KB Output is correct
9 Correct 46 ms 71276 KB Output is correct
10 Correct 46 ms 71276 KB Output is correct
11 Correct 46 ms 71276 KB Output is correct
12 Correct 49 ms 71276 KB Output is correct
13 Incorrect 44 ms 71276 KB Output isn't correct
14 Halted 0 ms 0 KB -