oj.uz

Submission #220703

# Submission time Handle Problem Language Result Execution time Memory
220703 2020-04-08T12:39:36 Z Vimmer Skandi (COCI20_skandi) C++14
50 / 110
 1050 ms 64220 KB 
#include <bits/stdc++.h>

//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("-O3")
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("fast-math")
//#pragma GCC optimize("no-stack-protector")

#define F first
#define S second
#define sz(x) int(x.size())
#define pb push_back
#define N 1000005
#define MOD ll(998244353)

using namespace std;

typedef long long ll;

typedef long double ld;



int mt[N], idr[505][505][2];

pair <int, int> conv[505 * 505][2];

bool lft[N];

set <int> g[N];


bool mk[N], mkr[N], was[N];

bool kuna(int v)
{
    if (mk[v]) return 0;

    mk[v] = 1;

    for (auto it : g[v])
    {
        if (mt[it] == -1 || kuna(mt[it]))
            {
                mt[it] = v;

                return 1;
            }
    }

    return 0;
}

void dfs(int v, int tp)
{
    mkr[v] = 1;

    if (!tp)
    {
        for (auto it : g[v])
            if (!mkr[it]) dfs(it, 1);
    }
    else if (mt[v] != -1 && !mkr[mt[v]]) dfs(mt[v], 0);
}
int main()
{
    ios_base::sync_with_stdio(0); istream::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    int n, m;

    cin >> n >> m;

    string s[n];

    for (int i = 0; i < n; i++) cin >> s[i];

    int id = 0;

    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++) {conv[id][0] = {i, j}; idr[i][j][0] = id++; lft[id] = 1; conv[id][1] = {i, j}; idr[i][j][1] = id++;}

    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
          if (s[i][j] == '0')
            {
                int x = i;

                while (s[x][j] == '0') x--;

                int y = j;

                while (s[i][y] == '0') y--;

                g[idr[x][j][1]].insert(idr[i][y][0]);
            }

    memset(mt, -1, sizeof(mt));

    for (int i = 0; i < N; i++)
    {
        if (sz(g[i]) == 0) continue;

        memset(mk, 0, sizeof(mk));

        kuna(i);
    }

    vector <pair <pair <int, int>, int> > ans; ans.clear();

    for (int i = 0; i < N; i++) if (mt[i] != -1) {g[mt[i]].erase(i); was[mt[i]] = 1;}

    for (int i = 0; i < N; i++) if (lft[i] && !was[i]) dfs(i, 0);

    for (int i = 0; i < N; i++)
    {
        if (lft[i] && !mkr[i]) ans.pb({conv[i][1], 1});

        if (mkr[i] && !lft[i]) ans.pb({conv[i][0], 0});
    }
    cout << sz(ans) << endl;

    for (auto it : ans) cout << it.F.F + 1 << " " << it.F.S + 1 << " " << (it.S == 0 ? "DESNO" : "DOLJE") << endl;
}

