QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#192496#3125. Dango MakerCamillus#13 9ms7996kbC++203.7kb2023-09-30 14:40:592024-07-04 02:49:06

Judging History

你现在查看的是最新测评结果

  • [2024-07-04 02:49:06]
  • 评测
  • 测评结果:13
  • 用时:9ms
  • 内存:7996kb
  • [2023-09-30 14:40:59]
  • 提交

answer

#include "bits/stdc++.h"
using namespace std;

char t[3000][3000];

int S = 0;
int T = 1;
int cnt_vertexes = 2;

map<pair<int, int>, int> saved_input_vertexes;
int get_input_vertex(int i, int j) {
    if (!saved_input_vertexes.contains(make_pair(i, j))) {
        saved_input_vertexes[make_pair(i, j)] = cnt_vertexes++;
    }
    return saved_input_vertexes[make_pair(i, j)];
}

map<pair<int, int>, int> saved_output_vertexes;
int get_output_vertex(int i, int j) {
    if (!saved_output_vertexes.contains(make_pair(i, j))) {
        saved_output_vertexes[make_pair(i, j)] = cnt_vertexes++;
    }
    return saved_output_vertexes[make_pair(i, j)];
}

map<pair<int, int>, int> saved_vertexes;
int get_vertex(int i, int j) {
    if (!saved_vertexes.contains(make_pair(i, j))) {
        saved_vertexes[make_pair(i, j)] = cnt_vertexes++;
    }
    return saved_vertexes[make_pair(i, j)];
}

struct Edge {
    int to, f, c;
};

Edge edges[3'000'000];
int cnt_edges = 0;

vector<int> g[10'000'000];

void add_edge(int u, int v, int w) {
    edges[cnt_edges] = Edge{v, 0, w};
    g[u].push_back(cnt_edges);
    cnt_edges++;
    edges[cnt_edges] = Edge{u, 0, 0};
    g[v].push_back(cnt_edges);
    cnt_edges++;
}

int dist[10'000'000];
int p[10'000'000];

bool bfs() {
    memset(dist, 1, sizeof(int) * cnt_vertexes);
    int inf = dist[S];
    dist[S] = 0;
    deque<int> Q = {S};
    while (!Q.empty()) {
        int u = Q.front();
        Q.pop_front();
        for (int e_i : g[u]) {
            auto& [v, f, c] = edges[e_i];
            if (f < c && dist[v] > dist[u] + 1) {
                dist[v] = dist[u] + 1;
                Q.push_back(v);
            }
        }
    }
    return dist[T] != inf;
}

int dfs(int u, int flow = INT32_MAX) {
    if (u == T) {
        return flow;
    }
    for (; p[u] < g[u].size(); p[u]++) {
        int e_i = g[u][p[u]];
        auto& [v, f, c] = edges[e_i];
        if (f < c && dist[v] == dist[u] + 1) {
            int res = dfs(v, min(flow, c - f));
            if (res) {
                f += res;
                return res;
            }
        }
    }
    return 0;
}

int dinic() {
    int ans = 0;
    while (bfs()) {
        memset(p, 0, sizeof(int) * cnt_vertexes);
        while (int res = dfs(S)) {
            ans += res;
        }
    }
    return ans;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> t[i][j];
        }
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (t[i][j] == 'R') {
                add_edge(S, get_vertex(i, j), 1);
            }
            if (t[i][j] == 'W') {
                add_edge(get_vertex(i, j), T, 1);
            }
            if (t[i][j] == 'G') {
                add_edge(get_input_vertex(i, j), get_output_vertex(i, j), 1);
            }
            if (i + 2 < n && t[i][j] == 'R' && t[i + 1][j] == 'G' && t[i + 2][j] == 'W') {
                add_edge(get_vertex(i, j), get_input_vertex(i + 1, j), 1);
                add_edge(get_output_vertex(i + 1, j), get_vertex(i + 2, j), 1);
            }
            if (j + 2 < m && t[i][j] == 'R' && t[i][j + 1] == 'G' && t[i][j + 2] == 'W') {
                add_edge(get_vertex(i, j), get_input_vertex(i, j + 1), 1);
                add_edge(get_output_vertex(i, j + 1), get_vertex(i, j + 2), 1);
            }
        }
    }

    cout << dinic() << '\n';
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 13
Accepted

