oj.uz

Submission #220713

# Submission time Handle Problem Language Result Execution time Memory
220713 2020-04-08T12:48:57 Z Vimmer Skandi (COCI20_skandi) C++14
50 / 110
 10000 ms 44296 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];

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;

                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]) 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 || 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 < N; i++) if (mt[i] != -1) g[mt[i]].erase(i);

    for (int i = 0; i < N; i++) if (lft[i] && !was[i] && !mkr[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 24 ms 26368 KB Correct.
2 Correct 24 ms 26240 KB Correct.
3 Correct 24 ms 26368 KB Correct.
4 Correct 24 ms 26368 KB Correct.
5 Correct 26 ms 26368 KB Correct.
6 Correct 26 ms 26240 KB Correct.
7 Correct 25 ms 26240 KB Correct.
8 Correct 25 ms 26496 KB Correct.
9 Correct 25 ms 26368 KB Correct.
10 Correct 25 ms 26240 KB Correct.
11 Correct 24 ms 26240 KB Correct.
12 Correct 24 ms 26240 KB Correct.
13 Correct 27 ms 26368 KB Correct.
14 Correct 27 ms 26240 KB Correct.
15 Correct 25 ms 26240 KB Correct.
16 Correct 24 ms 26240 KB Correct.
17 Correct 24 ms 26240 KB Correct.
18 Correct 23 ms 26240 KB Correct.
19 Correct 25 ms 26368 KB Correct.
20 Correct 26 ms 26240 KB Correct.
21 Correct 26 ms 26368 KB Correct.
22 Correct 24 ms 26240 KB Correct.
23 Correct 24 ms 26240 KB Correct.

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 28032 KB Correct.
2 Correct 27 ms 27136 KB Correct.
3 Correct 29 ms 27776 KB Correct.
4 Correct 27 ms 27008 KB Correct.
5 Correct 27 ms 27008 KB Correct.
6 Correct 26 ms 26752 KB Correct.
7 Correct 26 ms 26624 KB Correct.
8 Correct 31 ms 27136 KB Correct.
9 Correct 29 ms 28672 KB Correct.
10 Correct 47 ms 28664 KB Correct.
11 Correct 47 ms 28644 KB Correct.
12 Correct 41 ms 28664 KB Correct.
13 Correct 44 ms 28544 KB Correct.
14 Correct 45 ms 28544 KB Correct.
15 Correct 42 ms 28664 KB Correct.
16 Correct 44 ms 28668 KB Correct.
17 Correct 41 ms 28664 KB Correct.
18 Correct 39 ms 28664 KB Correct.
19 Correct 45 ms 28664 KB Correct.
20 Correct 37 ms 28672 KB Correct.
21 Correct 45 ms 28664 KB Correct.
22 Correct 49 ms 28672 KB Correct.
23 Correct 46 ms 28672 KB Correct.
24 Correct 35 ms 28672 KB Correct.
25 Correct 42 ms 28664 KB Correct.
26 Correct 43 ms 28544 KB Correct.

Subtask #3
0.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 26368 KB Correct.
2 Correct 24 ms 26240 KB Correct.
3 Correct 24 ms 26368 KB Correct.
4 Correct 24 ms 26368 KB Correct.
5 Correct 26 ms 26368 KB Correct.
6 Correct 26 ms 26240 KB Correct.
7 Correct 25 ms 26240 KB Correct.
8 Correct 25 ms 26496 KB Correct.
9 Correct 25 ms 26368 KB Correct.
10 Correct 25 ms 26240 KB Correct.
11 Correct 24 ms 26240 KB Correct.
12 Correct 24 ms 26240 KB Correct.
13 Correct 27 ms 26368 KB Correct.
14 Correct 27 ms 26240 KB Correct.
15 Correct 25 ms 26240 KB Correct.
16 Correct 24 ms 26240 KB Correct.
17 Correct 24 ms 26240 KB Correct.
18 Correct 23 ms 26240 KB Correct.
19 Correct 25 ms 26368 KB Correct.
20 Correct 26 ms 26240 KB Correct.
21 Correct 26 ms 26368 KB Correct.
22 Correct 24 ms 26240 KB Correct.
23 Correct 24 ms 26240 KB Correct.
24 Correct 27 ms 28032 KB Correct.
25 Correct 27 ms 27136 KB Correct.
26 Correct 29 ms 27776 KB Correct.
27 Correct 27 ms 27008 KB Correct.
28 Correct 27 ms 27008 KB Correct.
29 Correct 26 ms 26752 KB Correct.
30 Correct 26 ms 26624 KB Correct.
31 Correct 31 ms 27136 KB Correct.
32 Correct 29 ms 28672 KB Correct.
33 Correct 47 ms 28664 KB Correct.
34 Correct 47 ms 28644 KB Correct.
35 Correct 41 ms 28664 KB Correct.
36 Correct 44 ms 28544 KB Correct.
37 Correct 45 ms 28544 KB Correct.
38 Correct 42 ms 28664 KB Correct.
39 Correct 44 ms 28668 KB Correct.
40 Correct 41 ms 28664 KB Correct.
41 Correct 39 ms 28664 KB Correct.
42 Correct 45 ms 28664 KB Correct.
43 Correct 37 ms 28672 KB Correct.
44 Correct 45 ms 28664 KB Correct.
45 Correct 49 ms 28672 KB Correct.
46 Correct 46 ms 28672 KB Correct.
47 Correct 35 ms 28672 KB Correct.
48 Correct 42 ms 28664 KB Correct.
49 Correct 43 ms 28544 KB Correct.
50 Correct 859 ms 41856 KB Correct.
51 Execution timed out 10083 ms 44296 KB Time limit exceeded
52 Halted 0 ms 0 KB -