Submission #730519

#	Time	Username	Problem	Language	Result	Execution time	Memory
730519		The_Samurai	Land of the Rainbow Gold (APIO17_rainbow)	C++17	11 / 100	3072 ms	1048576 KiB

rainbow

#include "bits/stdc++.h"
#include "rainbow.h"
using namespace std;

vector<vector<bool>> ex;
int r, c;

void init(int R, int C, int sr, int sc, int M, char *S) {
    r = R; c = C;
    ex.assign(r + 1, vector<bool>(c + 1));
    ex[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++;
        ex[sr][sc] = true;
    }
}

int colour(int ar, int ac, int br, int bc) {
    auto vis = ex;
    int ans = 0;
//    cout << '\t' << ar << ' ' << ac << ' ' << br << ' ' << bc << endl;
    for (int x = ar; x <= br; x++) {
        for (int y = ac; y <= bc; y++) {
            if (vis[x][y]) continue;
            queue<pair<int, int>> q;
            q.push({x, y});
            vis[x][y] = true;
            ans++;
            vector<pair<int, int>> a = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
            while (!q.empty()) {
                auto [qx, qy] = q.front();
//                cout << '\t' << qx << ' ' << qy << endl;
                q.pop();
                for (auto [dx, dy]: a) {
                    qx += dx; qy += dy;
                    if (qx >= ar and qx <= br and qy >= ac and qy <= bc and !vis[qx][qy]) {
                        vis[qx][qy] = true;
                        q.push({qx, qy});
                    }
                    qx -= dx; qy -= dy;
                }
            }
        }
    }
    return ans;
}

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