oj.uz

Submission #65011

# Submission time Handle Problem Language Result Execution time Memory
65011 2018-08-06T12:18:10 Z patrikpavic2 Dango Maker (JOI18_dango_maker) C++17
0 / 100
 686 ms 263168 KB 
#include <cstdio>
#include <cstring>
#include <vector>

using namespace std;

const int N = 3e3 + 50;
const int M = N * N / 3;

vector < int > v[M];

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

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

int matching( ) {
    int sol = 0;
    memset( mat, -1, sizeof( mat ) );
    for( int i = cnt - 1; i ; i--) {
        if(ty[i]) continue;
        cookie++;
        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++){
            char c = getchar_unlocked();
            while(c != 'R' && c != 'W' && c != 'G') c = getchar_unlocked();
            s[i][j] = c;
        }
    }
    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]);
                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]);
                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:45: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
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 94412 KB Output is correct
2 Correct 90 ms 94440 KB Output is correct
3 Correct 86 ms 94516 KB Output is correct
4 Correct 81 ms 94576 KB Output is correct
5 Correct 101 ms 94576 KB Output is correct
6 Runtime error 686 ms 263168 KB Execution killed with signal 9 (could be triggered by violating memory limits)
7 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 94412 KB Output is correct
2 Correct 90 ms 94440 KB Output is correct
3 Correct 86 ms 94516 KB Output is correct
4 Correct 81 ms 94576 KB Output is correct
5 Correct 101 ms 94576 KB Output is correct
6 Runtime error 686 ms 263168 KB Execution killed with signal 9 (could be triggered by violating memory limits)
7 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 94412 KB Output is correct
2 Correct 90 ms 94440 KB Output is correct
3 Correct 86 ms 94516 KB Output is correct
4 Correct 81 ms 94576 KB Output is correct
5 Correct 101 ms 94576 KB Output is correct
6 Runtime error 686 ms 263168 KB Execution killed with signal 9 (could be triggered by violating memory limits)
7 Halted 0 ms 0 KB -