답안 #64999 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
64999	2018-08-06T12:02:06 Z	patrikpavic2	Dango Maker (JOI18_dango_maker)	C++17	33 / 100	5 ms	692 KB

dango_maker

        #include <cstdio>
        #include <cstring>
        #include <vector>

        using namespace std;

        const int N = 105;
        const int M = N * N / 5;

        vector < int > v[M];

        bool bio[M], ty[M];
        int mat[M], kk[N][N][2];
        char s[N][N];
        int n, m, edg, cnt = 1;

        int dfs( int node ) {
            if( bio[ node ] ) return 0;
            bio[ node ] = 1;
            for(int sus : v[node]){
                if( mat[ sus ] == -1 || dfs( mat[ sus ]) ) {
                    mat[ sus ] = node;
                    return 1;
                }
            }
            return 0;
        }

        int matching( ) {
            int sol = 0;
            memset( mat, -1, sizeof( mat ) );
            for( int i = 1; i < cnt; i++) {
                if(ty[i]) continue;
                memset(bio, 0, sizeof(bio));
                sol += dfs(i);

            }
            return sol;
        }


        int main(){
            memset(s, '.', sizeof(s));
            scanf("%d%d", &n, &m);
            for(int i = 1;i<=n;i++){
                for(int j = 1;j<=m;j++){
                    scanf(" %c", &s[i][j]);
                }
            }
            for(int i = 1;i<=n;i++){
                for(int j = 1;j<=m;j++){
                    if(s[i][j] != 'G') continue;
                    int kol = 0;
                    if(s[i - 1][j] == 'R' && s[i + 1][j] == 'W'){
                        kk[i][j][0] = cnt;
                        cnt++;kol++;
                    }
                    if(s[i][j - 1] == 'R' && s[i][j + 1] == 'W'){
                        ty[cnt] = 1;
                        kk[i][j][1] = cnt;
                        cnt++;kol++;
                    }
                    if(kol == 2){
                        v[cnt - 1].push_back(cnt - 2);
                        v[cnt - 2].push_back(cnt - 1);
                        edg++;
                    }
                }
            }
            for(int i = 1;i<=n;i++){
                for(int j = 1;j<=m;j++){
                    if(i + 1 < n && j + 1 < m && s[i][j] == 'R' && s[i + 1][j] == 'G' && s[i][j + 1] == 'G' && s[i + 2][j] == 'W' && s[i][j + 2] == 'W'){
                        v[kk[i + 1][j][0]].push_back(kk[i][j + 1][1]);
                        v[kk[i][j + 1][1]].push_back(kk[i + 1][j][0]);
                        //printf("AT %d %d\n", i, j);
                        edg++;
                    }
                    if(i > 2 && j > 2 && s[i][j] == 'W' && s[i - 1][j] == 'G' && s[i][j - 1] == 'G' && s[i - 2][j] == 'R' && s[i][j - 2] == 'R'){
                        v[kk[i - 1][j][0]].push_back(kk[i][j - 1][1]);
                        v[kk[i][j - 1][1]].push_back(kk[i - 1][j][0]);
                        //printf("AT %d %d\n", i, j);
                        edg++;
                    }

                }
            }
            //printf("EDG %d\n", edg);
            printf("%d\n", cnt - matching() - 1);
            return 0;
        }

Compilation message

dango_maker.cpp: In function 'int main()':
dango_maker.cpp:44:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d%d", &n, &m);
             ~~~~~^~~~~~~~~~~~~~~~
dango_maker.cpp:47:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
                     scanf(" %c", &s[i][j]);
                     ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
13.0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	5 ms	540 KB	Output is correct
3	Correct	4 ms	540 KB	Output is correct
4	Correct	2 ms	540 KB	Output is correct
5	Correct	2 ms	540 KB	Output is correct
6	Correct	2 ms	540 KB	Output is correct
7	Correct	3 ms	596 KB	Output is correct
8	Correct	5 ms	648 KB	Output is correct
9	Correct	2 ms	648 KB	Output is correct
10	Correct	3 ms	648 KB	Output is correct
11	Correct	2 ms	648 KB	Output is correct
12	Correct	2 ms	648 KB	Output is correct
13	Correct	2 ms	648 KB	Output is correct
14	Correct	2 ms	648 KB	Output is correct
15	Correct	3 ms	680 KB	Output is correct
16	Correct	3 ms	680 KB	Output is correct

