oj.uz

Submission #710857

# Submission time Handle Problem Language Result Execution time Memory
710857 2023-03-16T02:33:17 Z Luicosas Skandi (COCI20_skandi) C++17
110 / 110
 381 ms 36764 KB 
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

#define pb push_back
#define sz(x) (int)(x.size())
#define itr(x) x.begin(), x.end()
#define prv(x) for(auto& i : x) cout << i << " "; cout << "\n";
#define debug(...) cerr << #__VA_ARGS__ << " : "; for(auto& i : {__VA_ARGS__}) cerr << i << " "; cerr << "\n";

vector<array<int,2>> locs;
vector<int> dis, calc, caps;
vector<vector<array<int,3>>> adj;

void cdis(int source) {
    deque<array<int,2>> que(1, {source, 0});
    while(sz(que) > 0) {
        int idx = que[0][0], d = que[0][1];
        que.pop_front();

        if(dis[idx] <= d) {
            continue;
        }
        dis[idx] = d;

        for(auto e : adj[idx]) {
            if(caps[e[1]] > 0) {
                que.push_back({e[0], d + 1});
            }
        }
    }
}

int augment(int idx, int cap, int sink) {
    if(idx == sink) {
        return cap;
    }

    while(calc[idx] < sz(adj[idx])) {
        auto& e = adj[idx][calc[idx]];
        if(dis[idx] >= dis[e[0]]) {
            calc[idx]++;
            continue;
        }
        if(caps[e[1]] == 0) {
            calc[idx]++;
            continue;
        }
        int aug = augment(e[0], min(cap, caps[e[1]]), sink);
        if(aug == 0) {
            calc[idx]++;
            continue;
        }
        caps[e[1]] -= aug;
        caps[e[2]] += aug;
        return aug;
    }
    return 0;
}

void dinic(int source, int sink) {
    while(true) {
        dis.assign(sz(adj), INT_MAX);
        cdis(source);

        if(dis[sink] == INT_MAX) {
            return;
        }

        calc.assign(sz(adj), 0);
        while(augment(source, INT_MAX, sink));
    }
}

