Submission #569459

#	Time	Username	Problem	Language	Result	Execution time	Memory
569459		saarang123	Land of the Rainbow Gold (APIO17_rainbow)	C++17	11 / 100	3081 ms	4648 KiB

rainbow

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

// https://github.com/Aeren1564/Algorithms
template<bool Enable_small_to_large = true>
struct disjoint_set {
    int n, cc;
    vector<int> p;
    disjoint_set(int n): n(n), p(n, -1), cc(n) { }
    int root(int u) {
        return p[u] < 0 ? u : p[u] = root(p[u]);
    }
    bool share(int a, int b) {
        return root(a) == root(b);
    }
    int size(int u) {
        return -p[root(u)];
    }
    bool merge(int u, int v) {
        u = root(u), v = root(v);
        if(u == v) return false;
        if constexpr(Enable_small_to_large) if(p[u] > p[v]) swap(u, v);
        p[u] += p[v], p[v] = u; cc--;
        return true;
    }
    void clear() {
        fill(p.begin(), p.end(), -1);
    }
    vector<vector<int>> group_up() {
        vector<vector<int>> g(n);
        for(auto i = 0; i < n; ++ i) g[root(i)].push_back(i);
        g.erase(remove_if(g.begin(), g.end(), [&](auto &s){ return s.empty(); }), g.end());
        return g;
    }
};

const int MXN = 53;
const vector<array<int, 2>> dir = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
bool f[MXN][MXN];
int n, m;

int con(int i, int j) {
    return m * i + j;
}

void init(int R, int C, int sr, int sc, int M, char *S) {
    n = R, m = C;
    int x = sr - 1, y = sc - 1;
    f[x][y] = true;
    for(int i = 0; i < M; i++) {
        char c = S[i];
        if(c == 'N')
            x--;
        else if(c == 'S')
            x++;
        else if(c == 'W')
            y--;
        else
            y++;
        //cout << x + 1 << ' ' << y + 1 << '\n';
        f[x][y] = true;
    }
}

int colour(int ar, int ac, int br, int bc) {
    vector<bool> vis(n * m);
    ar--, ac--, br--, bc--;
    function<void(int, int)> dfs = [&] (int i, int j) {
        if(vis[con(i, j)])
            return;
        vis[con(i, j)] = true;
        //cout << i + 1 << ' ' << j + 1 << '\n';
        for(auto &[dx, dy] : dir) {
            int nx = i + dx, ny = j + dy;
            if(ar <= nx && nx <= br && ac <= ny && ny <= bc && !f[nx][ny])
                dfs(nx, ny);
        }
    };
    int cnt = 0;
    for(int i = ar; i <= br; i++)
        for(int j = ac; j <= bc; j++) if(!f[i][j] && !vis[con(i, j)]) {
            cnt++;
            //cout << "ok: " << cnt << endl;
            dfs(i, j);
        }
    //cout << cnt << '\n';
    return cnt;
}

#ifdef saarang
static int R, C, M, Q;
static int sr, sc;
static char S[100000 + 5];

int main() {
    scanf("%d %d %d %d", &R, &C, &M, &Q);
    scanf("%d %d", &sr, &sc);
    if (M > 0) {
        scanf(" %s ", S);
    }

    init(R, C, sr, sc, M, S);

    int query;
    for (query = 0; query < Q; query++) {
        int ar, ac, br, bc;
        scanf("%d %d %d %d", &ar, &ac, &br, &bc);
        printf("%d\n", colour(ar, ac, br, bc));
    }

    return 0;
}
#endif

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