oj.uz

Submission #220694

# Submission time Handle Problem Language Result Execution time Memory
220694 2020-04-08T11:53:37 Z Vimmer Skandi (COCI20_skandi) C++14
50 / 110
 1041 ms 64156 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 1000005
#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 43 ms 52224 KB Correct.
2 Correct 44 ms 52224 KB Correct.
3 Correct 44 ms 52216 KB Correct.
4 Correct 48 ms 52224 KB Correct.
5 Correct 44 ms 52224 KB Correct.
6 Correct 44 ms 52216 KB Correct.
7 Correct 46 ms 52224 KB Correct.
8 Correct 43 ms 52224 KB Correct.
9 Correct 44 ms 52216 KB Correct.
10 Correct 43 ms 52216 KB Correct.
11 Correct 52 ms 52224 KB Correct.
12 Correct 43 ms 52224 KB Correct.
13 Correct 47 ms 52224 KB Correct.
14 Correct 57 ms 52216 KB Correct.
15 Correct 49 ms 52216 KB Correct.
16 Correct 42 ms 52224 KB Correct.
17 Correct 44 ms 52216 KB Correct.
18 Correct 43 ms 52224 KB Correct.
19 Correct 44 ms 52224 KB Correct.
20 Correct 46 ms 52224 KB Correct.
21 Correct 43 ms 52224 KB Correct.
22 Correct 42 ms 52224 KB Correct.
23 Correct 44 ms 52224 KB Correct.

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 54016 KB Correct.
2 Correct 52 ms 53112 KB Correct.
3 Correct 56 ms 53752 KB Correct.
4 Correct 48 ms 52984 KB Correct.
5 Correct 49 ms 52864 KB Correct.
6 Correct 49 ms 52608 KB Correct.
7 Correct 49 ms 52608 KB Correct.
8 Correct 61 ms 52984 KB Correct.
9 Correct 48 ms 54656 KB Correct.
10 Correct 80 ms 54528 KB Correct.
11 Correct 97 ms 54464 KB Correct.
12 Correct 82 ms 54528 KB Correct.
13 Correct 87 ms 54520 KB Correct.
14 Correct 80 ms 54520 KB Correct.
15 Correct 79 ms 54648 KB Correct.
16 Correct 75 ms 54528 KB Correct.
17 Correct 72 ms 54648 KB Correct.
18 Correct 70 ms 54520 KB Correct.
19 Correct 84 ms 54528 KB Correct.
20 Correct 67 ms 54652 KB Correct.
21 Correct 76 ms 54528 KB Correct.
22 Correct 79 ms 54528 KB Correct.
23 Correct 86 ms 54528 KB Correct.
24 Correct 61 ms 54528 KB Correct.
25 Correct 75 ms 54624 KB Correct.
26 Correct 82 ms 54520 KB Correct.

Subtask #3
0.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 52224 KB Correct.
2 Correct 44 ms 52224 KB Correct.
3 Correct 44 ms 52216 KB Correct.
4 Correct 48 ms 52224 KB Correct.
5 Correct 44 ms 52224 KB Correct.
6 Correct 44 ms 52216 KB Correct.
7 Correct 46 ms 52224 KB Correct.
8 Correct 43 ms 52224 KB Correct.
9 Correct 44 ms 52216 KB Correct.
10 Correct 43 ms 52216 KB Correct.
11 Correct 52 ms 52224 KB Correct.
12 Correct 43 ms 52224 KB Correct.
13 Correct 47 ms 52224 KB Correct.
14 Correct 57 ms 52216 KB Correct.
15 Correct 49 ms 52216 KB Correct.
16 Correct 42 ms 52224 KB Correct.
17 Correct 44 ms 52216 KB Correct.
18 Correct 43 ms 52224 KB Correct.
19 Correct 44 ms 52224 KB Correct.
20 Correct 46 ms 52224 KB Correct.
21 Correct 43 ms 52224 KB Correct.
22 Correct 42 ms 52224 KB Correct.
23 Correct 44 ms 52224 KB Correct.
24 Correct 51 ms 54016 KB Correct.
25 Correct 52 ms 53112 KB Correct.
26 Correct 56 ms 53752 KB Correct.
27 Correct 48 ms 52984 KB Correct.
28 Correct 49 ms 52864 KB Correct.
29 Correct 49 ms 52608 KB Correct.
30 Correct 49 ms 52608 KB Correct.
31 Correct 61 ms 52984 KB Correct.
32 Correct 48 ms 54656 KB Correct.
33 Correct 80 ms 54528 KB Correct.
34 Correct 97 ms 54464 KB Correct.
35 Correct 82 ms 54528 KB Correct.
36 Correct 87 ms 54520 KB Correct.
37 Correct 80 ms 54520 KB Correct.
38 Correct 79 ms 54648 KB Correct.
39 Correct 75 ms 54528 KB Correct.
40 Correct 72 ms 54648 KB Correct.
41 Correct 70 ms 54520 KB Correct.
42 Correct 84 ms 54528 KB Correct.
43 Correct 67 ms 54652 KB Correct.
44 Correct 76 ms 54528 KB Correct.
45 Correct 79 ms 54528 KB Correct.
46 Correct 86 ms 54528 KB Correct.
47 Correct 61 ms 54528 KB Correct.
48 Correct 75 ms 54624 KB Correct.
49 Correct 82 ms 54520 KB Correct.
50 Incorrect 1041 ms 64156 KB First line is not correct.
51 Halted 0 ms 0 KB -