oj.uz

Submission #220705

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

                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 24 ms 26240 KB Correct.
2 Correct 24 ms 26240 KB Correct.
3 Correct 24 ms 26240 KB Correct.
4 Correct 25 ms 26240 KB Correct.
5 Correct 24 ms 26368 KB Correct.
6 Correct 25 ms 26240 KB Correct.
7 Correct 24 ms 26240 KB Correct.
8 Correct 24 ms 26240 KB Correct.
9 Correct 24 ms 26240 KB Correct.
10 Correct 24 ms 26240 KB Correct.
11 Correct 24 ms 26240 KB Correct.
12 Correct 23 ms 26368 KB Correct.
13 Correct 25 ms 26240 KB Correct.
14 Correct 24 ms 26240 KB Correct.
15 Correct 25 ms 26240 KB Correct.
16 Correct 27 ms 26240 KB Correct.
17 Correct 25 ms 26240 KB Correct.
18 Correct 24 ms 26368 KB Correct.
19 Correct 28 ms 26360 KB Correct.
20 Correct 24 ms 26240 KB Correct.
21 Correct 24 ms 26240 KB Correct.
22 Correct 25 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 26 ms 28032 KB Correct.
2 Correct 25 ms 27136 KB Correct.
3 Correct 30 ms 27776 KB Correct.
4 Correct 27 ms 27008 KB Correct.
5 Correct 28 ms 27008 KB Correct.
6 Correct 26 ms 26624 KB Correct.
7 Correct 27 ms 26624 KB Correct.
8 Correct 30 ms 27136 KB Correct.
9 Correct 28 ms 28672 KB Correct.
10 Correct 44 ms 28544 KB Correct.
11 Correct 44 ms 28544 KB Correct.
12 Correct 44 ms 28664 KB Correct.
13 Correct 46 ms 28544 KB Correct.
14 Correct 46 ms 28544 KB Correct.
15 Correct 45 ms 28664 KB Correct.
16 Correct 43 ms 28672 KB Correct.
17 Correct 41 ms 28664 KB Correct.
18 Correct 38 ms 28672 KB Correct.
19 Correct 45 ms 28664 KB Correct.
20 Correct 36 ms 28664 KB Correct.
21 Correct 43 ms 28664 KB Correct.
22 Correct 44 ms 28664 KB Correct.
23 Correct 45 ms 28544 KB Correct.
24 Correct 35 ms 28672 KB Correct.
25 Correct 44 ms 28664 KB Correct.
26 Correct 45 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 25 ms 26240 KB Correct.
5 Correct 24 ms 26368 KB Correct.
6 Correct 25 ms 26240 KB Correct.
7 Correct 24 ms 26240 KB Correct.
8 Correct 24 ms 26240 KB Correct.
9 Correct 24 ms 26240 KB Correct.
10 Correct 24 ms 26240 KB Correct.
11 Correct 24 ms 26240 KB Correct.
12 Correct 23 ms 26368 KB Correct.
13 Correct 25 ms 26240 KB Correct.
14 Correct 24 ms 26240 KB Correct.
15 Correct 25 ms 26240 KB Correct.
16 Correct 27 ms 26240 KB Correct.
17 Correct 25 ms 26240 KB Correct.
18 Correct 24 ms 26368 KB Correct.
19 Correct 28 ms 26360 KB Correct.
20 Correct 24 ms 26240 KB Correct.
21 Correct 24 ms 26240 KB Correct.
22 Correct 25 ms 26240 KB Correct.
23 Correct 24 ms 26240 KB Correct.
24 Correct 26 ms 28032 KB Correct.
25 Correct 25 ms 27136 KB Correct.
26 Correct 30 ms 27776 KB Correct.
27 Correct 27 ms 27008 KB Correct.
28 Correct 28 ms 27008 KB Correct.
29 Correct 26 ms 26624 KB Correct.
30 Correct 27 ms 26624 KB Correct.
31 Correct 30 ms 27136 KB Correct.
32 Correct 28 ms 28672 KB Correct.
33 Correct 44 ms 28544 KB Correct.
34 Correct 44 ms 28544 KB Correct.
35 Correct 44 ms 28664 KB Correct.
36 Correct 46 ms 28544 KB Correct.
37 Correct 46 ms 28544 KB Correct.
38 Correct 45 ms 28664 KB Correct.
39 Correct 43 ms 28672 KB Correct.
40 Correct 41 ms 28664 KB Correct.
41 Correct 38 ms 28672 KB Correct.
42 Correct 45 ms 28664 KB Correct.
43 Correct 36 ms 28664 KB Correct.
44 Correct 43 ms 28664 KB Correct.
45 Correct 44 ms 28664 KB Correct.
46 Correct 45 ms 28544 KB Correct.
47 Correct 35 ms 28672 KB Correct.
48 Correct 44 ms 28664 KB Correct.
49 Correct 45 ms 28544 KB Correct.
50 Correct 903 ms 41712 KB Correct.
51 Execution timed out 10068 ms 44172 KB Time limit exceeded
52 Halted 0 ms 0 KB -