vector<int> visx, visy;
void bilabel(int idx) {
    visy[idx] = 1;

    for(auto& e : adj[idx]) {
        int xidx = e[0] - sz(locs);
        if(e[0] < sz(locs) * 2 && visx[xidx] == 0 && caps[e[1]] == 1) {
            visx[xidx] = 1;
            for(auto& e : adj[e[0]]) {
                if(caps[e[1]] == 1 && !visy[e[0]]) {
                    bilabel(e[0]);
                }
            }
        }
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n, m;
    cin >> n >> m;

    vector<vector<int>> A(n, vector<int>(m, 0));
    for(auto& v : A) {
        for(auto& i : v) {
            char c;
            cin >> c;
            i = (c - '0');
        }
    }

    vector<vector<array<int,2>>> lb(n, vector<array<int,2>>(m, {-1, -1}));
    for(int y = 0; y < n; y++) {
        for(int x = 0; x < m; x++) {
            if(A[y][x]) {
                lb[y][x] = {sz(locs), sz(locs)};
                locs.pb({y + 1, x + 1});
            } else {
                lb[y][x][0] = lb[y - 1][x][0];
                lb[y][x][1] = lb[y][x - 1][1];
            }
            // cout << "{" << lb[y][x][0] << " " << lb[y][x][1] << "} ";
        }
        // cout << "\n";
    }

    adj.assign(sz(locs) * 2 + 2, vector<array<int,3>>(0));
    int src = sz(locs) * 2, snk = src + 1;;
    function<void(int,int,int)> addedge = [&](int u, int v, int cap) {
        int c1 = sz(caps);
        caps.pb(cap);
        int c2 = sz(caps);
        caps.pb(0);
        adj[u].pb({v, c1, c2});
        adj[v].pb({u, c2, c1});
    };
    for(int i = 0; i < sz(locs); i++) {
        addedge(src, i, 1);
        addedge(sz(locs) + i, snk, 1);
    }
    for(int y = 0; y < n; y++) {
        for(int x = 0; x < m; x++) {
            if(A[y][x] == 0) {
                addedge(lb[y][x][0], sz(locs) + lb[y][x][1], 1);
            }
        }
    }

    dinic(src, snk);

    //debug(sz(locs));
    //for(int i = 0; i < sz(locs); i++) {
    //    for(auto& e : adj[i]) if(e[0] < src) {
    //        debug(i, e[0], caps[e[1]], caps[e[2]]);
    //    }
    //}

    visx.assign(sz(locs), 0);
    visy.assign(sz(locs), 0);
    for(int i = 0; i < sz(locs); i++) {
        bool matched = 0;
        for(auto& e : adj[i]) {
            if(e[0] < sz(locs) * 2 && caps[e[2]] == 1) {
                matched = 1;
            }
        }
        // debug(matched);
        if(!matched) {
            bilabel(i);
        }
    }
    //for(int i = 0; i < sz(locs); i++) {
    //    cout << visy[i] << " ";
    //}
    //cout << "\n";
    //for(int i = 0; i < sz(locs); i++) {
    //    cout << visx[i] << " ";
    //}
    //cout << "\n";

    int cnt = 0;
    for(int i = 0; i < sz(locs); i++) {
        if(!visy[i]) {
            cnt++;
        }
        if(visx[i]) {
            cnt++;
        }
    }

    cout << cnt << "\n";
    for(int i = 0; i < sz(locs); i++) {
        if(!visy[i]) {
            cout << locs[i][0] << " " << locs[i][1] << " DOLJE\n";
        }
        if(visx[i]) {
            cout << locs[i][0] << " " << locs[i][1] << " DESNO\n";
        }
    }
}

Subtask #1
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Correct.
2 Correct 1 ms 212 KB Correct.
3 Correct 0 ms 212 KB Correct.
4 Correct 1 ms 212 KB Correct.
5 Correct 1 ms 320 KB Correct.
6 Correct 1 ms 212 KB Correct.
7 Correct 1 ms 212 KB Correct.
8 Correct 1 ms 212 KB Correct.
9 Correct 1 ms 212 KB Correct.
10 Correct 1 ms 212 KB Correct.
11 Correct 1 ms 212 KB Correct.
12 Correct 1 ms 212 KB Correct.
13 Correct 0 ms 212 KB Correct.
14 Correct 1 ms 212 KB Correct.
15 Correct 1 ms 212 KB Correct.
16 Correct 1 ms 212 KB Correct.
17 Correct 1 ms 212 KB Correct.
18 Correct 1 ms 212 KB Correct.
19 Correct 1 ms 212 KB Correct.
20 Correct 1 ms 340 KB Correct.
21 Correct 1 ms 212 KB Correct.
22 Correct 0 ms 212 KB Correct.
23 Correct 1 ms 212 KB Correct.

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Correct.
2 Correct 1 ms 340 KB Correct.
3 Correct 1 ms 468 KB Correct.
4 Correct 1 ms 468 KB Correct.
5 Correct 1 ms 468 KB Correct.
6 Correct 1 ms 340 KB Correct.
7 Correct 1 ms 320 KB Correct.
8 Correct 1 ms 468 KB Correct.
9 Correct 1 ms 724 KB Correct.
10 Correct 3 ms 1108 KB Correct.
11 Correct 3 ms 980 KB Correct.
12 Correct 3 ms 832 KB Correct.
13 Correct 3 ms 1084 KB Correct.
14 Correct 2 ms 980 KB Correct.
15 Correct 3 ms 968 KB Correct.
16 Correct 3 ms 996 KB Correct.
17 Correct 3 ms 852 KB Correct.
18 Correct 3 ms 852 KB Correct.
19 Correct 3 ms 980 KB Correct.
20 Correct 2 ms 852 KB Correct.
21 Correct 2 ms 960 KB Correct.
22 Correct 3 ms 960 KB Correct.
23 Correct 3 ms 964 KB Correct.
24 Correct 3 ms 852 KB Correct.
25 Correct 3 ms 980 KB Correct.
26 Correct 3 ms 980 KB Correct.

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Correct.
2 Correct 1 ms 212 KB Correct.
3 Correct 0 ms 212 KB Correct.
4 Correct 1 ms 212 KB Correct.
5 Correct 1 ms 320 KB Correct.
6 Correct 1 ms 212 KB Correct.
7 Correct 1 ms 212 KB Correct.
8 Correct 1 ms 212 KB Correct.
9 Correct 1 ms 212 KB Correct.
10 Correct 1 ms 212 KB Correct.
11 Correct 1 ms 212 KB Correct.
12 Correct 1 ms 212 KB Correct.
13 Correct 0 ms 212 KB Correct.
14 Correct 1 ms 212 KB Correct.
15 Correct 1 ms 212 KB Correct.
16 Correct 1 ms 212 KB Correct.
17 Correct 1 ms 212 KB Correct.
18 Correct 1 ms 212 KB Correct.
19 Correct 1 ms 212 KB Correct.
20 Correct 1 ms 340 KB Correct.
21 Correct 1 ms 212 KB Correct.
22 Correct 0 ms 212 KB Correct.
23 Correct 1 ms 212 KB Correct.
24 Correct 1 ms 468 KB Correct.
25 Correct 1 ms 340 KB Correct.
26 Correct 1 ms 468 KB Correct.
27 Correct 1 ms 468 KB Correct.
28 Correct 1 ms 468 KB Correct.
29 Correct 1 ms 340 KB Correct.
30 Correct 1 ms 320 KB Correct.
31 Correct 1 ms 468 KB Correct.
32 Correct 1 ms 724 KB Correct.
33 Correct 3 ms 1108 KB Correct.
34 Correct 3 ms 980 KB Correct.
35 Correct 3 ms 832 KB Correct.
36 Correct 3 ms 1084 KB Correct.
37 Correct 2 ms 980 KB Correct.
38 Correct 3 ms 968 KB Correct.
39 Correct 3 ms 996 KB Correct.
40 Correct 3 ms 852 KB Correct.
41 Correct 3 ms 852 KB Correct.
42 Correct 3 ms 980 KB Correct.
43 Correct 2 ms 852 KB Correct.
44 Correct 2 ms 960 KB Correct.
45 Correct 3 ms 960 KB Correct.
46 Correct 3 ms 964 KB Correct.
47 Correct 3 ms 852 KB Correct.
48 Correct 3 ms 980 KB Correct.
49 Correct 3 ms 980 KB Correct.
50 Correct 167 ms 29744 KB Correct.
51 Correct 377 ms 15328 KB Correct.
52 Correct 244 ms 24772 KB Correct.
53 Correct 162 ms 31552 KB Correct.
54 Correct 201 ms 21548 KB Correct.
55 Correct 170 ms 30260 KB Correct.
56 Correct 164 ms 35328 KB Correct.
57 Correct 162 ms 34092 KB Correct.
58 Correct 381 ms 14812 KB Correct.
59 Correct 144 ms 23484 KB Correct.
60 Correct 174 ms 29300 KB Correct.
61 Correct 266 ms 19440 KB Correct.
62 Correct 173 ms 29100 KB Correct.
63 Correct 172 ms 30012 KB Correct.
64 Correct 34 ms 13252 KB Correct.
65 Correct 173 ms 29952 KB Correct.
66 Correct 244 ms 21792 KB Correct.
67 Correct 362 ms 22880 KB Correct.
68 Correct 208 ms 29136 KB Correct.
69 Correct 189 ms 27100 KB Correct.
70 Correct 183 ms 29044 KB Correct.
71 Correct 271 ms 26404 KB Correct.
72 Correct 180 ms 36764 KB Correct.
73 Correct 260 ms 28948 KB Correct.
74 Correct 285 ms 25896 KB Correct.
75 Correct 259 ms 30644 KB Correct.