Submission #949800

#	Time	Username	Problem	Language	Result	Execution time	Memory
949800		jerzyk	Sandwich (JOI16_sandwich)	C++17	35 / 100	8051 ms	40700 KiB

sandwich

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#pragma GCC optimize("Ofast","unroll-loops")
#pragma GCC target("popcnt")

#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
using namespace __gnu_pbds;
using namespace std;
#define pb push_back
#define st first
#define nd second
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
const ll I = 1000LL * 1000LL * 1000LL * 1000LL * 1000LL * 1000LL;
const ll M = 1000LL * 1000LL * 1000LL + 7LL;
const int N = 400 + 7;
int n, m; 
bitset<N * N * 2> vis;
bool nor[N * N * 2]; 
int il = 0;
int cnt[2 * N * N];
vector<int> ed[2 * N * N], red[2 * N * N];
string s[N];
int answer[N][N];
queue<int> q;
int ben[2 * N * N];

inline void TSort()
{
    int v;
    queue<int> q;
    int nm = n * m * 2;
    for(int i = 1; i <= nm; ++i)
        for(int j = 0; j < (int)ed[i].size(); ++j)
            red[ed[i][j]].pb(i);
    for(int i = 1; i <= nm; ++i)
        for(int j = 0; j < (int)red[i].size(); ++j)
            ++cnt[red[i][j]];
    for(int i = 1; i <= nm; ++i)
        if(cnt[i] == 0)
            q.push(i);
    while(q.size() > 0)
    {
        v = q.front();
        q.pop();
        nor[v] = true;
        for(int i = 0; i < (int)red[v].size(); ++i)
        {
            --cnt[red[v][i]];
            if(cnt[red[v][i]] == 0)
                q.push(red[v][i]);
        }
    }
}

inline void Clean()
{
    il = 0;
    vis.reset();
}

void DFS(int s)
{
    int v;
    if(vis[s]) return;
    q.push(s);
    vis[s] = 1;
    while(q.size() > 0)
    {
        v = q.front(); q.pop();
        ++il;
        for(int i = 0; i < (int)ed[v].size(); ++i)
            if(!vis[ed[v][i]])
            {
                vis[ed[v][i]] = 1;
                q.push(ed[v][i]);
            }
    }
}

inline int F(int i, int j)
{
    if(i < 1 || i > n || j < 1 || j > m) return 0;
    return j + (i - 1) * m;
}

void DoE(int i, int j)
{
    int a = F(i, j), u = F(i - 1, j), d = F(i + 1, j), l = F(i, j - 1), r = F(i, j + 1);
    int a2 = a + n * m;
    if(d != 0) d += n * m;
    if(l != 0 && s[i][j - 1] == 'N') l += n * m;
    if(r != 0 && s[i][j + 1] == 'Z') r += n * m;

    if(u != 0)
        ed[a].pb(u);
    if(d != 0)
        ed[a2].pb(d);

    if(l != 0)
    {
        if(s[i][j] == 'Z')
            ed[a].pb(l);
        else
            ed[a2].pb(l);
    }
    if(r != 0)
    {
        if(s[i][j] == 'Z')
            ed[a2].pb(r);
        else
            ed[a].pb(r);
    }
}

void Solve()
{
    cin >> n >> m;
    for(int i = 1; i <= n; ++i)
    {
        cin >> s[i];
        s[i] = "#" + s[i] + "#";
        for(int j = 1; j <= m; ++j)
            answer[i][j] = -1;
    }
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= m; ++j)
            DoE(i, j);

    TSort();

    for(int j = 1; j <= m; ++j)
    {
        for(int i = 1; i <= n; ++i)
        {
            int a = F(i, j);
            if(!nor[a])
                break;
            DFS(a);
            if(answer[i][j] == -1)
                answer[i][j] = il * 2;
            else
                answer[i][j] = min(answer[i][j], il * 2);
        }
        if(nor[F(1, j)])
            Clean();
        for(int i = n; i >= 1; --i)
        {
            int a = F(i, j) + n * m;
            if(!nor[a])
                break;
            DFS(a);

            if(answer[i][j] == -1)
                answer[i][j] = il * 2;
            else
                answer[i][j] = min(answer[i][j], il * 2);
        }
        if(nor[F(n, j) + n * m])
            Clean();
    }

    for(int i = 1; i <= n; ++i)
    {
        for(int j = 1; j <= m; ++j)
            cout << answer[i][j] << " ";
        cout << "\n";
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    //int t; cin >> t;
    //while(t--)
        Solve();

    return 0;
}

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