oj.uz

Submission #391540

# Submission time Handle Problem Language Result Execution time Memory
391540 2021-04-19T09:26:49 Z phathnv Skandi (COCI20_skandi) C++11
110 / 110
 3513 ms 31268 KB 
#include <bits/stdc++.h>

#define mp make_pair
#define X first
#define Y second
#define taskname "SKANDI"

using namespace std;

typedef long long ll;
typedef pair <int, int> ii;

struct _network{
    static const int N = 600010;
    int h[N], vst[N], Time;
    vector <int> adj[N];
    int nE, neg[N], nxt[N], f[N], c[N];

    int cnt = 0;

    void addEdge(int u, int v, int cap){
        adj[u].push_back(++nE);
        c[nE] = cap;
        nxt[nE] = v;

        adj[v].push_back(++nE);
        c[nE] = 0;
        nxt[nE] = u;
        neg[nE] = nE - 1;
        neg[nE - 1] = nE;
    }
    bool bfs(int s, int t){
        Time++;
        queue <int> qu;
        h[s] = 0;
        vst[s] = Time;
        qu.push(s);
        while (!qu.empty()){
            int u = qu.front();
            qu.pop();
            if (u == t)
                return 1;
            for(int e : adj[u]){
                int v = nxt[e];
                if (vst[v] != Time && f[e] < c[e]){
                    vst[v] = Time;
                    h[v] = h[u] + 1;
                    qu.push(v);
                }
            }
        }
        return 0;
    }
    bool enlarge(int u, int t){
        if (u == t)
            return 1;

        vst[u] = Time;

        for(int e : adj[u]){
            int v = nxt[e];
            if (vst[v] != Time && f[e] < c[e] && h[u] + 1 == h[v])
                if (enlarge(v, t)){
                    f[e]++;
                    f[neg[e]]--;
                    return 1;
                }
        }
        return 0;
    }
    int maxFlow(int s, int t){
        int res = 0;
        while (bfs(s, t)){
            Time++;
            while (enlarge(s, t))
                res++;
        }
        return res;
    }
    vector <ii> minCut(int n, int s, int t){
        vector <ii> res;
        assert(!bfs(s, t));
        for(int u = 0; u <= n; u++)
            if (vst[u] == Time)
                for(int e : adj[u]){
                    int v = nxt[e];
                    if (vst[v] != Time && c[e] > 0)
                        res.push_back(mp(u, v));
                }
        return res;
    }
} network;

const int N = 510;
const int INF = 1e9;

int m, n;
char a[N][N];

void readInput(){
    scanf("%d %d", &m, &n);
    for(int i = 1; i <= m; i++)
        scanf("%s", a[i] + 1);
}

int s, t, preCol[N], curId, x[N * N], y[N * N];
void solve(){
    s = 0;
    t = 1;
    curId = 1;

    for(int i = 1; i <= m; i++){
        int preRow = -1;
        for(int j = 1; j <= n; j++){
            if (a[i][j] == '0'){
                network.addEdge(preRow, preCol[j], INF);
            } else {
                if (j < n && a[i][j + 1] == '0'){
                    preRow = ++curId;
                    x[curId] = i;
                    y[curId] = j;
                    network.addEdge(s, curId, 1);
                }

                if (i < m && a[i + 1][j] == '0'){
                    preCol[j] = ++curId;
                    x[curId] = i;
                    y[curId] = j;
                    network.addEdge(curId, t, 1);
                }
            }
        }
    }

    cerr << curId << endl;

    int cnt = 0;
    for(int i = 2; i <= m; i++)
        for(int j = 2; j <= n; j++)
            cnt += a[i][j] - '0';

    printf("%d\n", network.maxFlow(s, t));
    vector <ii> tmp = network.minCut(curId, s, t);
    for(ii p : tmp){
        assert(p.X == 0 || p.Y == 1);
        if (p.X == 0)
            printf("%d %d DESNO\n", x[p.Y], y[p.Y]);
        else
            printf("%d %d DOLJE\n", x[p.X], y[p.X]);
    }
}

int main(){
    readInput();
    solve();
    return 0;
}

Compilation message

skandi.cpp: In function 'void readInput()':
skandi.cpp:101:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  101 |     scanf("%d %d", &m, &n);
      |     ~~~~~^~~~~~~~~~~~~~~~~
skandi.cpp:103:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  103 |         scanf("%s", a[i] + 1);
      |         ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14408 KB Correct.
