Submission #45426

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
45426	2018-04-13T13:18:09 Z	choikiwon	Young Zebra (KRIII5_YZ)	C++17	0 / 7	500 ms	128632 KB

YZ

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

int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};

int N, M;
int G[402][402], chk[402][402], sz[1000010];
bool vis[402][402][802];

struct Info {
    int r, c, x;
};

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]);
        }
    }

    memset(chk, -1, sizeof(chk));
    memset(vis, 0, sizeof(vis));

    int ccnt = 0;
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < M; j++) {
            if(chk[i][j] != -1) continue;

            queue<Info> q;
            q.push({i, j, 400});
            vis[i][j][400] = 1;
            chk[i][j] = ccnt;

            int cnt = 1;
            int inf = 0;
            while(!q.empty()) {
                Info u = q.front(); q.pop();

                //cout << i << ' ' << j << ' ' << u.r << ' ' << u.c << ' ' << u.x << endl;

                for(int d = 0; d < 4; d++) {
                    int nr = (u.r + N + dy[d]) % N;
                    int nc = (u.c + M + dx[d]) % M;
                    int nx = u.x;
                    if(u.c + dx[d] < 0) nx = u.x - 1;
                    if(u.c + dx[d] >= M) nx = u.x + 1;
                    if(nx < 0 || 800 <= nx) continue;
                    if(G[nr][nc] != G[u.r][u.c]) continue;
                    if(!vis[nr][nc][nx]) {
                        if(chk[nr][nc] != -1) {
                            inf = 1;
                        }
                        else {
                            cnt++;
                            chk[nr][nc] = ccnt;
                        }
                        q.push({nr, nc, nx});
                        vis[nr][nc][nx] = 1;
                    }
                }
            }

            if(sz[ccnt] != -1) sz[ccnt] = inf? -1: cnt;
            ccnt++;
        }
    }

    memset(chk, -1, sizeof(chk));
    memset(vis, 0, sizeof(vis));

    ccnt = 0;
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < M; j++) {
            if(chk[i][j] != -1) continue;

            queue<Info> q;
            q.push({i, j, 400});
            vis[i][j][400] = 1;
            chk[i][j] = ccnt;

            int cnt = 1;
            int inf = 0;
            while(!q.empty()) {
                Info u = q.front(); q.pop();

                //cout << i << ' ' << j << ' ' << u.r << ' ' << u.c << ' ' << u.x << endl;

                for(int d = 0; d < 4; d++) {
                    int nr = (u.r + N + dy[d]) % N;
                    int nc = (u.c + M + dx[d]) % M;
                    int nx = u.x;
                    if(u.r + dy[d] < 0) nx = u.x - 1;
                    if(u.r + dy[d] >= N) nx = u.x + 1;
                    if(nx < 0 || 800 <= nx) continue;
                    if(G[nr][nc] != G[u.r][u.c]) continue;
                    if(!vis[nr][nc][nx]) {
                        if(chk[nr][nc] != -1) {
                            inf = 1;
                        }
                        else {
                            cnt++;
                            chk[nr][nc] = ccnt;
                        }
                        q.push({nr, nc, nx});
                        vis[nr][nc][nx] = 1;
                    }
                }
            }

            if(sz[ccnt] != -1) sz[ccnt] = inf? -1 : cnt;
            ccnt++;
        }
    }

    for(int i = 0; i < N; i++) {
        for(int j = 0; j < M; j++) {
            printf("%d ", sz[ chk[i][j] ]);
        }
        printf("\n");
    }
}

Compilation message

YZ.cpp: In function 'int main()':
YZ.cpp:21:33: warning: format '%c' expects argument of type 'char*', but argument 2 has type 'int*' [-Wformat=]
             scanf("%c", &G[i][j]);
                         ~~~~~~~~^
YZ.cpp:16:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &N, &M);
     ~~~~~^~~~~~~~~~~~~~~~~
YZ.cpp:19:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("\n");
         ~~~~~^~~~~~
YZ.cpp:21: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

0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	1081 ms	128632 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-