oj.uz

Submission #220715

# Submission time Handle Problem Language Result Execution time Memory
220715 2020-04-08T12:52:09 Z Vimmer Skandi (COCI20_skandi) C++14
110 / 110
 5651 ms 32108 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 500005
#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];

vector <int> g[N];


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

set <pair <int, int> > se;

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;

                was[v] = 1;

                return 1;
            }
    }

    return 0;
}

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

    if (!tp)
    {
        for (auto it : g[v])
            if (!mkr[it] && se.find({v, it}) == se.end()) 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]].pb(idr[i][y][0]);
            }

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

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

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

        was[i] = kuna(i);
    }

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

    for (int i = 0; i < id; i++) if (mt[i] != -1) se.insert({mt[i], i});

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

    for (int i = 0; i < id; 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 14 ms 14592 KB Correct.
2 Correct 13 ms 14592 KB Correct.
3 Correct 13 ms 14592 KB Correct.
4 Correct 15 ms 14592 KB Correct.
5 Correct 13 ms 14592 KB Correct.
6 Correct 13 ms 14592 KB Correct.
7 Correct 13 ms 14592 KB Correct.
8 Correct 13 ms 14592 KB Correct.
9 Correct 13 ms 14592 KB Correct.
10 Correct 13 ms 14592 KB Correct.
11 Correct 14 ms 14592 KB Correct.
12 Correct 13 ms 14592 KB Correct.
13 Correct 13 ms 14592 KB Correct.
14 Correct 13 ms 14592 KB Correct.
15 Correct 13 ms 14592 KB Correct.
16 Correct 13 ms 14592 KB Correct.
17 Correct 13 ms 14592 KB Correct.
18 Correct 13 ms 14592 KB Correct.
19 Correct 14 ms 14592 KB Correct.
20 Correct 13 ms 14592 KB Correct.
21 Correct 13 ms 14592 KB Correct.
22 Correct 13 ms 14592 KB Correct.
23 Correct 13 ms 14592 KB Correct.

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 16256 KB Correct.
2 Correct 15 ms 15360 KB Correct.
3 Correct 18 ms 16000 KB Correct.
4 Correct 16 ms 15232 KB Correct.
5 Correct 19 ms 15488 KB Correct.
6 Correct 15 ms 14976 KB Correct.
7 Correct 16 ms 14848 KB Correct.
8 Correct 19 ms 15360 KB Correct.
9 Correct 16 ms 16768 KB Correct.
10 Correct 33 ms 16888 KB Correct.
11 Correct 36 ms 16768 KB Correct.
12 Correct 33 ms 16896 KB Correct.
13 Correct 32 ms 16896 KB Correct.
14 Correct 32 ms 16892 KB Correct.
15 Correct 34 ms 16896 KB Correct.
16 Correct 32 ms 16896 KB Correct.
17 Correct 29 ms 16768 KB Correct.
18 Correct 29 ms 16892 KB Correct.
19 Correct 32 ms 16888 KB Correct.
20 Correct 26 ms 16896 KB Correct.
21 Correct 32 ms 16888 KB Correct.
22 Correct 35 ms 16888 KB Correct.
23 Correct 33 ms 16888 KB Correct.
24 Correct 23 ms 16768 KB Correct.
25 Correct 32 ms 16896 KB Correct.
26 Correct 34 ms 16888 KB Correct.

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 14592 KB Correct.
2 Correct 13 ms 14592 KB Correct.
3 Correct 13 ms 14592 KB Correct.
4 Correct 15 ms 14592 KB Correct.
5 Correct 13 ms 14592 KB Correct.
6 Correct 13 ms 14592 KB Correct.
7 Correct 13 ms 14592 KB Correct.
8 Correct 13 ms 14592 KB Correct.
9 Correct 13 ms 14592 KB Correct.
10 Correct 13 ms 14592 KB Correct.
11 Correct 14 ms 14592 KB Correct.
12 Correct 13 ms 14592 KB Correct.
13 Correct 13 ms 14592 KB Correct.
14 Correct 13 ms 14592 KB Correct.
15 Correct 13 ms 14592 KB Correct.
16 Correct 13 ms 14592 KB Correct.
17 Correct 13 ms 14592 KB Correct.
18 Correct 13 ms 14592 KB Correct.
19 Correct 14 ms 14592 KB Correct.
20 Correct 13 ms 14592 KB Correct.
21 Correct 13 ms 14592 KB Correct.
22 Correct 13 ms 14592 KB Correct.
23 Correct 13 ms 14592 KB Correct.
24 Correct 15 ms 16256 KB Correct.
25 Correct 15 ms 15360 KB Correct.
26 Correct 18 ms 16000 KB Correct.
27 Correct 16 ms 15232 KB Correct.
28 Correct 19 ms 15488 KB Correct.
29 Correct 15 ms 14976 KB Correct.
30 Correct 16 ms 14848 KB Correct.
31 Correct 19 ms 15360 KB Correct.
32 Correct 16 ms 16768 KB Correct.
33 Correct 33 ms 16888 KB Correct.
34 Correct 36 ms 16768 KB Correct.
35 Correct 33 ms 16896 KB Correct.
36 Correct 32 ms 16896 KB Correct.
37 Correct 32 ms 16892 KB Correct.
38 Correct 34 ms 16896 KB Correct.
39 Correct 32 ms 16896 KB Correct.
40 Correct 29 ms 16768 KB Correct.
41 Correct 29 ms 16892 KB Correct.
42 Correct 32 ms 16888 KB Correct.
43 Correct 26 ms 16896 KB Correct.
44 Correct 32 ms 16888 KB Correct.
45 Correct 35 ms 16888 KB Correct.
46 Correct 33 ms 16888 KB Correct.
47 Correct 23 ms 16768 KB Correct.
48 Correct 32 ms 16896 KB Correct.
49 Correct 34 ms 16888 KB Correct.
50 Correct 914 ms 29604 KB Correct.
51 Correct 5651 ms 27076 KB Correct.
52 Correct 914 ms 30956 KB Correct.
53 Correct 847 ms 29932 KB Correct.
54 Correct 782 ms 28784 KB Correct.
55 Correct 998 ms 31340 KB Correct.
56 Correct 950 ms 31088 KB Correct.
57 Correct 916 ms 30576 KB Correct.
58 Correct 3635 ms 26980 KB Correct.
59 Correct 874 ms 28268 KB Correct.
60 Correct 915 ms 30320 KB Correct.
61 Correct 679 ms 28592 KB Correct.
62 Correct 1006 ms 30192 KB Correct.
63 Correct 957 ms 30576 KB Correct.
64 Correct 193 ms 25976 KB Correct.
65 Correct 936 ms 30452 KB Correct.
66 Correct 777 ms 29696 KB Correct.
67 Correct 796 ms 30700 KB Correct.
68 Correct 999 ms 31472 KB Correct.
69 Correct 881 ms 29636 KB Correct.
70 Correct 907 ms 30192 KB Correct.
71 Correct 1038 ms 31864 KB Correct.
72 Correct 1008 ms 31704 KB Correct.
73 Correct 1012 ms 32108 KB Correct.
74 Correct 936 ms 31728 KB Correct.
75 Correct 1036 ms 32036 KB Correct.