oj.uz

Submission #42437

# Submission time Handle Problem Language Result Execution time Memory
42437 2018-02-27T07:33:57 Z adlet Dango Maker (JOI18_dango_maker) C++14
0 / 100
 24 ms 24164 KB 
#include <bits/stdc++.h>

using namespace std;

#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast,no-stack-protector")
#pragma GCC target("avx")

#define name "name"
#define file(s) if(fopen(s".in", "r")) freopen(s".in","r",stdin), freopen(s".out","w",stdout);

typedef long long ll;

const int N = 1e6;
const int MN = 3e3 + 5;
const int INF = 1e9;

int n, m, n1, m1, cnt, lim, timer;

int used[MN][MN], was[N], us[N];

char a[MN][MN];

struct edge {
    int v, u, c, f;
};

vector < edge > e;

vector < vector < int > > g(N);

inline void addEdge(int v, int u, int w) {
    cout << v << " " << u << "\n";
    e.push_back({v, u, w, 0});
    g[v].push_back(e.size() - 1);
    e.push_back({u, v, 0, 0});
    g[u].push_back(e.size() - 1);
}

int dfs(int v, int t, int pushed = INF, int p = -1) {
    if (pushed < lim || !pushed)
        return 0;
    if (v == t)
        return pushed;
    us[v] = timer;
    for (int id : g[v]) {
        int to = e[id].u, c = e[id].c, f = e[id].f;
        if (p == to || us[to] == timer || c == f)
            continue;
        int go = dfs(to, t, min(pushed, c - f), v);
        if (go > 0) {
            e[id].f += go;
            e[id ^ 1].f -= go;
            return go;
        }
    }
    return 0;
}

int FordFulkerson(int s, int t) {
    int res = 0;
    lim = 1 << 15;
    while (lim) {
        ++timer;
        int pushed = dfs(s, t);
        if (!pushed) {
            lim >>= 1;
            continue;
        }
        res += pushed;
    }
    return res;
}

int main() {
//    file(name);
    cin >> n >> m;
    n1 = 2;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            cin >> a[i][j];
        }
    }
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j + 2 <= m; ++j) {
            if (a[i][j] == 'R' && a[i][j + 1] == 'G' && a[i][j + 2] == 'W') {
                ++n1;
                used[i][j] = n1;
                used[i][j + 1] = n1;
                used[i][j + 2] = n1;
                addEdge(1, n1, 1);
            }
        }
    }
    for (int j = 1; j <= m; ++j) {
        for (int i = 1; i + 2 <= n; ++i) {
            if (a[i][j] == 'R' && a[i + 1][j] == 'G' && a[i + 2][j] == 'W') {
                if (!used[i][j] && !used[i + 1][j] && !used[i + 2][j]) {
                    ++cnt;
                } else {
                    ++m1;
                    if (used[i][j]) {
                        was[used[i][j]] = 1;
                        addEdge(used[i][j], n1 + m1, 1);
                    }
                    if (used[i + 1][j]) {
                        was[used[i + 1][j]] = 1;
                        addEdge(used[i + 1][j], n1 + m1, 1);
                    }
                    if (used[i + 2][j]) {
                        was[used[i + 2][j]] = 1;
                        addEdge(used[i + 2][j], n1 + m1, 1);
                    }
                    addEdge(m1, 2, 1);
                }
            }
        }
    }
    for (int i = 3; i <= n1; ++i) {
        if (!was[i]) {
            ++cnt;
        }
    }
    cout << FordFulkerson(1, 2) + cnt;
}

Compilation message

dango_maker.cpp:5:0: warning: ignoring #pragma comment  [-Wunknown-pragmas]
 #pragma comment(linker, "/stack:200000000")
 ^

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 23800 KB Output is correct
2 Correct 24 ms 23908 KB Output is correct
3 Correct 21 ms 23908 KB Output is correct
4 Correct 22 ms 24056 KB Output is correct
5 Correct 20 ms 24164 KB Output is correct
6 Incorrect 20 ms 24164 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 23800 KB Output is correct
2 Correct 24 ms 23908 KB Output is correct
3 Correct 21 ms 23908 KB Output is correct
4 Correct 22 ms 24056 KB Output is correct
5 Correct 20 ms 24164 KB Output is correct
6 Incorrect 20 ms 24164 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 23800 KB Output is correct
2 Correct 24 ms 23908 KB Output is correct
3 Correct 21 ms 23908 KB Output is correct
4 Correct 22 ms 24056 KB Output is correct
5 Correct 20 ms 24164 KB Output is correct
6 Incorrect 20 ms 24164 KB Output isn't correct
7 Halted 0 ms 0 KB -