Subtask #2
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	5 ms	540 KB	Output is correct
3	Correct	4 ms	540 KB	Output is correct
4	Correct	2 ms	540 KB	Output is correct
5	Correct	2 ms	540 KB	Output is correct
6	Correct	2 ms	540 KB	Output is correct
7	Correct	3 ms	596 KB	Output is correct
8	Correct	5 ms	648 KB	Output is correct
9	Correct	2 ms	648 KB	Output is correct
10	Correct	3 ms	648 KB	Output is correct
11	Correct	2 ms	648 KB	Output is correct
12	Correct	2 ms	648 KB	Output is correct
13	Correct	2 ms	648 KB	Output is correct
14	Correct	2 ms	648 KB	Output is correct
15	Correct	3 ms	680 KB	Output is correct
16	Correct	3 ms	680 KB	Output is correct
17	Correct	2 ms	680 KB	Output is correct
18	Correct	3 ms	680 KB	Output is correct
19	Correct	2 ms	680 KB	Output is correct
20	Correct	2 ms	680 KB	Output is correct
21	Correct	3 ms	680 KB	Output is correct
22	Correct	2 ms	680 KB	Output is correct
23	Correct	3 ms	680 KB	Output is correct
24	Correct	3 ms	680 KB	Output is correct
25	Correct	3 ms	680 KB	Output is correct
26	Correct	3 ms	692 KB	Output is correct
27	Correct	3 ms	692 KB	Output is correct
28	Correct	2 ms	692 KB	Output is correct
29	Correct	3 ms	692 KB	Output is correct
30	Correct	3 ms	692 KB	Output is correct
31	Correct	3 ms	692 KB	Output is correct
32	Correct	4 ms	692 KB	Output is correct
33	Correct	3 ms	692 KB	Output is correct
34	Correct	4 ms	692 KB	Output is correct
35	Correct	3 ms	692 KB	Output is correct
36	Correct	2 ms	692 KB	Output is correct
37	Correct	2 ms	692 KB	Output is correct
38	Correct	2 ms	692 KB	Output is correct
39	Correct	3 ms	692 KB	Output is correct
40	Correct	3 ms	692 KB	Output is correct
41	Correct	2 ms	692 KB	Output is correct
42	Correct	3 ms	692 KB	Output is correct
43	Correct	2 ms	692 KB	Output is correct
44	Correct	3 ms	692 KB	Output is correct
45	Correct	2 ms	692 KB	Output is correct
46	Correct	2 ms	692 KB	Output is correct
47	Correct	3 ms	692 KB	Output is correct
48	Correct	4 ms	692 KB	Output is correct
49	Correct	3 ms	692 KB	Output is correct
50	Correct	2 ms	692 KB	Output is correct
51	Correct	3 ms	692 KB	Output is correct
52	Correct	3 ms	692 KB	Output is correct
53	Correct	3 ms	692 KB	Output is correct

Subtask #3
0 / 67.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	5 ms	540 KB	Output is correct
3	Correct	4 ms	540 KB	Output is correct
4	Correct	2 ms	540 KB	Output is correct
5	Correct	2 ms	540 KB	Output is correct
6	Correct	2 ms	540 KB	Output is correct
7	Correct	3 ms	596 KB	Output is correct
8	Correct	5 ms	648 KB	Output is correct
9	Correct	2 ms	648 KB	Output is correct
10	Correct	3 ms	648 KB	Output is correct
11	Correct	2 ms	648 KB	Output is correct
12	Correct	2 ms	648 KB	Output is correct
13	Correct	2 ms	648 KB	Output is correct
14	Correct	2 ms	648 KB	Output is correct
15	Correct	3 ms	680 KB	Output is correct
16	Correct	3 ms	680 KB	Output is correct
17	Correct	2 ms	680 KB	Output is correct
18	Correct	3 ms	680 KB	Output is correct
19	Correct	2 ms	680 KB	Output is correct
20	Correct	2 ms	680 KB	Output is correct
21	Correct	3 ms	680 KB	Output is correct
22	Correct	2 ms	680 KB	Output is correct
23	Correct	3 ms	680 KB	Output is correct
24	Correct	3 ms	680 KB	Output is correct
25	Correct	3 ms	680 KB	Output is correct
26	Correct	3 ms	692 KB	Output is correct
27	Correct	3 ms	692 KB	Output is correct
28	Correct	2 ms	692 KB	Output is correct
29	Correct	3 ms	692 KB	Output is correct
30	Correct	3 ms	692 KB	Output is correct
31	Correct	3 ms	692 KB	Output is correct
32	Correct	4 ms	692 KB	Output is correct
33	Correct	3 ms	692 KB	Output is correct
34	Correct	4 ms	692 KB	Output is correct
35	Correct	3 ms	692 KB	Output is correct
36	Correct	2 ms	692 KB	Output is correct
37	Correct	2 ms	692 KB	Output is correct
38	Correct	2 ms	692 KB	Output is correct
39	Correct	3 ms	692 KB	Output is correct
40	Correct	3 ms	692 KB	Output is correct
41	Correct	2 ms	692 KB	Output is correct
42	Correct	3 ms	692 KB	Output is correct
43	Correct	2 ms	692 KB	Output is correct
44	Correct	3 ms	692 KB	Output is correct
45	Correct	2 ms	692 KB	Output is correct
46	Correct	2 ms	692 KB	Output is correct
47	Correct	3 ms	692 KB	Output is correct
48	Correct	4 ms	692 KB	Output is correct
49	Correct	3 ms	692 KB	Output is correct
50	Correct	2 ms	692 KB	Output is correct
51	Correct	3 ms	692 KB	Output is correct
52	Correct	3 ms	692 KB	Output is correct
53	Correct	3 ms	692 KB	Output is correct
54	Incorrect	2 ms	692 KB	Output isn't correct
55	Halted	0 ms	0 KB	-

답안 #64999

Compilation message

Subtask #1 13.0 / 13.0

Subtask #2 20.0 / 20.0

Subtask #3 0 / 67.0

Subtask #1
13.0 / 13.0

Subtask #2
20.0 / 20.0

Subtask #3
0 / 67.0