oj.uz

Submission #64997

# Submission time Handle Problem Language Result Execution time Memory
64997 2018-08-06T11:58:49 Z patrikpavic2 Dango Maker (JOI18_dango_maker) C++17
13 / 100
 3 ms 688 KB 
    #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;
            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:43:14: 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:46:22: 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

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 484 KB Output is correct
3 Correct 2 ms 560 KB Output is correct
4 Correct 2 ms 560 KB Output is correct
5 Correct 2 ms 636 KB Output is correct
6 Correct 2 ms 636 KB Output is correct
7 Correct 3 ms 644 KB Output is correct
8 Correct 3 ms 644 KB Output is correct
9 Correct 2 ms 644 KB Output is correct
10 Correct 2 ms 644 KB Output is correct
11 Correct 3 ms 644 KB Output is correct
12 Correct 2 ms 644 KB Output is correct
13 Correct 2 ms 644 KB Output is correct
14 Correct 3 ms 644 KB Output is correct
15 Correct 3 ms 644 KB Output is correct
16 Correct 3 ms 644 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 484 KB Output is correct
3 Correct 2 ms 560 KB Output is correct
4 Correct 2 ms 560 KB Output is correct
5 Correct 2 ms 636 KB Output is correct
6 Correct 2 ms 636 KB Output is correct
7 Correct 3 ms 644 KB Output is correct
8 Correct 3 ms 644 KB Output is correct
9 Correct 2 ms 644 KB Output is correct
10 Correct 2 ms 644 KB Output is correct
11 Correct 3 ms 644 KB Output is correct
12 Correct 2 ms 644 KB Output is correct
13 Correct 2 ms 644 KB Output is correct
14 Correct 3 ms 644 KB Output is correct
15 Correct 3 ms 644 KB Output is correct
16 Correct 3 ms 644 KB Output is correct
17 Correct 3 ms 644 KB Output is correct
18 Correct 3 ms 644 KB Output is correct
19 Correct 2 ms 644 KB Output is correct
20 Correct 3 ms 644 KB Output is correct
21 Correct 2 ms 644 KB Output is correct
22 Correct 3 ms 644 KB Output is correct
23 Correct 3 ms 644 KB Output is correct
24 Correct 3 ms 644 KB Output is correct
25 Correct 3 ms 644 KB Output is correct
26 Correct 3 ms 688 KB Output is correct
27 Incorrect 2 ms 688 KB Output isn't correct
28 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 484 KB Output is correct
3 Correct 2 ms 560 KB Output is correct
4 Correct 2 ms 560 KB Output is correct
5 Correct 2 ms 636 KB Output is correct
6 Correct 2 ms 636 KB Output is correct
7 Correct 3 ms 644 KB Output is correct
8 Correct 3 ms 644 KB Output is correct
9 Correct 2 ms 644 KB Output is correct
10 Correct 2 ms 644 KB Output is correct
11 Correct 3 ms 644 KB Output is correct
12 Correct 2 ms 644 KB Output is correct
13 Correct 2 ms 644 KB Output is correct
14 Correct 3 ms 644 KB Output is correct
15 Correct 3 ms 644 KB Output is correct
16 Correct 3 ms 644 KB Output is correct
17 Correct 3 ms 644 KB Output is correct
18 Correct 3 ms 644 KB Output is correct
19 Correct 2 ms 644 KB Output is correct
20 Correct 3 ms 644 KB Output is correct
21 Correct 2 ms 644 KB Output is correct
22 Correct 3 ms 644 KB Output is correct
23 Correct 3 ms 644 KB Output is correct
24 Correct 3 ms 644 KB Output is correct
25 Correct 3 ms 644 KB Output is correct
26 Correct 3 ms 688 KB Output is correct
27 Incorrect 2 ms 688 KB Output isn't correct
28 Halted 0 ms 0 KB -