oj.uz

Submission #220714

# Submission time Handle Problem Language Result Execution time Memory
220714 2020-04-08T12:50:54 Z Vimmer Skandi (COCI20_skandi) C++14
18 / 110
 19 ms 16640 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];

vector <int> g[N];


bool mk[N], mkr[N], was[N], bad[505][505];

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] && !bad[v][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]].pb(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) bad[mt[i]][i] = 1;

    for (int i = 0; i < N; i++) if (lft[i] && !was[i] && !mkr[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 17 ms 14592 KB Correct.
2 Correct 15 ms 14592 KB Correct.
3 Correct 15 ms 14592 KB Correct.
4 Correct 15 ms 14592 KB Correct.
5 Correct 15 ms 14592 KB Correct.
6 Correct 15 ms 14592 KB Correct.
7 Correct 15 ms 14592 KB Correct.
8 Correct 16 ms 14592 KB Correct.
9 Correct 16 ms 14592 KB Correct.
10 Correct 16 ms 14592 KB Correct.
11 Correct 17 ms 14592 KB Correct.
12 Correct 15 ms 14592 KB Correct.
13 Correct 15 ms 14592 KB Correct.
14 Correct 15 ms 14592 KB Correct.
15 Correct 15 ms 14592 KB Correct.
16 Correct 16 ms 14592 KB Correct.
17 Correct 15 ms 14592 KB Correct.
18 Correct 15 ms 14592 KB Correct.
19 Correct 15 ms 14592 KB Correct.
20 Correct 15 ms 14592 KB Correct.
21 Correct 16 ms 14592 KB Correct.
22 Correct 15 ms 14592 KB Correct.
23 Correct 15 ms 14592 KB Correct.

Subtask #2
0.0 / 32.0

# Verdict Execution time Memory Grader output
1 Incorrect 19 ms 16640 KB First line is not correct.
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 14592 KB Correct.
2 Correct 15 ms 14592 KB Correct.
3 Correct 15 ms 14592 KB Correct.
4 Correct 15 ms 14592 KB Correct.
5 Correct 15 ms 14592 KB Correct.
6 Correct 15 ms 14592 KB Correct.
7 Correct 15 ms 14592 KB Correct.
8 Correct 16 ms 14592 KB Correct.
9 Correct 16 ms 14592 KB Correct.
10 Correct 16 ms 14592 KB Correct.
11 Correct 17 ms 14592 KB Correct.
12 Correct 15 ms 14592 KB Correct.
13 Correct 15 ms 14592 KB Correct.
14 Correct 15 ms 14592 KB Correct.
15 Correct 15 ms 14592 KB Correct.
16 Correct 16 ms 14592 KB Correct.
17 Correct 15 ms 14592 KB Correct.
18 Correct 15 ms 14592 KB Correct.
19 Correct 15 ms 14592 KB Correct.
20 Correct 15 ms 14592 KB Correct.
21 Correct 16 ms 14592 KB Correct.
22 Correct 15 ms 14592 KB Correct.
23 Correct 15 ms 14592 KB Correct.
24 Incorrect 19 ms 16640 KB First line is not correct.
25 Halted 0 ms 0 KB -