Submission #731974

#	Time	Username	Problem	Language	Result	Execution time	Memory
731974		Josia	Land of the Rainbow Gold (APIO17_rainbow)	C++14	11 / 100	3062 ms	1048576 KiB

rainbow

#include "rainbow.h"

#include <bits/stdc++.h>

using namespace std;


int R, C;
vector<vector<bool>> riv;

map<char, pair<int, int>> dir;


void init(signed r, signed c, signed sr, signed sc, signed M, char *S) {
    dir['N'] = {-1, 0};
    dir['S'] = {1, 0};
    dir['W'] = {0, -1};
    dir['E'] = {0, 1};


    R = r; C = c;
    riv.assign(R, vector<bool>(C));

    pair<int, int> pos = {sr-1, sc-1};
    riv[pos.first][pos.second]=1;


    for (int i=0;i<M;i++) {
        pos.first += dir[S[i]].first;
        pos.second += dir[S[i]].second;

        riv[pos.first][pos.second]=1;
    }
}



vector<vector<bool>> vis;

bool dfs(pair<int, int> v, int ar, int ac, int br, int bc) {
    if (v.first < ar || v.first > br) return 0;
    if (v.second < ac || v.second > bc) return 0;
    if (vis[v.first][v.second]) return 0;
    if (riv[v.first][v.second]) return 0;
    vis[v.first][v.second] = 1;


    for (auto i: dir) {
        dfs({v.first+i.second.first, v.second + i.second.second}, ar, ac, br, bc);
    }

    return 1;
}


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

    vis.assign(R, vector<bool>(C));

    int res = 0;

    for (int i = ar; i<=br; i++) {
        for (int j = ac; j<=bc; j++) {
            res += dfs({i, j}, ar, ac, br, bc);
        }
    }

    return res;

}

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