oj.uz

Submission #64138

# Submission time Handle Problem Language Result Execution time Memory
64138 2018-08-03T12:00:29 Z patrikpavic2 Dango Maker (JOI18_dango_maker) C++17
13 / 100
 96 ms 79444 KB 
#include <cstdio>
#include <cstring>
#include <vector>

using namespace std;

const int N = 1e3 + 50;
const int M = 2 * N * N;

vector < int > v[M], k[N][N];

int ty[M], sl[M], bio[M];
char s[N][N];
int n, m, edg;


void dfs(int x){
    sl[ty[x]]++;
    bio[x] = 1;
    edg += int(v[x].size());
    for(int y : v[x])
        if(!bio[y])
            dfs(y);
}

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]);
        }
    }
    int cnt = 1;
    for(int i = 1;i<=n;i++){
        for(int j = 1;j<=m;j++){
            if(s[i][j] != 'G') continue;
            if(s[i - 1][j] == 'R' && s[i + 1][j] == 'W'){
                k[i - 1][j].push_back(cnt);
                k[i + 1][j].push_back(cnt);
                k[i][j].push_back(cnt);
                cnt++;
            }
            if(s[i][j - 1] == 'R' && s[i][j + 1] == 'W'){
                k[i][j - 1].push_back(cnt);
                k[i][j + 1].push_back(cnt);
                k[i][j].push_back(cnt);
                ty[cnt] = 1;
                cnt++;
            }
        }
    }
    for(int i = 1;i<=n;i++){
        for(int j = 1;j<=m;j++){
            if(k[i][j].size() == 2){
                v[k[i][j][0]].push_back(k[i][j][1]);
                v[k[i][j][1]].push_back(k[i][j][0]);
            }
        }
    }
    int sol = 0;
    //printf("CNT = %d\n", cnt);
    for(int i = 1;i<cnt;i++){
        if(bio[i]) continue;
        sl[0] = 0, sl[1] = 0;
        dfs(i);
        if((sl[0] + sl[1]) * 2 < edg) printf("PUSI KURAC\n");
        //printf("X : %d, %d %d\n", sl[0], sl[1]);
        sol += max(sl[0], sl[1]);
    }
    printf("%d\n", sol);
    return 0;
}

Compilation message

dango_maker.cpp: In function 'int main()':
dango_maker.cpp:28:10: 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:31:18: 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 89 ms 79156 KB Output is correct
2 Correct 82 ms 79156 KB Output is correct
3 Correct 90 ms 79156 KB Output is correct
4 Correct 85 ms 79272 KB Output is correct
5 Correct 77 ms 79332 KB Output is correct
6 Correct 79 ms 79332 KB Output is correct
7 Correct 82 ms 79332 KB Output is correct
8 Correct 72 ms 79332 KB Output is correct
9 Correct 83 ms 79332 KB Output is correct
10 Correct 71 ms 79332 KB Output is correct
11 Correct 75 ms 79332 KB Output is correct
12 Correct 78 ms 79444 KB Output is correct
13 Correct 80 ms 79444 KB Output is correct
14 Correct 83 ms 79444 KB Output is correct
15 Correct 72 ms 79444 KB Output is correct
16 Correct 92 ms 79444 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 79156 KB Output is correct
2 Correct 82 ms 79156 KB Output is correct
3 Correct 90 ms 79156 KB Output is correct
4 Correct 85 ms 79272 KB Output is correct
5 Correct 77 ms 79332 KB Output is correct
6 Correct 79 ms 79332 KB Output is correct
7 Correct 82 ms 79332 KB Output is correct
8 Correct 72 ms 79332 KB Output is correct
9 Correct 83 ms 79332 KB Output is correct
10 Correct 71 ms 79332 KB Output is correct
11 Correct 75 ms 79332 KB Output is correct
12 Correct 78 ms 79444 KB Output is correct
13 Correct 80 ms 79444 KB Output is correct
14 Correct 83 ms 79444 KB Output is correct
15 Correct 72 ms 79444 KB Output is correct
16 Correct 92 ms 79444 KB Output is correct
17 Correct 84 ms 79444 KB Output is correct
18 Correct 96 ms 79444 KB Output is correct
19 Incorrect 90 ms 79444 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 79156 KB Output is correct
2 Correct 82 ms 79156 KB Output is correct
3 Correct 90 ms 79156 KB Output is correct
4 Correct 85 ms 79272 KB Output is correct
5 Correct 77 ms 79332 KB Output is correct
6 Correct 79 ms 79332 KB Output is correct
7 Correct 82 ms 79332 KB Output is correct
8 Correct 72 ms 79332 KB Output is correct
9 Correct 83 ms 79332 KB Output is correct
10 Correct 71 ms 79332 KB Output is correct
11 Correct 75 ms 79332 KB Output is correct
12 Correct 78 ms 79444 KB Output is correct
13 Correct 80 ms 79444 KB Output is correct
14 Correct 83 ms 79444 KB Output is correct
15 Correct 72 ms 79444 KB Output is correct
16 Correct 92 ms 79444 KB Output is correct
17 Correct 84 ms 79444 KB Output is correct
18 Correct 96 ms 79444 KB Output is correct
19 Incorrect 90 ms 79444 KB Output isn't correct
20 Halted 0 ms 0 KB -