oj.uz

Submission #220693

# Submission time Handle Problem Language Result Execution time Memory
220693 2020-04-08T11:52:56 Z Vimmer Skandi (COCI20_skandi) C++14
50 / 110
 573 ms 38388 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[505 * 505][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++;}

    int koler = 0;

    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;
}

Compilation message

skandi.cpp: In function 'int main()':
skandi.cpp:84:9: warning: unused variable 'koler' [-Wunused-variable]
     int koler = 0;
         ^~~~~

Subtask #1
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 26240 KB Correct.
2 Correct 25 ms 26368 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 23 ms 26240 KB Correct.
7 Correct 24 ms 26368 KB Correct.
8 Correct 24 ms 26368 KB Correct.
9 Correct 25 ms 26240 KB Correct.
10 Correct 24 ms 26368 KB Correct.
11 Correct 23 ms 26368 KB Correct.
12 Correct 24 ms 26240 KB Correct.
13 Correct 24 ms 26240 KB Correct.
14 Correct 24 ms 26240 KB Correct.
15 Correct 24 ms 26368 KB Correct.
16 Correct 24 ms 26368 KB Correct.
17 Correct 27 ms 26368 KB Correct.
18 Correct 24 ms 26368 KB Correct.
19 Correct 24 ms 26240 KB Correct.
20 Correct 24 ms 26240 KB Correct.
21 Correct 25 ms 26240 KB Correct.
22 Correct 25 ms 26368 KB Correct.
23 Correct 24 ms 26368 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 29 ms 27776 KB Correct.
4 Correct 27 ms 27008 KB Correct.
5 Correct 30 ms 27008 KB Correct.
6 Correct 26 ms 26752 KB Correct.
7 Correct 26 ms 26624 KB Correct.
8 Correct 30 ms 27136 KB Correct.
9 Correct 27 ms 28672 KB Correct.
10 Correct 46 ms 28664 KB Correct.
11 Correct 45 ms 28544 KB Correct.
12 Correct 42 ms 28664 KB Correct.
13 Correct 44 ms 28664 KB Correct.
14 Correct 44 ms 28544 KB Correct.
15 Correct 42 ms 28664 KB Correct.
16 Correct 43 ms 28664 KB Correct.
17 Correct 40 ms 28664 KB Correct.
18 Correct 40 ms 28664 KB Correct.
19 Correct 44 ms 28664 KB Correct.
20 Correct 38 ms 28672 KB Correct.
21 Correct 43 ms 28664 KB Correct.
22 Correct 50 ms 28664 KB Correct.
23 Correct 45 ms 28640 KB Correct.
24 Correct 33 ms 28672 KB Correct.
25 Correct 44 ms 28664 KB Correct.
26 Correct 46 ms 28544 KB Correct.

Subtask #3
0.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 26240 KB Correct.
2 Correct 25 ms 26368 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 23 ms 26240 KB Correct.
7 Correct 24 ms 26368 KB Correct.
8 Correct 24 ms 26368 KB Correct.
9 Correct 25 ms 26240 KB Correct.
10 Correct 24 ms 26368 KB Correct.
11 Correct 23 ms 26368 KB Correct.
12 Correct 24 ms 26240 KB Correct.
13 Correct 24 ms 26240 KB Correct.
14 Correct 24 ms 26240 KB Correct.
15 Correct 24 ms 26368 KB Correct.
16 Correct 24 ms 26368 KB Correct.
17 Correct 27 ms 26368 KB Correct.
18 Correct 24 ms 26368 KB Correct.
19 Correct 24 ms 26240 KB Correct.
20 Correct 24 ms 26240 KB Correct.
21 Correct 25 ms 26240 KB Correct.
22 Correct 25 ms 26368 KB Correct.
23 Correct 24 ms 26368 KB Correct.
24 Correct 26 ms 28032 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 30 ms 27008 KB Correct.
29 Correct 26 ms 26752 KB Correct.
30 Correct 26 ms 26624 KB Correct.
31 Correct 30 ms 27136 KB Correct.
32 Correct 27 ms 28672 KB Correct.
33 Correct 46 ms 28664 KB Correct.
34 Correct 45 ms 28544 KB Correct.
35 Correct 42 ms 28664 KB Correct.
36 Correct 44 ms 28664 KB Correct.
37 Correct 44 ms 28544 KB Correct.
38 Correct 42 ms 28664 KB Correct.
39 Correct 43 ms 28664 KB Correct.
40 Correct 40 ms 28664 KB Correct.
41 Correct 40 ms 28664 KB Correct.
42 Correct 44 ms 28664 KB Correct.
43 Correct 38 ms 28672 KB Correct.
44 Correct 43 ms 28664 KB Correct.
45 Correct 50 ms 28664 KB Correct.
46 Correct 45 ms 28640 KB Correct.
47 Correct 33 ms 28672 KB Correct.
48 Correct 44 ms 28664 KB Correct.
49 Correct 46 ms 28544 KB Correct.
50 Incorrect 573 ms 38388 KB First line is not correct.
51 Halted 0 ms 0 KB -