oj.uz

Submission #530981

# Submission time Handle Problem Language Result Execution time Memory
530981 2022-02-27T08:59:30 Z Tenis0206 Skandi (COCI20_skandi) C++11
110 / 110
 180 ms 14876 KB 
#include <bits/stdc++.h>

using namespace std;

int n,m;
char c[505][505];

int sus[505][505], stg[505][505];

vector<int> G[250005];

bool sel[250005], st[250005], dr[250005];

int l[250005],r[250005];

bool cupleaza(int nod)
{
    sel[nod] = true;
    for(auto it : G[nod])
    {
        if(!r[it])
        {
            r[it] = nod;
            l[nod] = it;
            return true;
        }
    }
    for(auto it : G[nod])
    {
        if(!sel[r[it]] && cupleaza(r[it]))
        {
            r[it] = nod;
            l[nod] = it;
            return true;
        }
    }
    return false;
}

void dfs(int nod)
{
    for(auto it : G[nod])
    {
        if(!dr[it])
        {
            dr[it] = true;
            st[r[it]] = false;
            dfs(r[it]);
        }
    }
}

pair<int,int> decod(int val)
{
    int l = (val - 1) / m + 1;
    int c = (val - 1) % m + 1;
    return {l,c};
}

string output[2];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    output[0] = "DESNO";
    output[1] = "DOLJE";
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            cin>>c[i][j];
            if(c[i][j]=='1')
            {
                sus[i][j] = (i - 1) * m + j;
                stg[i][j] = (i - 1) * m + j;
            }
            else
            {
                sus[i][j] = sus[i-1][j];
                stg[i][j] = stg[i][j-1];
            }
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(c[i][j]=='1')
            {
                continue;
            }
            G[stg[i][j]].push_back(sus[i][j]);
        }
    }
    bool done = false;
    while(!done)
    {
        done = true;
        memset(sel,0,sizeof(sel));
        for(int i=1;i<=n*m;i++)
        {
            if(!l[i] && !sel[i] && cupleaza(i))
            {
                done = false;
            }
        }
    }
    for(int i=1;i<=n*m;i++)
    {
        if(l[i])
        {
            st[i] = true;
        }
    }
    for(int i=1;i<=n*m;i++)
    {
        if(!l[i])
        {
            dfs(i);
        }
    }
    vector<pair<pair<int,int>,int>> rez;
    for(int i=1;i<=n*m;i++)
    {
        if(st[i])
        {
            rez.push_back({decod(i),0});
        }
        if(dr[i])
        {
            rez.push_back({decod(i),1});
        }
    }
    cout<<rez.size()<<'\n';
    for(auto it : rez)
    {
        cout<<it.first.first<<' '<<it.first.second<<' '<<output[it.second]<<'\n';
    }
    return 0;
}

