oj.uz

Submission #406460

# Submission time Handle Problem Language Result Execution time Memory
406460 2021-05-17T15:42:02 Z aryan12 Land of the Rainbow Gold (APIO17_rainbow) C++17
11 / 100
 3000 ms 2084 KB 
#include "rainbow.h"
#include <bits/stdc++.h>
using namespace std;

const int N = 55;
bool isRiver[N][N], vis[N][N];
char direction[4] = {'N', 'S', 'E', 'W'};
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, 1, -1};

void init(int R, int C, int sr, int sc, int M, char *S) {
    for(int i = 1; i <= R; i++) {
        for(int j = 1; j <= C; j++) {
            isRiver[i][j] = false;
        }
    }
    isRiver[sr][sc] = true;
    for(int i = 0; i < M; i++) {
        for(int j = 0; j < 4; j++) {
            if(direction[j] == S[i]) {
                sr += dx[j];
                sc += dy[j];
                isRiver[sr][sc] = true;
                break;
            }
        }
    }
    /*for(int i = 1; i <= R; i++) {
        for(int j = 1; j <= C; j++) {
            cout << isRiver[i][j] << " ";
        }
        cout << "\n";
    }*/
}

void DoBfs(int row_min, int col_min, int row_max, int col_max, int cur_row, int cur_col) {
    queue<pair<int, int> > bfs;
    bfs.push({cur_row, cur_col});
    vis[cur_row][cur_col] = true;
    while(!bfs.empty()) {
        cur_row = bfs.front().first, cur_col = bfs.front().second;
        bfs.pop();
        for(int i = 0; i < 4; i++) {
            if(vis[cur_row + dx[i]][cur_col + dy[i]] || isRiver[cur_row + dx[i]][cur_col + dy[i]])
                continue;
            if(cur_row + dx[i] < row_min || cur_row + dx[i] > row_max)
                continue;
            if(cur_col + dy[i] < col_min || cur_col + dy[i] > col_max)
                continue;
            bfs.push({cur_row + dx[i], cur_col + dy[i]});
            vis[cur_row + dx[i]][cur_col + dy[i]] = true;
        }
    }
}

int colour(int ar, int ac, int br, int bc) {
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < N; j++) {
            vis[i][j] = false;
        }
    }
    int cnt = 0;
    for(int i = ar; i <= br; i++) {
        for(int j = ac; j <= bc; j++) {
            if(!vis[i][j] && !isRiver[i][j]) {
                DoBfs(ar, ac, br, bc, i, j);
                cnt++;
            }
        }
    }
    return cnt;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 332 KB Output is correct
2 Correct 8 ms 332 KB Output is correct
3 Correct 19 ms 332 KB Output is correct
4 Correct 20 ms 204 KB Output is correct
5 Correct 8 ms 332 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 17 ms 336 KB Output is correct
12 Correct 14 ms 332 KB Output is correct
13 Correct 11 ms 336 KB Output is correct
14 Correct 17 ms 332 KB Output is correct
15 Correct 1 ms 296 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 1 ms 204 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Runtime error 2 ms 716 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 296 KB Output is correct
2 Runtime error 2 ms 588 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 332 KB Output is correct
2 Correct 8 ms 332 KB Output is correct
3 Correct 19 ms 332 KB Output is correct
4 Correct 20 ms 204 KB Output is correct
5 Correct 8 ms 332 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 17 ms 336 KB Output is correct
12 Correct 14 ms 332 KB Output is correct
13 Correct 11 ms 336 KB Output is correct
14 Correct 17 ms 332 KB Output is correct
15 Correct 1 ms 296 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Execution timed out 3067 ms 2084 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 332 KB Output is correct
2 Correct 8 ms 332 KB Output is correct
3 Correct 19 ms 332 KB Output is correct
4 Correct 20 ms 204 KB Output is correct
5 Correct 8 ms 332 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 17 ms 336 KB Output is correct
12 Correct 14 ms 332 KB Output is correct
13 Correct 11 ms 336 KB Output is correct
14 Correct 17 ms 332 KB Output is correct
15 Correct 1 ms 296 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Execution timed out 3067 ms 2084 KB Time limit exceeded
19 Halted 0 ms 0 KB -