oj.uz

Submission #521883

# Submission time Handle Problem Language Result Execution time Memory
521883 2022-02-03T11:01:14 Z Monarchuwu Dango Maker (JOI18_dango_maker) C++17
13 / 100
 141 ms 212216 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];

int cntX, cntY;
int num[N][N];
vector<int> g[N2];
void init_graph() {
    int cnt(0);
    for (int i = 0; i < m; ++i)
        for (int j = 0; j < n; ++j) if (c[i][j] == 'R') {
            if (j + 2 < n && c[i][j + 1] == 'G' && c[i][j + 2] == 'W')
                num[i][j] = ++cnt;
            else if (i + 2 < m && c[i + 1][j] == 'G' && c[i + 2][j] == 'W')
                num[i][j] = ++cnt;
        }
    cntX = cnt;
    for (int i = 0; i < m; ++i)
        for (int j = 0; j < n; ++j) if (c[i][j] == 'W') {
            if (j >= 2 && c[i][j - 1] == 'G' && c[i][j - 2] == 'R') {
                num[i][j] = ++cnt;
                g[num[i][j - 2]].push_back(cnt);
            }
            else if (i >= 2 && c[i - 1][j] == 'G' && c[i - 2][j] == 'R') {
                num[i][j] = ++cnt;
                g[num[i - 2][j]].push_back(cnt);
            }
        }
    cntY = cnt;
}

int mat[N2];
int dist[N2];
bool bfs() {
    queue<int> q;
    dist[0] = inf;
    for (int i = 1; i <= cntX; ++i)
        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] || 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 = 1; i <= cntX; ++i)
            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 << hopcroft_karp() << '\n';
}
/**  /\_/\
 *  (= ._.)
 *  / >0  \>1
**/

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 117 ms 212040 KB Output is correct
2 Correct 122 ms 211996 KB Output is correct
3 Correct 114 ms 212076 KB Output is correct
4 Correct 116 ms 212216 KB Output is correct
5 Correct 111 ms 211988 KB Output is correct
6 Correct 141 ms 212100 KB Output is correct
7 Correct 120 ms 212068 KB Output is correct
8 Correct 112 ms 212032 KB Output is correct
9 Correct 112 ms 212040 KB Output is correct
10 Correct 112 ms 212088 KB Output is correct
11 Correct 117 ms 212104 KB Output is correct
12 Correct 115 ms 212088 KB Output is correct
13 Correct 122 ms 212008 KB Output is correct
14 Correct 124 ms 212064 KB Output is correct
15 Correct 115 ms 212036 KB Output is correct
16 Correct 112 ms 212016 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 117 ms 212040 KB Output is correct
2 Correct 122 ms 211996 KB Output is correct
3 Correct 114 ms 212076 KB Output is correct
4 Correct 116 ms 212216 KB Output is correct
5 Correct 111 ms 211988 KB Output is correct
6 Correct 141 ms 212100 KB Output is correct
7 Correct 120 ms 212068 KB Output is correct
8 Correct 112 ms 212032 KB Output is correct
9 Correct 112 ms 212040 KB Output is correct
10 Correct 112 ms 212088 KB Output is correct
11 Correct 117 ms 212104 KB Output is correct
12 Correct 115 ms 212088 KB Output is correct
13 Correct 122 ms 212008 KB Output is correct
14 Correct 124 ms 212064 KB Output is correct
15 Correct 115 ms 212036 KB Output is correct
16 Correct 112 ms 212016 KB Output is correct
17 Incorrect 116 ms 212000 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 117 ms 212040 KB Output is correct
2 Correct 122 ms 211996 KB Output is correct
3 Correct 114 ms 212076 KB Output is correct
4 Correct 116 ms 212216 KB Output is correct
5 Correct 111 ms 211988 KB Output is correct
6 Correct 141 ms 212100 KB Output is correct
7 Correct 120 ms 212068 KB Output is correct
8 Correct 112 ms 212032 KB Output is correct
9 Correct 112 ms 212040 KB Output is correct
10 Correct 112 ms 212088 KB Output is correct
11 Correct 117 ms 212104 KB Output is correct
12 Correct 115 ms 212088 KB Output is correct
13 Correct 122 ms 212008 KB Output is correct
14 Correct 124 ms 212064 KB Output is correct
15 Correct 115 ms 212036 KB Output is correct
16 Correct 112 ms 212016 KB Output is correct
17 Incorrect 116 ms 212000 KB Output isn't correct
18 Halted 0 ms 0 KB -