oj.uz

답안 #220714

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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 -