oj.uz

Submission #521955

# Submission time Handle Problem Language Result Execution time Memory
521955 2022-02-03T13:52:41 Z Monarchuwu Dango Maker (JOI18_dango_maker) C++17
13 / 100
 130 ms 212276 KB 
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
typedef long long ll;

const int N = 3000 + 3, N2 = N * N, inf = 1e9 + 7;
int m, n;
char c[N][N];
vector<int> vertexX;

int cnt, num[N][N];
vector<int> g[N2];
void init_graph() {
    for (int i = 0; i < m; ++i)
        for (int j = 0; j < n; ++j) if (c[i][j] == 'G') {
            bool flag11(false), flag12(false), flag21(false), flag22(false);

            // check ngang
            if (j > 0 && j + 1 < n && c[i][j - 1] == 'R' && c[i][j + 1] == 'W') {
                flag11 = true;
                if (i > 1 && c[i - 2][j + 1] == 'R' && c[i - 1][j + 1] == 'G') flag21 = true;
            }

            // check dọc
            if (i > 0 && i + 1 < m && c[i - 1][j] == 'R' && c[i + 1][j] == 'W') {
                flag12 = true;
                if (j + 2 < n && c[i - 1][j + 1] == 'G' && c[i - 1][j + 2] == 'W') flag22 = true;
            }

            if (flag11 || flag12) {
                num[i][j] = ++cnt;
                if (i & 1) vertexX.push_back(num[i][j]);
            }
            bool flag3 = (flag11 && flag22) || (flag12 && flag21);
            if (!flag3 && (flag21 || flag22)) {
                if (i & 1)
                    g[num[i][j]].push_back(num[i - 1][j + 1]);
                else g[num[i - 1][j + 1]].push_back(num[i][j]);
            }
        }
}

int mat[N2];
int dist[N2];
bool bfs() {
    queue<int> q;
    dist[0] = inf;
    for (int i : vertexX)
        if (mat[i]) dist[i] = inf;
        else {
            dist[i] = 0;
            q.push(i);
        }

    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int v : g[u]) {
            if (dist[mat[v]] == inf) {
                dist[mat[v]] = dist[u] + 1;
                q.push(mat[v]);
            }
        }
    }
    return dist[0] != inf;
}

bool dfs(int u) {
    for (int v : g[u]) {
        if (!mat[v] || (dist[mat[v]] == dist[u] + 1 && dfs(mat[v]))) {
            mat[v] = u, mat[u] = v;
            dist[u] = inf;
            return true;
        }
    }
    dist[u] = inf;
    return false;
}

int hopcroft_karp() {
    int ans(0);
    while (bfs()) {
        for (int i : vertexX)
            if (!mat[i] && dfs(i)) ++ans;
    }
    return ans;
}

int main() {
    cin.tie(NULL)->sync_with_stdio(false);
    cin >> m >> n;
    for (int i = 0; i < m; ++i) cin >> c[i];
    init_graph();

    cout << cnt - hopcroft_karp() << '\n';
}
/**  /\_/\
 *  (= ._.)
 *  / >0  \>1
**/

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 212088 KB Output is correct
2 Correct 101 ms 212020 KB Output is correct
3 Correct 115 ms 212276 KB Output is correct
4 Correct 106 ms 211980 KB Output is correct
5 Correct 102 ms 212088 KB Output is correct
6 Correct 104 ms 212040 KB Output is correct
7 Correct 103 ms 212116 KB Output is correct
8 Correct 130 ms 212076 KB Output is correct
9 Correct 105 ms 212052 KB Output is correct
10 Correct 105 ms 212036 KB Output is correct
11 Correct 103 ms 212016 KB Output is correct
12 Correct 103 ms 212016 KB Output is correct
13 Correct 105 ms 212104 KB Output is correct
14 Correct 103 ms 212040 KB Output is correct
15 Correct 128 ms 212100 KB Output is correct
16 Correct 122 ms 212072 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 212088 KB Output is correct
2 Correct 101 ms 212020 KB Output is correct
3 Correct 115 ms 212276 KB Output is correct
4 Correct 106 ms 211980 KB Output is correct
5 Correct 102 ms 212088 KB Output is correct
6 Correct 104 ms 212040 KB Output is correct
7 Correct 103 ms 212116 KB Output is correct
8 Correct 130 ms 212076 KB Output is correct
9 Correct 105 ms 212052 KB Output is correct
10 Correct 105 ms 212036 KB Output is correct
11 Correct 103 ms 212016 KB Output is correct
12 Correct 103 ms 212016 KB Output is correct
13 Correct 105 ms 212104 KB Output is correct
14 Correct 103 ms 212040 KB Output is correct
15 Correct 128 ms 212100 KB Output is correct
16 Correct 122 ms 212072 KB Output is correct
17 Correct 109 ms 212052 KB Output is correct
18 Correct 119 ms 212036 KB Output is correct
19 Correct 111 ms 212132 KB Output is correct
20 Incorrect 101 ms 212084 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 212088 KB Output is correct
2 Correct 101 ms 212020 KB Output is correct
3 Correct 115 ms 212276 KB Output is correct
4 Correct 106 ms 211980 KB Output is correct
5 Correct 102 ms 212088 KB Output is correct
6 Correct 104 ms 212040 KB Output is correct
7 Correct 103 ms 212116 KB Output is correct
8 Correct 130 ms 212076 KB Output is correct
9 Correct 105 ms 212052 KB Output is correct
10 Correct 105 ms 212036 KB Output is correct
11 Correct 103 ms 212016 KB Output is correct
12 Correct 103 ms 212016 KB Output is correct
13 Correct 105 ms 212104 KB Output is correct
14 Correct 103 ms 212040 KB Output is correct
15 Correct 128 ms 212100 KB Output is correct
16 Correct 122 ms 212072 KB Output is correct
17 Correct 109 ms 212052 KB Output is correct
18 Correct 119 ms 212036 KB Output is correct
19 Correct 111 ms 212132 KB Output is correct
20 Incorrect 101 ms 212084 KB Output isn't correct
21 Halted 0 ms 0 KB -