Submission #238657

#	Time	Username	Problem	Language	Result	Execution time	Memory
238657		SamAnd	Skandi (COCI20_skandi)	C++17	110 / 110	1926 ms	35568 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define m_p make_pair
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define fi first
#define se second
typedef long long ll;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
mt19937 rnf(2106);
const int N = 1003;

int n, m;
char a[N][N];

vector<int> g[N * N];

int ul[N][N], uu[N][N];

int f(int i, int j)
{
    return i * m + j;
}

int u[N * N];

bool c[N * N];
vector<int> v;
bool dfs(int x)
{
    if (c[x])
        return false;
    c[x] = true;
    v.push_back(x);
    for (int i = 0; i < g[x].size(); ++i)
    {
        int h = g[x][i];
        if (u[h] == -1)
        {
            u[h] = x;
            return true;
        }
        else if (dfs(u[h]))
        {
            u[h] = x;
            return true;
        }
    }
    return false;
}

bool cc[N * N];
void dfs1(int x)
{
    c[x] = true;
    for (int i = 0; i < g[x].size(); ++i)
    {
        int h = g[x][i];
        if (!c[h])
            dfs1(h);
    }
}

void solv()
{
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; ++i)
    {
        scanf(" %s", a[i]);
    }
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < m; ++j)
        {
            if (a[i][j] == '1')
                ul[i][j] = j;
            else
                ul[i][j] = ul[i][j - 1];
        }
    }
    for (int j = 0; j < m; ++j)
    {
        for (int i = 0; i < n; ++i)
        {
            if (a[i][j] == '1')
                uu[i][j] = i;
            else
                uu[i][j] = uu[i - 1][j];
        }
    }
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < m; ++j)
        {
            if (a[i][j] == '0')
            {
                g[f(i, ul[i][j])].push_back(f(uu[i][j], j));
            }
        }
    }
    for (int i = 0; i < n * m; ++i)
        u[i] = -1;
    for (int i = 0; i < n * m; ++i)
    {
        dfs(i);
        for (int j = 0; j < v.size(); ++j)
            c[v[j]] = false;
        v.clear();
    }
    for (int i = 0; i < n * m; ++i)
        g[i].clear();
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < m; ++j)
        {
            if (a[i][j] == '0')
            {
                if (u[f(uu[i][j], j)] == f(i, ul[i][j]))
                    g[f(uu[i][j], j) + n * m].push_back(f(i, ul[i][j]));
                else
                    g[f(i, ul[i][j])].push_back(f(uu[i][j], j) + n * m);
            }
        }
    }
    for (int i = 0; i < n * m; ++i)
    {
        if (u[i] != -1)
            cc[u[i]] = true;
    }
    for (int i = 0; i < n * m; ++i)
    {
        if (!cc[i])
            dfs1(i);
    }
    vector<pair<pair<int, int>, char> > ans;
    for (int i = 0; i < n * m; ++i)
    {
        if (!c[i])
        {
            int x = i / m;
            int y = i % m;
            ans.push_back(m_p(m_p(x + 1, y + 1), 'R'));
        }
    }
    for (int i = n * m; i < 2 * n * m; ++i)
    {
        if (c[i])
        {
            int x = (i - n * m) / m;
            int y = (i - n * m) % m;
            ans.push_back(m_p(m_p(x + 1, y + 1), 'D'));
        }
    }
    printf("%d\n", ans.size());
    for (int i = 0; i < ans.size(); ++i)
    {
        if (ans[i].se == 'R')
            printf("%d %d DESNO\n", ans[i].fi.fi, ans[i].fi.se);
        else
            printf("%d %d DOLJE\n", ans[i].fi.fi, ans[i].fi.se);
    }
}

int main()
{
    #ifdef SOMETHING
    freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    #endif // SOMETHING
    //ios_base::sync_with_stdio(false), cin.tie(0);
    solv();
    return 0;
}

//while ((double)clock() / CLOCKS_PER_SEC <= 0.9){}

Compilation message (stderr)

skandi.cpp: In function 'bool dfs(int)':
skandi.cpp:35:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < g[x].size(); ++i)
                     ~~^~~~~~~~~~~~~
skandi.cpp: In function 'void dfs1(int)':
skandi.cpp:56:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < g[x].size(); ++i)
                     ~~^~~~~~~~~~~~~
skandi.cpp: In function 'void solv()':
skandi.cpp:106:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int j = 0; j < v.size(); ++j)
                         ~~^~~~~~~~~~
skandi.cpp:154:30: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::vector<std::pair<std::pair<int, int>, char> >::size_type {aka long unsigned int}' [-Wformat=]
     printf("%d\n", ans.size());
                    ~~~~~~~~~~^
skandi.cpp:155:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < ans.size(); ++i)
                     ~~^~~~~~~~~~~~
skandi.cpp:66:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &n, &m);
     ~~~~~^~~~~~~~~~~~~~~~
skandi.cpp:69:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf(" %s", a[i]);
         ~~~~~^~~~~~~~~~~~~

• Subtask 1: 18 / 18
• Subtask 2: 32 / 32
• Subtask 3: 60 / 60