2 Correct 9 ms 14408 KB Correct.
3 Correct 9 ms 14420 KB Correct.
4 Correct 10 ms 14412 KB Correct.
5 Correct 9 ms 14424 KB Correct.
6 Correct 9 ms 14408 KB Correct.
7 Correct 9 ms 14364 KB Correct.
8 Correct 9 ms 14412 KB Correct.
9 Correct 10 ms 14448 KB Correct.
10 Correct 10 ms 14412 KB Correct.
11 Correct 9 ms 14424 KB Correct.
12 Correct 9 ms 14384 KB Correct.
13 Correct 9 ms 14456 KB Correct.
14 Correct 9 ms 14412 KB Correct.
15 Correct 10 ms 14476 KB Correct.
16 Correct 10 ms 14412 KB Correct.
17 Correct 10 ms 14412 KB Correct.
18 Correct 9 ms 14412 KB Correct.
19 Correct 9 ms 14412 KB Correct.
20 Correct 9 ms 14412 KB Correct.
21 Correct 9 ms 14404 KB Correct.
22 Correct 9 ms 14412 KB Correct.
23 Correct 10 ms 14412 KB Correct.

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14668 KB Correct.
2 Correct 9 ms 14536 KB Correct.
3 Correct 9 ms 14672 KB Correct.
4 Correct 9 ms 14540 KB Correct.
5 Correct 9 ms 14540 KB Correct.
6 Correct 10 ms 14540 KB Correct.
7 Correct 10 ms 14540 KB Correct.
8 Correct 9 ms 14660 KB Correct.
9 Correct 10 ms 14924 KB Correct.
10 Correct 11 ms 14924 KB Correct.
11 Correct 11 ms 14928 KB Correct.
12 Correct 11 ms 15056 KB Correct.
13 Correct 11 ms 14924 KB Correct.
14 Correct 11 ms 14928 KB Correct.
15 Correct 12 ms 15008 KB Correct.
16 Correct 13 ms 14928 KB Correct.
17 Correct 13 ms 15052 KB Correct.
18 Correct 12 ms 15056 KB Correct.
19 Correct 13 ms 14928 KB Correct.
20 Correct 11 ms 14924 KB Correct.
21 Correct 11 ms 15024 KB Correct.
22 Correct 11 ms 14928 KB Correct.
23 Correct 11 ms 14924 KB Correct.
24 Correct 10 ms 14924 KB Correct.
25 Correct 13 ms 15056 KB Correct.
26 Correct 11 ms 14924 KB Correct.

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14408 KB Correct.
2 Correct 9 ms 14408 KB Correct.
3 Correct 9 ms 14420 KB Correct.
4 Correct 10 ms 14412 KB Correct.
5 Correct 9 ms 14424 KB Correct.
6 Correct 9 ms 14408 KB Correct.
7 Correct 9 ms 14364 KB Correct.
8 Correct 9 ms 14412 KB Correct.
9 Correct 10 ms 14448 KB Correct.
10 Correct 10 ms 14412 KB Correct.
11 Correct 9 ms 14424 KB Correct.
12 Correct 9 ms 14384 KB Correct.
13 Correct 9 ms 14456 KB Correct.
14 Correct 9 ms 14412 KB Correct.
15 Correct 10 ms 14476 KB Correct.
16 Correct 10 ms 14412 KB Correct.
17 Correct 10 ms 14412 KB Correct.
18 Correct 9 ms 14412 KB Correct.
19 Correct 9 ms 14412 KB Correct.
20 Correct 9 ms 14412 KB Correct.
21 Correct 9 ms 14404 KB Correct.
22 Correct 9 ms 14412 KB Correct.
23 Correct 10 ms 14412 KB Correct.
24 Correct 9 ms 14668 KB Correct.
25 Correct 9 ms 14536 KB Correct.
26 Correct 9 ms 14672 KB Correct.
27 Correct 9 ms 14540 KB Correct.
28 Correct 9 ms 14540 KB Correct.
29 Correct 10 ms 14540 KB Correct.
30 Correct 10 ms 14540 KB Correct.
31 Correct 9 ms 14660 KB Correct.
32 Correct 10 ms 14924 KB Correct.
33 Correct 11 ms 14924 KB Correct.
34 Correct 11 ms 14928 KB Correct.
35 Correct 11 ms 15056 KB Correct.
36 Correct 11 ms 14924 KB Correct.
37 Correct 11 ms 14928 KB Correct.
38 Correct 12 ms 15008 KB Correct.
39 Correct 13 ms 14928 KB Correct.
40 Correct 13 ms 15052 KB Correct.
41 Correct 12 ms 15056 KB Correct.
42 Correct 13 ms 14928 KB Correct.
43 Correct 11 ms 14924 KB Correct.
44 Correct 11 ms 15024 KB Correct.
45 Correct 11 ms 14928 KB Correct.
46 Correct 11 ms 14924 KB Correct.
47 Correct 10 ms 14924 KB Correct.
48 Correct 13 ms 15056 KB Correct.
49 Correct 11 ms 14924 KB Correct.
50 Correct 2160 ms 27256 KB Correct.
51 Correct 640 ms 25316 KB Correct.
52 Correct 3038 ms 30188 KB Correct.
53 Correct 2060 ms 27312 KB Correct.
54 Correct 2164 ms 28176 KB Correct.
55 Correct 2951 ms 29564 KB Correct.
56 Correct 2268 ms 27964 KB Correct.
57 Correct 2240 ms 27880 KB Correct.
58 Correct 542 ms 25028 KB Correct.
59 Correct 2061 ms 27108 KB Correct.
60 Correct 2532 ms 28624 KB Correct.
61 Correct 1725 ms 27848 KB Correct.
62 Correct 2565 ms 28704 KB Correct.
63 Correct 2512 ms 28584 KB Correct.
64 Correct 39 ms 23884 KB Correct.
65 Correct 2522 ms 28436 KB Correct.
66 Correct 2206 ms 29044 KB Correct.
67 Correct 2383 ms 30200 KB Correct.
68 Correct 3121 ms 30032 KB Correct.
69 Correct 2372 ms 28268 KB Correct.
70 Correct 2380 ms 28180 KB Correct.
71 Correct 3352 ms 31200 KB Correct.
72 Correct 2790 ms 29004 KB Correct.
73 Correct 3456 ms 31180 KB Correct.
74 Correct 3093 ms 31268 KB Correct.
75 Correct 3513 ms 30968 KB Correct.