Test #1:

score: 13
Accepted
time: 4ms
memory: 7784kb

input:

1 1
G

output:

0

result:

ok single line: '0'

Test #2:

score: 0
Accepted
time: 4ms
memory: 7952kb

input:

1 2
RG

output:

0

result:

ok single line: '0'

Test #3:

score: 0
Accepted
time: 8ms
memory: 7924kb

input:

2 1
W
R

output:

0

result:

ok single line: '0'

Test #4:

score: 0
Accepted
time: 8ms
memory: 7984kb

input:

3 2
WW
RW
WR

output:

0

result:

ok single line: '0'

Test #5:

score: 0
Accepted
time: 8ms
memory: 7948kb

input:

4 4
GRRW
GWWR
WWWW
RGRG

output:

0

result:

ok single line: '0'

Test #6:

score: 0
Accepted
time: 8ms
memory: 7920kb

input:

4 4
RGRR
RRRG
GRGW
RGWW

output:

2

result:

ok single line: '2'

Test #7:

score: 0
Accepted
time: 9ms
memory: 7808kb

input:

4 4
RRGR
GRRG
WRGW
RGWW

output:

3

result:

ok single line: '3'

Test #8:

score: 0
Accepted
time: 8ms
memory: 7588kb

input:

4 4
RGWR
GGGW
WWGW
RWGW

output:

1

result:

ok single line: '1'

Test #9:

score: 0
Accepted
time: 8ms
memory: 7636kb

input:

3 3
RGW
GGG
WGW

output:

1

result:

ok single line: '1'

Test #10:

score: 0
Accepted
time: 8ms
memory: 7588kb

input:

4 1
W
R
G
W

output:

1

result:

ok single line: '1'

Test #11:

score: 0
Accepted
time: 4ms
memory: 7708kb

input:

4 4
RGWR
GWRG
WRGW
RGWR

output:

3

result:

ok single line: '3'

Test #12:

score: 0
Accepted
time: 8ms
memory: 7704kb

input:

4 4
RWWR
GWRG
WGGW
RGWR

output:

3

result:

ok single line: '3'

Test #13:

score: 0
Accepted
time: 8ms
memory: 7636kb

input:

4 4
RGWR
WWRG
WRGW
RWGR

output:

2

result:

ok single line: '2'

Test #14:

score: 0
Accepted
time: 8ms
memory: 7636kb

input:

4 4
RRRR
GGGG
WWWW
RRRR

output:

4

result:

ok single line: '4'

Test #15:

score: 0
Accepted
time: 9ms
memory: 7996kb

input:

4 4
RRRR
GGGR
WWWW
RRRR

output:

3

result:

ok single line: '3'

Test #16:

score: 0
Accepted
time: 8ms
memory: 7776kb

input:

4 4
RRRR
GGGG
WWWW
RWRR

output:

4

result:

ok single line: '4'

Subtask #2:

score: 0
Wrong Answer

Dependency #1:

100%
Accepted

Test #17:

score: 20
Accepted
time: 8ms
memory: 7788kb

input:

5 5
RRGRR
RGRGW
RRWRW
RGWGW
RWWWW

output:

3

result:

ok single line: '3'

Test #18:

score: 0
Accepted
time: 9ms
memory: 7640kb

input:

6 6
RGWRGW
RRRGWR
RRWGWR
WRRRWG
GGGGGW
WWWWWW

output:

7

result:

ok single line: '7'

Test #19:

score: 0
Accepted
time: 9ms
memory: 7944kb

input:

7 10
RRRGRGWRGW
RGGGWRRGWR
RWWWWGRRGG
RGWRWWGGGW
WWRGWRGWGW
RGWWGGRGWW
RRGWWWWWWW

output:

14

result:

ok single line: '14'

Test #20:

score: -20
Wrong Answer
time: 9ms
memory: 7708kb

input:

10 8
RGWRRRGW
RGWGRRGW
WRGWGRGW
RGWWRGWW
GWRRGWWW
WRRGRWRR
GRGWGRGG
WGWWWRWR
RGWRGRGW
RRWRGWWW

output:

15

result:

wrong answer 1st lines differ - expected: '16', found: '15'

Subtask #3:

score: 0
Skipped

Dependency #1:

100%
Accepted

Dependency #2:

0%