oj.uz

Submission #391541

# Submission time Handle Problem Language Result Execution time Memory
391541 2021-04-19T09:29:08 Z phathnv Skandi (COCI20_skandi) C++11
0 / 110
 10000 ms 14668 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))
            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:99:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   99 |     scanf("%d %d", &m, &n);
      |     ~~~~~^~~~~~~~~~~~~~~~~
skandi.cpp:101:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  101 |         scanf("%s", a[i] + 1);
      |         ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Execution timed out 10089 ms 14412 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 32.0

# Verdict Execution time Memory Grader output
1 Execution timed out 10067 ms 14668 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 60.0

# Verdict Execution time Memory Grader output
1 Execution timed out 10089 ms 14412 KB Time limit exceeded
2 Halted 0 ms 0 KB -