Submission #1169687

#	Time	Username	Problem	Language	Result	Execution time	Memory
1169687		stdfloat	Land of the Rainbow Gold (APIO17_rainbow)	C++20	11 / 100	3096 ms	1114112 KiB

rainbow

#include <bits/stdc++.h>
#include "rainbow.h"
// #include "grader.cpp"
using namespace std;

int n, m;

vector<vector<bool>> rv;

vector<int> dX = {-1, 0, 1, 0}, dY = {0, 1, 0, -1};

void init(int R, int C, int sr, int sc, int M, char *S) {
    n = R; m = C;

    sr--; sc--;

    rv.assign(n, vector<bool>(m));
    rv[sr][sc] = true;
    for (int i = 0; i < M; i++) {
        if (S[i] == 'N') sr--;
        else if (S[i] == 'S') sr++;
        else if (S[i] == 'W') sc--;
        else sc++;
    
        rv[sr][sc] = true;
    }
}

int colour(int ar, int ac, int br, int bc) {
    ar--; ac--; br--; bc--;

    int cnt = 0;
    vector<vector<bool>> vis(n, vector<bool>(m));
    for (int i = ar; i <= br; i++) {
        for (int j = ac; j <= bc; j++) {
            if (rv[i][j] || vis[i][j]) continue;
        
            cnt++;

            queue<pair<int, int>> q;
            q.push({i, j});
            vis[i][j] = true;
            while (!q.empty()) {
                auto [x, y] = q.front(); q.pop();

                for (int i = 0; i < 4; i++) {
                    int nx = x + dX[i], ny = y + dY[i];
                    if (ar <= nx && nx <= br && ac <= ny && ny <= bc && !vis[nx][ny] && !rv[nx][ny]) {
                        q.push({nx, ny});
                        vis[nx][ny] = true;
                    }
                }
            }
        }
    }

    return cnt;
}

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