oj.uz

Submission #569459

# Submission time Handle Problem Language Result Execution time Memory
569459 2022-05-27T12:02:04 Z saarang123 Land of the Rainbow Gold (APIO17_rainbow) C++17
11 / 100
 3000 ms 4648 KB 
#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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 212 KB Output is correct
2 Correct 9 ms 212 KB Output is correct
3 Correct 33 ms 468 KB Output is correct
4 Correct 34 ms 432 KB Output is correct
5 Correct 8 ms 372 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 24 ms 424 KB Output is correct
12 Correct 22 ms 340 KB Output is correct
13 Correct 11 ms 368 KB Output is correct
14 Correct 6 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Runtime error 2 ms 624 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Runtime error 1 ms 596 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 212 KB Output is correct
2 Correct 9 ms 212 KB Output is correct
3 Correct 33 ms 468 KB Output is correct
4 Correct 34 ms 432 KB Output is correct
5 Correct 8 ms 372 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 24 ms 424 KB Output is correct
12 Correct 22 ms 340 KB Output is correct
13 Correct 11 ms 368 KB Output is correct
14 Correct 6 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Execution timed out 3081 ms 4648 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 212 KB Output is correct
2 Correct 9 ms 212 KB Output is correct
3 Correct 33 ms 468 KB Output is correct
4 Correct 34 ms 432 KB Output is correct
5 Correct 8 ms 372 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 24 ms 424 KB Output is correct
12 Correct 22 ms 340 KB Output is correct
13 Correct 11 ms 368 KB Output is correct
14 Correct 6 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Execution timed out 3081 ms 4648 KB Time limit exceeded
19 Halted 0 ms 0 KB -