Submission #59027

#	Time	Username	Problem	Language	Result	Execution time	Memory
59027		choikiwon	Sandwich (JOI16_sandwich)	C++17	35 / 100	8016 ms	37684 KiB

sandwich

#include<bits/stdc++.h>
using namespace std;

typedef pair<int, int> pii;

const int MN = 402;

int E;
int la[MN * MN * 4], nxt[MN * MN * 4], oppo[MN * MN * 4];
void init() {
    E = 0;
    memset(la, -1, sizeof(la));
}
void add(int u, int v) {
    nxt[E] = la[u];
    la[u] = E;
    oppo[E] = v;
    E++;
}

int N, M;
char G[MN][MN];
vector<int> sadj[MN * MN * 2];
int tin[MN * MN * 2], bck[MN * MN * 2], id[MN * MN * 2], sz[MN * MN * 2], timer, scnt;
stack<int> stk;

inline int f(int r, int c, int t) {
    return r * (2 * M) + c * 2 + t;
}

void dfs(int u) {
    tin[u] = timer++;
    bck[u] = tin[u];
    stk.push(u);

    for(int i = la[u]; i != -1; i = nxt[i]) {
        int v = oppo[i];
        if(tin[v] == -1) {
            dfs(v);
            bck[u] = min(bck[u], bck[v]);
        }
        else if(id[v] == -1) {
            bck[u] = min(bck[u], tin[v]);
        }
    }
    if(bck[u] == tin[u]) {
        while(1) {
            int t = stk.top(); stk.pop();
            id[t] = scnt;
            if(t == u) break;
        }
        scnt++;
    }
}

int del[MN * MN * 2], chk[MN * MN * 2];
queue<int> q;

void scc() {
    memset(tin, -1, sizeof(tin));
    memset(id, -1, sizeof(id));
    for(int i = 0; i < N * M * 2; i++) if(tin[i] == -1) {
        dfs(i);
    }
    for(int i = 0; i < N * M * 2; i++) {
        sz[ id[i] ]++;

        for(int j = la[i]; j != -1; j = nxt[j]) {
            int k = oppo[j];
            if(id[i] == id[k]) continue;
            sadj[ id[i] ].push_back(id[k]);
        }
    }
    for(int i = 0; i < scnt; i++) {
        if(sz[i] > 1) {
            q.push(i);
            del[i] = 1;
        }
    }
    while(!q.empty()) {
        int u = q.front(); q.pop();

        for(int i = 0; i < sadj[u].size(); i++) {
            int v = sadj[u][i];
            if(!del[v]) {
                q.push(v);
                del[v] = 1;
            }
        }
    }
    for(int i = 0; i < N * M * 2; i++) {
        chk[i] = del[ id[i] ];
    }
}

int ans[MN * MN * 2], vis[MN * MN * 2];

int main() {
    scanf("%d %d", &N, &M);

    for(int i = 0; i < N; i++) {
        scanf("\n");
        for(int j = 0; j < M; j++) {
            scanf("%c", &G[i][j]);
        }
    }

    init();
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < M; j++) {
            for(int k = 0; k < 2; k++) {
                if(k) {
                    if(i) {
                        add(f(i - 1, j, k), f(i, j, k));
                    }
                }
                else if(i < N - 1) {
                    add(f(i + 1, j, k), f(i, j, k));
                }
                if(k ^ (G[i][j] == 'N')) {
                    if(j) {
                        add(f(i, j - 1, G[i][j - 1] == 'Z'), f(i, j, k));
                    }
                }
                else if(j < M - 1) {
                    add(f(i, j + 1, G[i][j + 1] == 'N'), f(i, j, k));
                }
            }
        }
    }

    scc();

    for(int i = 0; i < N; i++) {
        memset(vis, 0, sizeof(vis));

        for(int j = 0; j < M; j++) {
            int k = G[i][j] == 'N';
            if(chk[ f(i, j, k) ]) continue;

            q.push(f(i, j, k));
            ans[ f(i, j, k) ] += M - j;
            vis[ f(i, j, k) ] = 1;
            while(!q.empty()) {
                int u = q.front(); q.pop();

                for(int x = la[u]; x != -1; x = nxt[x]) {
                    int v = oppo[x];
                    if(!chk[v] && !vis[v]) {
                        q.push(v);
                        ans[v] += M - j;
                        vis[v] = 1;
                    }
                }
            }
        }
    }
    for(int i = 0; i < N; i++) {
        memset(vis, 0, sizeof(vis));

        for(int j = M - 1; j >= 0; j--) {
            int k = G[i][j] == 'Z';
            if(chk[ f(i, j, k) ]) continue;

            q.push(f(i, j, k));
            ans[ f(i, j, k) ] += j + 1;
            vis[ f(i, j, k) ] = 1;
            while(!q.empty()) {
                int u = q.front(); q.pop();

                for(int x = la[u]; x != -1; x = nxt[x]) {
                    int v = oppo[x];
                    if(!chk[v] && !vis[v]) {
                        q.push(v);
                        ans[v] += j + 1;
                        vis[v] = 1;
                    }
                }
            }
        }
    }

    for(int i = 0; i < N; i++) {
        for(int j = 0; j < M; j++) {
            if(chk[ f(i, j, 0) ] && chk[ f(i, j, 1) ]) printf("-1 ");
            else if(chk[ f(i, j, 0) ]) printf("%d ", 2 * ans[ f(i, j, 1) ]);
            else if(chk[ f(i, j, 1) ]) printf("%d ", 2 * ans[ f(i, j, 0) ]);
            else printf("%d ", 2 * min(ans[ f(i, j, 0) ], ans[ f(i, j, 1) ]));
        }
        printf("\n");
    }
}

Compilation message (stderr)

sandwich.cpp: In function 'void scc()':
sandwich.cpp:83:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i = 0; i < sadj[u].size(); i++) {
                        ~~^~~~~~~~~~~~~~~~
sandwich.cpp: In function 'int main()':
sandwich.cpp:99:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &N, &M);
     ~~~~~^~~~~~~~~~~~~~~~~
sandwich.cpp:102:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("\n");
         ~~~~~^~~~~~
sandwich.cpp:104:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%c", &G[i][j]);
             ~~~~~^~~~~~~~~~~~~~~~

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