QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#192783#3125. Dango MakerCamillus#0 1ms5884kbC++204.3kb2023-09-30 15:29:512024-07-04 02:13:34

Judging History

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

  • [2024-07-04 02:13:34]
  • 评测
  • 测评结果:0
  • 用时:1ms
  • 内存:5884kb
  • [2023-09-30 15:29:51]
  • 提交

answer

#include "bits/stdc++.h"
#pragma GCC optimize("O3,Ofast")
#pragma GCC target("avx,avx2,fma")
using namespace std;

char t[3000][3000];

int S = 0;
int T = 1;

int cnt_vertexes = 2;

int saved[3000][3000];
int get_input_vertex(int i, int j) {
    if (!saved[i][j]) {
        saved[i][j] = cnt_vertexes++;
        cnt_vertexes++;
    }
    return saved[i][j];
}

int get_output_vertex(int i, int j) {
    if (!saved[i][j]) {
        saved[i][j] = cnt_vertexes++;
        cnt_vertexes++;
    }
    return saved[i][j] + 1;
}

int get_vertex(int i, int j) {
    if (!saved[i][j]) {
        saved[i][j] = cnt_vertexes++;
    }
    return saved[i][j];
}

struct Edge {
    int to = 0;
    short f = 0, c = 0;
    Edge() = default;
    Edge(int to, short c) : to(to), f(0), c(c) {}
};

vector<Edge> edges;
vector<vector<int>> g;
vector<int> p;
vector<int> dist;
int mark[20'000'000];
int cur_mark = 0;

void add_edge(int u, int v, int w) {
    g[u].push_back(edges.size());
    edges.emplace_back(v, w);
    g[v].push_back(edges.size());
    edges.emplace_back(u, 0);
}

bool bfs() {
    cur_mark++;
    int inf = dist[S];
    mark[S] = cur_mark;
    dist[S] = 0;
    deque<int> Q = {S};
    while (!Q.empty()) {
        int u = Q.front();
        Q.pop_front();
        for (int e_i : g[u]) {
            int v = edges[e_i].to;
            short f = edges[e_i].f;
            short c = edges[e_i].c;
            if (mark[v] != cur_mark) {
                dist[v] = INT32_MAX;
                mark[v] = cur_mark;
            }
            if (f < c && dist[v] > dist[u] + 1) {
                dist[v] = dist[u] + 1;
                Q.push_back(v);
            }
        }
    }
    return mark[T] == cur_mark;
}

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

int dinic() {
    int ans = 0;
    while (bfs()) {
        cur_mark++;
        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') {
                get_vertex(i, j);
            }
            if (t[i][j] == 'W') {
                get_vertex(i, j);
            }
            if (t[i][j] == 'G') {
                get_input_vertex(i, j);
                get_output_vertex(i, j);
            }
        }
    }
    g.resize(cnt_vertexes);
    dist.resize(cnt_vertexes);
    p.resize(cnt_vertexes);
    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;
}

详细

Subtask #1:

score: 0
Time Limit Exceeded

Test #1:

score: 13
Accepted
time: 1ms
memory: 5664kb

input:

1 1
G

output:

0

result:

ok single line: '0'

Test #2:

score: 0
Accepted
time: 1ms
memory: 5884kb

input:

1 2
RG

output:

0

result:

ok single line: '0'

Test #3:

score: 0
Accepted
time: 0ms
memory: 5812kb

input:

2 1
W
R

output:

0

result:

ok single line: '0'

Test #4:

score: 0
Accepted
time: 0ms
memory: 5680kb

input:

3 2
WW
RW
WR

output:

0

result:

ok single line: '0'

Test #5:

score: 0
Accepted
time: 1ms
memory: 5656kb

input:

4 4
GRRW
GWWR
WWWW
RGRG

output:

0

result:

ok single line: '0'

Test #6:

score: -13
Time Limit Exceeded

input:

4 4
RGRR
RRRG
GRGW
RGWW

output:


result:


Subtask #2:

score: 0
Skipped

Dependency #1:

0%

Subtask #3:

score: 0
Skipped

Dependency #1:

0%