Submission #1203807

#	Time	Username	Problem	Language	Result	Execution time	Memory
1203807		jj_master	Land of the Rainbow Gold (APIO17_rainbow)	C++20	0 / 100	3090 ms	5476 KiB

rainbow

#include <bits/stdc++.h>
using namespace std;

const int N = 1005;

bool riv[N][N];            
int component[N][N];       
int R, C;
int dr[] = {-1, 1, 0, 0};
int dc[] = {0, 0, 1, -1};
int component_id = 0;

bool in_bounds(int r, int c) {
    return r >= 1 && r <= R && c >= 1 && c <= C;
}

void bfs(int sr, int sc) {
    queue<pair<int, int>> q;
    q.push({sr, sc});
    component[sr][sc] = component_id;

    while (!q.empty()) {
        auto [r, c] = q.front(); q.pop();
        for (int d = 0; d < 4; d++) {
            int nr = r + dr[d], nc = c + dc[d];
            if (in_bounds(nr, nc) && !riv[nr][nc] && component[nr][nc] == -1) {
                component[nr][nc] = component_id;
                q.push({nr, nc});
            }
        }
    }
}

void init(int r, int c, int sr, int sc, int m, char* s) {
    R = r;
    C = c;
    memset(riv, 0, sizeof(riv));
    memset(component, -1, sizeof(component));
    component_id = 0;
    int x = sr, y = sc;
    riv[x][y] = true;
    for (int i = 0; i < m; ++i) {
        if (s[i] == 'N') --x;
        else if (s[i] == 'S') ++x;
        else if (s[i] == 'E') ++y;
        else if (s[i] == 'W') --y;
        riv[x][y] = true;
    }
    for (int i = 1; i <= R; i++) {
        for (int j = 1; j <= C; j++) {
            if (!riv[i][j] && component[i][j] == -1) {
                bfs(i, j);
                component_id++;
            }
        }
    }
}

int colour(int r1, int c1, int r2, int c2) {
    unordered_set<int> unique_components;
    for (int i = r1; i <= r2; ++i) {
        for (int j = c1; j <= c2; ++j) {
            int id = component[i][j];
            if (id != -1) {
                unique_components.insert(id);
            }
        }
    }
    return unique_components.size();
}

• Subtask 1: 0 / 11
• Subtask 2: 0 / 12
• Subtask 3: 0 / 24
• Subtask 4: 0 / 27
• Subtask 5: 0 / 26