Subtask #1
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 52224 KB Correct.
2 Correct 44 ms 52224 KB Correct.
3 Correct 44 ms 52224 KB Correct.
4 Correct 43 ms 52224 KB Correct.
5 Correct 44 ms 52224 KB Correct.
6 Correct 42 ms 52224 KB Correct.
7 Correct 43 ms 52224 KB Correct.
8 Correct 44 ms 52352 KB Correct.
9 Correct 44 ms 52352 KB Correct.
10 Correct 44 ms 52224 KB Correct.
11 Correct 43 ms 52224 KB Correct.
12 Correct 43 ms 52224 KB Correct.
13 Correct 44 ms 52224 KB Correct.
14 Correct 43 ms 52224 KB Correct.
15 Correct 43 ms 52224 KB Correct.
16 Correct 43 ms 52216 KB Correct.
17 Correct 43 ms 52224 KB Correct.
18 Correct 44 ms 52216 KB Correct.
19 Correct 52 ms 52224 KB Correct.
20 Correct 47 ms 52344 KB Correct.
21 Correct 43 ms 52280 KB Correct.
22 Correct 43 ms 52216 KB Correct.
23 Correct 44 ms 52224 KB Correct.

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 53988 KB Correct.
2 Correct 46 ms 52992 KB Correct.
3 Correct 52 ms 53752 KB Correct.
4 Correct 49 ms 52984 KB Correct.
5 Correct 49 ms 52984 KB Correct.
6 Correct 48 ms 52608 KB Correct.
7 Correct 48 ms 52608 KB Correct.
8 Correct 55 ms 52992 KB Correct.
9 Correct 48 ms 54656 KB Correct.
10 Correct 81 ms 54524 KB Correct.
11 Correct 82 ms 54520 KB Correct.
12 Correct 73 ms 54528 KB Correct.
13 Correct 78 ms 54520 KB Correct.
14 Correct 78 ms 54520 KB Correct.
15 Correct 85 ms 54648 KB Correct.
16 Correct 91 ms 54576 KB Correct.
17 Correct 79 ms 54524 KB Correct.
18 Correct 76 ms 54520 KB Correct.
19 Correct 80 ms 54528 KB Correct.
20 Correct 77 ms 54580 KB Correct.
21 Correct 78 ms 54524 KB Correct.
22 Correct 82 ms 54528 KB Correct.
23 Correct 80 ms 54520 KB Correct.
24 Correct 63 ms 54624 KB Correct.
25 Correct 80 ms 54648 KB Correct.
26 Correct 79 ms 54520 KB Correct.

Subtask #3
0.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 52224 KB Correct.
2 Correct 44 ms 52224 KB Correct.
3 Correct 44 ms 52224 KB Correct.
4 Correct 43 ms 52224 KB Correct.
5 Correct 44 ms 52224 KB Correct.
6 Correct 42 ms 52224 KB Correct.
7 Correct 43 ms 52224 KB Correct.
8 Correct 44 ms 52352 KB Correct.
9 Correct 44 ms 52352 KB Correct.
10 Correct 44 ms 52224 KB Correct.
11 Correct 43 ms 52224 KB Correct.
12 Correct 43 ms 52224 KB Correct.
13 Correct 44 ms 52224 KB Correct.
14 Correct 43 ms 52224 KB Correct.
15 Correct 43 ms 52224 KB Correct.
16 Correct 43 ms 52216 KB Correct.
17 Correct 43 ms 52224 KB Correct.
18 Correct 44 ms 52216 KB Correct.
19 Correct 52 ms 52224 KB Correct.
20 Correct 47 ms 52344 KB Correct.
21 Correct 43 ms 52280 KB Correct.
22 Correct 43 ms 52216 KB Correct.
23 Correct 44 ms 52224 KB Correct.
24 Correct 48 ms 53988 KB Correct.
25 Correct 46 ms 52992 KB Correct.
26 Correct 52 ms 53752 KB Correct.
27 Correct 49 ms 52984 KB Correct.
28 Correct 49 ms 52984 KB Correct.
29 Correct 48 ms 52608 KB Correct.
30 Correct 48 ms 52608 KB Correct.
31 Correct 55 ms 52992 KB Correct.
32 Correct 48 ms 54656 KB Correct.
33 Correct 81 ms 54524 KB Correct.
34 Correct 82 ms 54520 KB Correct.
35 Correct 73 ms 54528 KB Correct.
36 Correct 78 ms 54520 KB Correct.
37 Correct 78 ms 54520 KB Correct.
38 Correct 85 ms 54648 KB Correct.
39 Correct 91 ms 54576 KB Correct.
40 Correct 79 ms 54524 KB Correct.
41 Correct 76 ms 54520 KB Correct.
42 Correct 80 ms 54528 KB Correct.
43 Correct 77 ms 54580 KB Correct.
44 Correct 78 ms 54524 KB Correct.
45 Correct 82 ms 54528 KB Correct.
46 Correct 80 ms 54520 KB Correct.
47 Correct 63 ms 54624 KB Correct.
48 Correct 80 ms 54648 KB Correct.
49 Correct 79 ms 54520 KB Correct.
50 Incorrect 1050 ms 64220 KB First line is not correct.
51 Halted 0 ms 0 KB -