답안 #59039 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
59039	2018-07-20T09:49:34 Z	choikiwon	Sandwich (JOI16_sandwich)	C++17	35 / 100	8000 ms	38956 KB

sandwich

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

typedef pair<int, int> pii;

const int MN = 402;

int E = 1;
int la[MN * MN * 4], nxt[MN * MN * 4], oppo[MN * MN * 4];
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 = 1, scnt = 1;
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; i = nxt[i]) {
        int v = oppo[i];
        if(!tin[v]) {
            dfs(v);
            bck[u] = min(bck[u], bck[v]);
        }
        else if(!id[v]) {
            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++;
    }
}

bool del[MN * MN * 2], chk[MN * MN * 2];
int q[1000010], head, tail;

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

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

        for(int i = 0; i < sadj[u].size(); i++) {
            int v = sadj[u][i];
            if(!del[v]) {
                q[tail++] = 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++) {
        getchar();
        for(int j = 0; j < M; j++) {
            G[i][j] = getchar();
        }
    }

    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();

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

            head = tail = 0;
            q[tail++] = f(i, j, k);
            ans[ f(i, j, k) ] += M - j;
            vis[ f(i, j, k) ] = pos;
            while(head != tail) {
                int u = q[head++];

                for(int x = la[u]; x != 0; x = nxt[x]) {
                    int v = oppo[x];
                    if(!chk[v] && vis[v] != pos) {
                        q[tail++] = v;
                        ans[v] += M - j;
                        vis[v] = pos;
                    }
                }
            }
        }
        pos++;
    }
    for(int i = 0; i < N; i++) {
        for(int j = M - 1; j >= 0; j--) {
            int k = G[i][j] == 'Z';
            if(chk[ f(i, j, k) ]) continue;

            head = tail = 0;
            q[tail++] = f(i, j, k);
            ans[ f(i, j, k) ] += j + 1;
            vis[ f(i, j, k) ] = pos;
            while(head != tail) {
                int u = q[head++];

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

    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

sandwich.cpp: In function 'void scc()':
sandwich.cpp:78: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:94:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &N, &M);
     ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
35.0 / 35.0

#	결과	실행 시간	메모리	Grader output
1	Correct	11 ms	7928 KB	Output is correct
2	Correct	11 ms	8180 KB	Output is correct
3	Correct	9 ms	8200 KB	Output is correct
4	Correct	8 ms	8200 KB	Output is correct
5	Correct	9 ms	8200 KB	Output is correct
6	Correct	9 ms	8612 KB	Output is correct
7	Correct	13 ms	8632 KB	Output is correct
8	Correct	12 ms	8648 KB	Output is correct
9	Correct	11 ms	8648 KB	Output is correct
10	Correct	14 ms	8676 KB	Output is correct
11	Correct	17 ms	8676 KB	Output is correct
12	Correct	14 ms	8676 KB	Output is correct
13	Correct	16 ms	8676 KB	Output is correct
14	Correct	18 ms	8676 KB	Output is correct
15	Correct	15 ms	8676 KB	Output is correct
16	Correct	14 ms	8732 KB	Output is correct
17	Correct	11 ms	8732 KB	Output is correct
18	Correct	12 ms	8748 KB	Output is correct
19	Correct	12 ms	8748 KB	Output is correct
20	Correct	12 ms	8748 KB	Output is correct
21	Correct	12 ms	8752 KB	Output is correct
22	Correct	12 ms	8752 KB	Output is correct
23	Correct	12 ms	8752 KB	Output is correct
24	Correct	16 ms	8768 KB	Output is correct
25	Correct	16 ms	8768 KB	Output is correct
26	Correct	14 ms	8768 KB	Output is correct
27	Correct	11 ms	8768 KB	Output is correct
28	Correct	12 ms	8876 KB	Output is correct

Subtask #2
0 / 65.0

#	결과	실행 시간	메모리	Grader output
1	Correct	11 ms	7928 KB	Output is correct
2	Correct	11 ms	8180 KB	Output is correct
3	Correct	9 ms	8200 KB	Output is correct
4	Correct	8 ms	8200 KB	Output is correct
5	Correct	9 ms	8200 KB	Output is correct
6	Correct	9 ms	8612 KB	Output is correct
7	Correct	13 ms	8632 KB	Output is correct
8	Correct	12 ms	8648 KB	Output is correct
9	Correct	11 ms	8648 KB	Output is correct
10	Correct	14 ms	8676 KB	Output is correct
11	Correct	17 ms	8676 KB	Output is correct
12	Correct	14 ms	8676 KB	Output is correct
13	Correct	16 ms	8676 KB	Output is correct
14	Correct	18 ms	8676 KB	Output is correct
15	Correct	15 ms	8676 KB	Output is correct
16	Correct	14 ms	8732 KB	Output is correct
17	Correct	11 ms	8732 KB	Output is correct
18	Correct	12 ms	8748 KB	Output is correct
19	Correct	12 ms	8748 KB	Output is correct
20	Correct	12 ms	8748 KB	Output is correct
21	Correct	12 ms	8752 KB	Output is correct
22	Correct	12 ms	8752 KB	Output is correct
23	Correct	12 ms	8752 KB	Output is correct
24	Correct	16 ms	8768 KB	Output is correct
25	Correct	16 ms	8768 KB	Output is correct
26	Correct	14 ms	8768 KB	Output is correct
27	Correct	11 ms	8768 KB	Output is correct
28	Correct	12 ms	8876 KB	Output is correct
29	Correct	8 ms	8876 KB	Output is correct
30	Correct	10 ms	8876 KB	Output is correct
31	Correct	59 ms	38820 KB	Output is correct
32	Correct	74 ms	38956 KB	Output is correct
33	Correct	30 ms	38956 KB	Output is correct
34	Correct	4502 ms	38956 KB	Output is correct
35	Correct	2414 ms	38956 KB	Output is correct
36	Correct	30 ms	38956 KB	Output is correct
37	Correct	6099 ms	38956 KB	Output is correct
38	Correct	5632 ms	38956 KB	Output is correct
39	Correct	6483 ms	38956 KB	Output is correct
40	Execution timed out	8101 ms	38956 KB	Time limit exceeded
41	Halted	0 ms	0 KB	-

답안 #59039

Compilation message

Subtask #1 35.0 / 35.0

Subtask #2 0 / 65.0

Subtask #1
35.0 / 35.0

Subtask #2
0 / 65.0