Subtask #1
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6340 KB Correct.
2 Correct 3 ms 6476 KB Correct.
3 Correct 4 ms 6452 KB Correct.
4 Correct 3 ms 6476 KB Correct.
5 Correct 4 ms 6348 KB Correct.
6 Correct 3 ms 6476 KB Correct.
7 Correct 5 ms 6388 KB Correct.
8 Correct 3 ms 6476 KB Correct.
9 Correct 3 ms 6476 KB Correct.
10 Correct 3 ms 6476 KB Correct.
11 Correct 4 ms 6476 KB Correct.
12 Correct 4 ms 6476 KB Correct.
13 Correct 3 ms 6476 KB Correct.
14 Correct 3 ms 6476 KB Correct.
15 Correct 3 ms 6476 KB Correct.
16 Correct 3 ms 6476 KB Correct.
17 Correct 3 ms 6456 KB Correct.
18 Correct 3 ms 6476 KB Correct.
19 Correct 3 ms 6476 KB Correct.
20 Correct 4 ms 6476 KB Correct.
21 Correct 4 ms 6476 KB Correct.
22 Correct 3 ms 6452 KB Correct.
23 Correct 3 ms 6476 KB Correct.

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8376 KB Correct.
2 Correct 4 ms 7244 KB Correct.
3 Correct 4 ms 8012 KB Correct.
4 Correct 4 ms 7224 KB Correct.
5 Correct 4 ms 7092 KB Correct.
6 Correct 4 ms 6860 KB Correct.
7 Correct 4 ms 6796 KB Correct.
8 Correct 4 ms 7296 KB Correct.
9 Correct 6 ms 8744 KB Correct.
10 Correct 5 ms 8780 KB Correct.
11 Correct 7 ms 8768 KB Correct.
12 Correct 6 ms 8736 KB Correct.
13 Correct 5 ms 8780 KB Correct.
14 Correct 6 ms 8780 KB Correct.
15 Correct 6 ms 8780 KB Correct.
16 Correct 5 ms 8768 KB Correct.
17 Correct 5 ms 8780 KB Correct.
18 Correct 6 ms 8760 KB Correct.
19 Correct 5 ms 8760 KB Correct.
20 Correct 5 ms 8780 KB Correct.
21 Correct 5 ms 8768 KB Correct.
22 Correct 6 ms 8760 KB Correct.
23 Correct 5 ms 8764 KB Correct.
24 Correct 6 ms 8700 KB Correct.
25 Correct 5 ms 8780 KB Correct.
26 Correct 5 ms 8780 KB Correct.

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6340 KB Correct.
2 Correct 3 ms 6476 KB Correct.
3 Correct 4 ms 6452 KB Correct.
4 Correct 3 ms 6476 KB Correct.
5 Correct 4 ms 6348 KB Correct.
6 Correct 3 ms 6476 KB Correct.
7 Correct 5 ms 6388 KB Correct.
8 Correct 3 ms 6476 KB Correct.
9 Correct 3 ms 6476 KB Correct.
10 Correct 3 ms 6476 KB Correct.
11 Correct 4 ms 6476 KB Correct.
12 Correct 4 ms 6476 KB Correct.
13 Correct 3 ms 6476 KB Correct.
14 Correct 3 ms 6476 KB Correct.
15 Correct 3 ms 6476 KB Correct.
16 Correct 3 ms 6476 KB Correct.
17 Correct 3 ms 6456 KB Correct.
18 Correct 3 ms 6476 KB Correct.
19 Correct 3 ms 6476 KB Correct.
20 Correct 4 ms 6476 KB Correct.
21 Correct 4 ms 6476 KB Correct.
22 Correct 3 ms 6452 KB Correct.
23 Correct 3 ms 6476 KB Correct.
24 Correct 4 ms 8376 KB Correct.
25 Correct 4 ms 7244 KB Correct.
26 Correct 4 ms 8012 KB Correct.
27 Correct 4 ms 7224 KB Correct.
28 Correct 4 ms 7092 KB Correct.
29 Correct 4 ms 6860 KB Correct.
30 Correct 4 ms 6796 KB Correct.
31 Correct 4 ms 7296 KB Correct.
32 Correct 6 ms 8744 KB Correct.
33 Correct 5 ms 8780 KB Correct.
34 Correct 7 ms 8768 KB Correct.
35 Correct 6 ms 8736 KB Correct.
36 Correct 5 ms 8780 KB Correct.
37 Correct 6 ms 8780 KB Correct.
38 Correct 6 ms 8780 KB Correct.
39 Correct 5 ms 8768 KB Correct.
40 Correct 5 ms 8780 KB Correct.
41 Correct 6 ms 8760 KB Correct.
42 Correct 5 ms 8760 KB Correct.
43 Correct 5 ms 8780 KB Correct.
44 Correct 5 ms 8768 KB Correct.
45 Correct 6 ms 8760 KB Correct.
46 Correct 5 ms 8764 KB Correct.
47 Correct 6 ms 8700 KB Correct.
48 Correct 5 ms 8780 KB Correct.
49 Correct 5 ms 8780 KB Correct.
50 Correct 32 ms 13616 KB Correct.
51 Correct 141 ms 12596 KB Correct.
52 Correct 41 ms 14268 KB Correct.
53 Correct 32 ms 13820 KB Correct.
54 Correct 35 ms 13244 KB Correct.
55 Correct 38 ms 14336 KB Correct.
56 Correct 35 ms 14188 KB Correct.
57 Correct 33 ms 14052 KB Correct.
58 Correct 180 ms 12664 KB Correct.
59 Correct 31 ms 13232 KB Correct.
60 Correct 35 ms 14016 KB Correct.
61 Correct 36 ms 13372 KB Correct.
62 Correct 36 ms 13888 KB Correct.
63 Correct 36 ms 14120 KB Correct.
64 Correct 16 ms 11952 KB Correct.
65 Correct 35 ms 14064 KB Correct.
66 Correct 40 ms 13500 KB Correct.
67 Correct 43 ms 14124 KB Correct.
68 Correct 40 ms 14440 KB Correct.
69 Correct 35 ms 13832 KB Correct.
70 Correct 35 ms 13988 KB Correct.
71 Correct 51 ms 14684 KB Correct.
72 Correct 38 ms 14596 KB Correct.
73 Correct 43 ms 14780 KB Correct.
74 Correct 45 ms 14608 KB Correct.
75 Correct 43 ms 14876 KB Correct.