Submission #286304

#	Time	Username	Problem	Language	Result	Execution time	Memory
286304		Alexa2001	Sandwich (JOI16_sandwich)	C++17	35 / 100	8032 ms	45144 KiB

sandwich

#include <bits/stdc++.h>

using namespace std;

const int inf = 1e9;
const int Nmax = 404;

int cells, n, m;


char a[Nmax][Nmax];
int ans[Nmax][Nmax], pending[Nmax];
bool Upper[Nmax][Nmax], Lower[Nmax][Nmax];

vector<pair<int,int>> v;
vector<pair<int,int>> edges[Nmax];
vector<int> to[2 * Nmax * Nmax];


void add_upper(int x, int y, int prv);


int code(int x, int y, int lw)
{
    return (x-1) * m + y + lw * n * m;
}

void add_lower(int x, int y, int prv = 0)
{
    if(prv) v.push_back({prv, code(x, y, 0)});

    if(Lower[x][y]) return;
    Lower[x][y] = 1;

    ++cells;

    if(a[x][y] == 'N') /// adaug dreapta
    {
        if(a[x][y+1] == 'N')
            add_lower(x, y+1, code(x, y, 0));
        else if(a[x][y+1] == 'Z')
            add_upper(x, y+1, code(x, y, 0));

        if(x - 1 >= 1)
            add_lower(x-1, y, code(x, y, 0));
    }
    else
    {
        if(a[x][y-1] == 'N')
            add_upper(x, y-1, code(x, y, 0));
        else if(a[x][y-1] == 'Z')
            add_lower(x, y-1, code(x, y, 0));

        if(x - 1 >= 1)
            add_lower(x-1, y, code(x, y, 0));
    }
}

void add_upper(int x, int y, int prv = 0)
{
    if(prv) v.push_back({prv, code(x, y, 1)});

    if(Upper[x][y]) return;
    Upper[x][y] = 1;

    ++cells;

    if(a[x][y] == 'N') /// adaug dreapta
    {
        if(a[x][y-1] == 'N')
            add_upper(x, y-1, code(x, y, 1));
        else if(a[x][y-1] == 'Z')
            add_lower(x, y-1, code(x, y, 1));

        if(x + 1 <= n)
            add_upper(x+1, y, code(x, y, 1));
    }
    else
    {
        if(a[x][y+1] == 'N')
            add_lower(x, y+1, code(x, y, 1));
        else if(a[x][y+1] == 'Z')
            add_upper(x, y+1, code(x, y, 1));

        if(x + 1 <= n)
            add_upper(x+1, y, code(x, y, 1));
    }
}

int nr, used[2*Nmax*Nmax];
bool bad;

void dfs(int node)
{
    if(used[node]) return;
    used[node] = -1;

    for(auto it : to[node])
        dfs(it);

    used[node] = ++nr;

    for(auto it : to[node])
        if(used[it] == -1) bad = 1;
}


bool cycle(int x, int y)
{
    int i, j;
    for(i=1; i<=2*n*m; ++i)
    {
        to[i].clear();
        used[i] = 0;
    }

    for(i=x; i<=y; ++i)
        for(j=0; j<edges[i].size(); ++j)
            to[edges[i][j].first].push_back(edges[i][j].second);

    nr = 0;
    bad = 0;

    for(i=1; i<=2*n*m; ++i)
        if(!used[i]) dfs(i);

    return bad;
}

void solve1(int c)
{
    int i, j;
    for(i=1; i<=n; ++i)
        for(j=1; j<=m; ++j)
            Lower[i][j] = Upper[i][j] = 0;

    cells = 0;
    bad = 0;

    for(i=1; i<=n; ++i)
    {
        add_lower(i, c);
        pending[i] = cells;
        edges[i] = v;
        v.clear();
    }

    int st, dr, mid;

    st = 1; dr = n;
    while(st <= dr)
    {
        mid = (st + dr) / 2;
        if(!cycle(1, mid)) st = mid + 1;
            else dr = mid-1;
    }

    for(i=1; i<=dr; ++i) ans[i][c] = min(ans[i][c], pending[i]);
}


void solve2(int c)
{
    int i, j;
    for(i=1; i<=n; ++i)
        for(j=1; j<=m; ++j)
            Lower[i][j] = Upper[i][j] = 0;

    cells = 0;
    bad = 0;


    for(i=n; i; --i)
    {
        add_upper(i, c);
        pending[i] = cells;
        edges[i] = v;
        v.clear();
    }


    int st, dr, mid;

    st = 1; dr = n;
    while(st <= dr)
    {
        mid = (st + dr) / 2;
        if(cycle(mid, n)) st = mid + 1;
            else dr = mid-1;
    }

    for(i=st; i<=n; ++i) ans[i][c] = min(ans[i][c], pending[i]);
}


int main()
{
  //  freopen("input", "r", stdin);
    cin.tie(0); cin.sync_with_stdio(false);

    cin >> n >> m;

    int i, j;
    for(i=1; i<=n; ++i) cin >> (a[i] + 1);

    for(i=1; i<=n; ++i)
        for(j=1; j<=m; ++j)
            ans[i][j] = inf;

    for(i=1; i<=m; ++i)
        solve1(i);

    for(i=1; i<=m; ++i)
        solve2(i);

    for(i=1; i<=n; ++i)
        for(j=1; j<=m; ++j)
            cout << (ans[i][j] == inf ? -1 : 2 * ans[i][j]) << " \n"[j==m];

    return 0;
}

Compilation message (stderr)

sandwich.cpp: In function 'bool cycle(int, int)':
sandwich.cpp:118:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  118 |         for(j=0; j<edges[i].size(); ++j)
      |                  ~^~~~~~~~~~~~~~~~

• Subtask 1: 35 / 35
• Subtask 2: 0 / 65