oj.uz

Submission #220712

# Submission time Handle Problem Language Result Execution time Memory
220712 2020-04-08T12:48:13 Z Vimmer Skandi (COCI20_skandi) C++14
50 / 110
 10000 ms 44664 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])
        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 26240 KB Correct.
2 Correct 24 ms 26240 KB Correct.
3 Correct 24 ms 26240 KB Correct.
4 Correct 24 ms 26368 KB Correct.
5 Correct 24 ms 26240 KB Correct.
6 Correct 26 ms 26368 KB Correct.
7 Correct 25 ms 26240 KB Correct.
8 Correct 25 ms 26360 KB Correct.
9 Correct 25 ms 26240 KB Correct.
10 Correct 24 ms 26368 KB Correct.
11 Correct 24 ms 26240 KB Correct.
12 Correct 25 ms 26368 KB Correct.
13 Correct 24 ms 26368 KB Correct.
14 Correct 24 ms 26368 KB Correct.
15 Correct 24 ms 26368 KB Correct.
16 Correct 24 ms 26368 KB Correct.
17 Correct 24 ms 26368 KB Correct.
18 Correct 24 ms 26240 KB Correct.
19 Correct 24 ms 26240 KB Correct.
20 Correct 25 ms 26240 KB Correct.
21 Correct 30 ms 26368 KB Correct.
22 Correct 24 ms 26368 KB Correct.
23 Correct 25 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 26 ms 27136 KB Correct.
3 Correct 30 ms 27776 KB Correct.
4 Correct 27 ms 27008 KB Correct.
5 Correct 30 ms 27128 KB Correct.
6 Correct 27 ms 26752 KB Correct.
7 Correct 27 ms 26624 KB Correct.
8 Correct 31 ms 27136 KB Correct.
9 Correct 29 ms 28672 KB Correct.
10 Correct 43 ms 28544 KB Correct.
11 Correct 45 ms 28544 KB Correct.
12 Correct 40 ms 28664 KB Correct.
13 Correct 43 ms 28672 KB Correct.
14 Correct 44 ms 28544 KB Correct.
15 Correct 42 ms 28664 KB Correct.
16 Correct 42 ms 28664 KB Correct.
17 Correct 42 ms 28672 KB Correct.
18 Correct 44 ms 28664 KB Correct.
19 Correct 45 ms 28672 KB Correct.
20 Correct 38 ms 28672 KB Correct.
21 Correct 44 ms 28672 KB Correct.
22 Correct 44 ms 28664 KB Correct.
23 Correct 44 ms 28544 KB Correct.
24 Correct 34 ms 28672 KB Correct.
25 Correct 43 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 26240 KB Correct.
2 Correct 24 ms 26240 KB Correct.
3 Correct 24 ms 26240 KB Correct.
4 Correct 24 ms 26368 KB Correct.
5 Correct 24 ms 26240 KB Correct.
6 Correct 26 ms 26368 KB Correct.
7 Correct 25 ms 26240 KB Correct.
8 Correct 25 ms 26360 KB Correct.
9 Correct 25 ms 26240 KB Correct.
10 Correct 24 ms 26368 KB Correct.
11 Correct 24 ms 26240 KB Correct.
12 Correct 25 ms 26368 KB Correct.
13 Correct 24 ms 26368 KB Correct.
14 Correct 24 ms 26368 KB Correct.
15 Correct 24 ms 26368 KB Correct.
16 Correct 24 ms 26368 KB Correct.
17 Correct 24 ms 26368 KB Correct.
18 Correct 24 ms 26240 KB Correct.
19 Correct 24 ms 26240 KB Correct.
20 Correct 25 ms 26240 KB Correct.
21 Correct 30 ms 26368 KB Correct.
22 Correct 24 ms 26368 KB Correct.
23 Correct 25 ms 26240 KB Correct.
24 Correct 27 ms 28032 KB Correct.
25 Correct 26 ms 27136 KB Correct.
26 Correct 30 ms 27776 KB Correct.
27 Correct 27 ms 27008 KB Correct.
28 Correct 30 ms 27128 KB Correct.
29 Correct 27 ms 26752 KB Correct.
30 Correct 27 ms 26624 KB Correct.
31 Correct 31 ms 27136 KB Correct.
32 Correct 29 ms 28672 KB Correct.
33 Correct 43 ms 28544 KB Correct.
34 Correct 45 ms 28544 KB Correct.
35 Correct 40 ms 28664 KB Correct.
36 Correct 43 ms 28672 KB Correct.
37 Correct 44 ms 28544 KB Correct.
38 Correct 42 ms 28664 KB Correct.
39 Correct 42 ms 28664 KB Correct.
40 Correct 42 ms 28672 KB Correct.
41 Correct 44 ms 28664 KB Correct.
42 Correct 45 ms 28672 KB Correct.
43 Correct 38 ms 28672 KB Correct.
44 Correct 44 ms 28672 KB Correct.
45 Correct 44 ms 28664 KB Correct.
46 Correct 44 ms 28544 KB Correct.
47 Correct 34 ms 28672 KB Correct.
48 Correct 43 ms 28664 KB Correct.
49 Correct 43 ms 28544 KB Correct.
50 Correct 892 ms 41968 KB Correct.
51 Execution timed out 10059 ms 44664 KB Time limit exceeded
52 Halted 0 ms 0 KB -