oj.uz

Submission #220711

# Submission time Handle Problem Language Result Execution time Memory
220711 2020-04-08T12:44:06 Z Vimmer Skandi (COCI20_skandi) C++14
50 / 110
 10000 ms 44416 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) 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 25 ms 26368 KB Correct.
4 Correct 24 ms 26240 KB Correct.
5 Correct 24 ms 26240 KB Correct.
6 Correct 27 ms 26496 KB Correct.
7 Correct 25 ms 26240 KB Correct.
8 Correct 24 ms 26240 KB Correct.
9 Correct 23 ms 26240 KB Correct.
10 Correct 27 ms 26240 KB Correct.
11 Correct 24 ms 26240 KB Correct.
12 Correct 25 ms 26368 KB Correct.
13 Correct 24 ms 26240 KB Correct.
14 Correct 30 ms 26240 KB Correct.
15 Correct 27 ms 26368 KB Correct.
16 Correct 24 ms 26368 KB Correct.
17 Correct 24 ms 26240 KB Correct.
18 Correct 24 ms 26368 KB Correct.
19 Correct 23 ms 26240 KB Correct.
20 Correct 24 ms 26240 KB Correct.
21 Correct 24 ms 26240 KB Correct.
22 Correct 25 ms 26368 KB Correct.
23 Correct 24 ms 26240 KB Correct.

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 28040 KB Correct.
2 Correct 25 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 26624 KB Correct.
7 Correct 28 ms 26624 KB Correct.
8 Correct 31 ms 27136 KB Correct.
9 Correct 28 ms 28672 KB Correct.
10 Correct 46 ms 28544 KB Correct.
11 Correct 45 ms 28664 KB Correct.
12 Correct 41 ms 28664 KB Correct.
13 Correct 45 ms 28544 KB Correct.
14 Correct 45 ms 28544 KB Correct.
15 Correct 44 ms 28664 KB Correct.
16 Correct 44 ms 28664 KB Correct.
17 Correct 42 ms 28664 KB Correct.
18 Correct 38 ms 28664 KB Correct.
19 Correct 43 ms 28664 KB Correct.
20 Correct 41 ms 28672 KB Correct.
21 Correct 44 ms 28664 KB Correct.
22 Correct 45 ms 28644 KB Correct.
23 Correct 44 ms 28664 KB Correct.
24 Correct 34 ms 28672 KB Correct.
25 Correct 43 ms 28664 KB Correct.
26 Correct 44 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 25 ms 26368 KB Correct.
4 Correct 24 ms 26240 KB Correct.
5 Correct 24 ms 26240 KB Correct.
6 Correct 27 ms 26496 KB Correct.
7 Correct 25 ms 26240 KB Correct.
8 Correct 24 ms 26240 KB Correct.
9 Correct 23 ms 26240 KB Correct.
10 Correct 27 ms 26240 KB Correct.
11 Correct 24 ms 26240 KB Correct.
12 Correct 25 ms 26368 KB Correct.
13 Correct 24 ms 26240 KB Correct.
14 Correct 30 ms 26240 KB Correct.
15 Correct 27 ms 26368 KB Correct.
16 Correct 24 ms 26368 KB Correct.
17 Correct 24 ms 26240 KB Correct.
18 Correct 24 ms 26368 KB Correct.
19 Correct 23 ms 26240 KB Correct.
20 Correct 24 ms 26240 KB Correct.
21 Correct 24 ms 26240 KB Correct.
22 Correct 25 ms 26368 KB Correct.
23 Correct 24 ms 26240 KB Correct.
24 Correct 29 ms 28040 KB Correct.
25 Correct 25 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 26624 KB Correct.
30 Correct 28 ms 26624 KB Correct.
31 Correct 31 ms 27136 KB Correct.
32 Correct 28 ms 28672 KB Correct.
33 Correct 46 ms 28544 KB Correct.
34 Correct 45 ms 28664 KB Correct.
35 Correct 41 ms 28664 KB Correct.
36 Correct 45 ms 28544 KB Correct.
37 Correct 45 ms 28544 KB Correct.
38 Correct 44 ms 28664 KB Correct.
39 Correct 44 ms 28664 KB Correct.
40 Correct 42 ms 28664 KB Correct.
41 Correct 38 ms 28664 KB Correct.
42 Correct 43 ms 28664 KB Correct.
43 Correct 41 ms 28672 KB Correct.
44 Correct 44 ms 28664 KB Correct.
45 Correct 45 ms 28644 KB Correct.
46 Correct 44 ms 28664 KB Correct.
47 Correct 34 ms 28672 KB Correct.
48 Correct 43 ms 28664 KB Correct.
49 Correct 44 ms 28544 KB Correct.
50 Correct 900 ms 41712 KB Correct.
51 Execution timed out 10053 ms 44416 KB Time limit exceeded
52 Halted 0 ms 0 KB -