oj.uz

Submission #220704

# Submission time Handle Problem Language Result Execution time Memory
220704 2020-04-08T12:40:05 Z Vimmer Skandi (COCI20_skandi) C++14
50 / 110
 10000 ms 70292 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[N][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 44 ms 52224 KB Correct.
2 Correct 42 ms 52224 KB Correct.
3 Correct 42 ms 52216 KB Correct.
4 Correct 43 ms 52224 KB Correct.
5 Correct 45 ms 52352 KB Correct.
6 Correct 44 ms 52224 KB Correct.
7 Correct 43 ms 52216 KB Correct.
8 Correct 44 ms 52220 KB Correct.
9 Correct 44 ms 52224 KB Correct.
10 Correct 43 ms 52224 KB Correct.
11 Correct 46 ms 52352 KB Correct.
12 Correct 43 ms 52224 KB Correct.
13 Correct 43 ms 52224 KB Correct.
14 Correct 44 ms 52216 KB Correct.
15 Correct 44 ms 52224 KB Correct.
16 Correct 44 ms 52224 KB Correct.
17 Correct 47 ms 52224 KB Correct.
18 Correct 43 ms 52224 KB Correct.
19 Correct 48 ms 52216 KB Correct.
20 Correct 44 ms 52224 KB Correct.
21 Correct 44 ms 52216 KB Correct.
22 Correct 44 ms 52224 KB Correct.
23 Correct 46 ms 52352 KB Correct.

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 54016 KB Correct.
2 Correct 45 ms 52984 KB Correct.
3 Correct 52 ms 53752 KB Correct.
4 Correct 48 ms 52984 KB Correct.
5 Correct 48 ms 52992 KB Correct.
6 Correct 49 ms 52608 KB Correct.
7 Correct 48 ms 52608 KB Correct.
8 Correct 53 ms 52992 KB Correct.
9 Correct 49 ms 54648 KB Correct.
10 Correct 78 ms 54520 KB Correct.
11 Correct 81 ms 54520 KB Correct.
12 Correct 80 ms 54520 KB Correct.
13 Correct 79 ms 54520 KB Correct.
14 Correct 82 ms 54520 KB Correct.
15 Correct 77 ms 54544 KB Correct.
16 Correct 78 ms 54544 KB Correct.
17 Correct 72 ms 54648 KB Correct.
18 Correct 72 ms 54528 KB Correct.
19 Correct 79 ms 54528 KB Correct.
20 Correct 68 ms 54528 KB Correct.
21 Correct 77 ms 54528 KB Correct.
22 Correct 78 ms 54528 KB Correct.
23 Correct 77 ms 54520 KB Correct.
24 Correct 60 ms 54648 KB Correct.
25 Correct 77 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 44 ms 52224 KB Correct.
2 Correct 42 ms 52224 KB Correct.
3 Correct 42 ms 52216 KB Correct.
4 Correct 43 ms 52224 KB Correct.
5 Correct 45 ms 52352 KB Correct.
6 Correct 44 ms 52224 KB Correct.
7 Correct 43 ms 52216 KB Correct.
8 Correct 44 ms 52220 KB Correct.
9 Correct 44 ms 52224 KB Correct.
10 Correct 43 ms 52224 KB Correct.
11 Correct 46 ms 52352 KB Correct.
12 Correct 43 ms 52224 KB Correct.
13 Correct 43 ms 52224 KB Correct.
14 Correct 44 ms 52216 KB Correct.
15 Correct 44 ms 52224 KB Correct.
16 Correct 44 ms 52224 KB Correct.
17 Correct 47 ms 52224 KB Correct.
18 Correct 43 ms 52224 KB Correct.
19 Correct 48 ms 52216 KB Correct.
20 Correct 44 ms 52224 KB Correct.
21 Correct 44 ms 52216 KB Correct.
22 Correct 44 ms 52224 KB Correct.
23 Correct 46 ms 52352 KB Correct.
24 Correct 47 ms 54016 KB Correct.
25 Correct 45 ms 52984 KB Correct.
26 Correct 52 ms 53752 KB Correct.
27 Correct 48 ms 52984 KB Correct.
28 Correct 48 ms 52992 KB Correct.
29 Correct 49 ms 52608 KB Correct.
30 Correct 48 ms 52608 KB Correct.
31 Correct 53 ms 52992 KB Correct.
32 Correct 49 ms 54648 KB Correct.
33 Correct 78 ms 54520 KB Correct.
34 Correct 81 ms 54520 KB Correct.
35 Correct 80 ms 54520 KB Correct.
36 Correct 79 ms 54520 KB Correct.
37 Correct 82 ms 54520 KB Correct.
38 Correct 77 ms 54544 KB Correct.
39 Correct 78 ms 54544 KB Correct.
40 Correct 72 ms 54648 KB Correct.
41 Correct 72 ms 54528 KB Correct.
42 Correct 79 ms 54528 KB Correct.
43 Correct 68 ms 54528 KB Correct.
44 Correct 77 ms 54528 KB Correct.
45 Correct 78 ms 54528 KB Correct.
46 Correct 77 ms 54520 KB Correct.
47 Correct 60 ms 54648 KB Correct.
48 Correct 77 ms 54648 KB Correct.
49 Correct 79 ms 54520 KB Correct.
50 Correct 1604 ms 67676 KB Correct.
51 Execution timed out 10055 ms 70292 KB Time limit exceeded
52 Halted 0 ms 0 KB -