Submission #403327

#	Time	Username	Problem	Language	Result	Execution time	Memory
403327		wiwiho	Land of the Rainbow Gold (APIO17_rainbow)	C++14	11 / 100	3092 ms	1048580 KiB

rainbow

#include "rainbow.h"

#include <bits/stdc++.h>

#define mp make_pair
#define F first
#define S second
#define printv(a, b) { \
    for(auto pv : a) b << pv << " "; \
    b << "\n"; \
}

using namespace std;

using pii = pair<int, int>;

vector<vector<bool>> g;
vector<vector<int>> vst;

int n, m;

void init(int R, int C, int sr, int sc, int M, char *S) {
    n = R; m = C;
    g.resize(n + 2, vector<bool>(m + 2));
    for(int i = 1; i <= m; i++){
        g[0][i] = g[n + 1][i] = true;
    }
    for(int i = 1; i <= n; i++){
        g[i][0] = g[i][m + 1] = true;
    }

    g[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++;
        g[sr][sc] = true;
    }

    //for(int i = 0; i <= n + 1; i++) printv(g[i], cerr);
}

vector<pii> dir = {mp(1, 0), mp(0, 1), mp(-1, 0), mp(0, -1)};

void bfs(int sx, int sy, int ar, int ac, int br, int bc){
    queue<pii> q;
    q.push(mp(sx, sy));
    vst[sx][sy] = true;
    while(!q.empty()){
        int x = q.front().F, y = q.front().S;
        q.pop();
        for(pii d : dir){
            int nx = x + d.F, ny = y + d.S;
            if(g[nx][ny] || vst[nx][ny]) continue;
            if(nx < ar || br < nx || ny < ac || bc < ny) continue;
            vst[nx][ny] = true;
            q.push(mp(nx, ny));
        }
    }
}

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

    vst.clear();
    vst.resize(n + 2, vector<int>(m + 2));

    int ans = 0;
    for(int i = ar; i <= br; i++){
        for(int j = ac; j <= bc; j++){
            if(g[i][j] || vst[i][j]) continue;
            ans++;
            bfs(i, j, ar, ac, br, bc);
        }
    }

    return ans;
}

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