oj.uz

Submission #887735

# Submission time Handle Problem Language Result Execution time Memory
887735 2023-12-15T06:25:26 Z hamidh100 Land of the Rainbow Gold (APIO17_rainbow) C++17
11 / 100
 29 ms 964 KB 
#include "rainbow.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;
typedef vector<int> VI;
typedef vector<ll> VL;
#define PB push_back
#define MP make_pair
#define all(a) (a).begin(), (a).end()
#define endl '\n'
#define dbg(x) cerr << '[' << #x << ": " << x << "]\n"
#define dbg2(x, y) cerr << '[' << #x << ": " << x << ", " << #y << ": " << y << "]\n"
#define YES cout << "YES\n"
#define NO cout << "NO\n"

const ll INF = (ll)2e18 + 1386;
const ld EPS = 0.000000000000001;
const int MOD = 1e9 + 7;

inline int _add(int a, int b){ int res = a + b; return (res >= MOD ? res - MOD : res); }
inline int _neg(int a, int b){ int res = (abs(a - b) < MOD ? a - b : (a - b) % MOD); return (res < 0 ? res + MOD : res); }
inline int _mlt(ll a, ll b){ return (a * b % MOD); }
inline void fileIO(string i, string o){ freopen(i.c_str(), "r", stdin); freopen(o.c_str(), "w", stdout); }

const int MAXN = 51;

int par[MAXN * MAXN], n, m;
int a[MAXN][MAXN];

inline int c(int x, int y){ return (x - 1) * m + y; }

int getpar(int v){
    return par[v] == v ? v : par[v] = getpar(par[v]);
}

void merge(int u, int v){
    u = getpar(u), v = getpar(v);
    par[u] = v;
}

void init(int R, int C, int sr, int sc, int M, char *S) {
    n = R, m = C;
    iota(par, par + R * C + 1, 0);
    a[sr][sc] = 1;
    for (int i = 0; i < M; i++){
        char ch = S[i];
        if (ch == 'N') a[--sr][sc] = 1;
        else if (ch == 'S') a[++sr][sc] = 1;
        else if (ch == 'E') a[sr][++sc] = 1;
        else a[sr][--sc] = 1;
    }
}

int dx[] = {0, 0, +1, -1};
int dy[] = {+1, -1, 0, 0};

int colour(int ar, int ac, int br, int bc) {
    for (int i = ar; i <= br; i++){
        for (int j = ac; j <= bc; j++){
            if (a[i][j] == 1) continue;
            for (int ii = 0; ii < 4; ii++){
                int x = i + dx[ii], y = j + dy[ii];
                if (x >= ar && x <= br && y >= ac && y <= bc && a[x][y] == 0){
                    merge(c(i, j), c(x, y));
                }
            }
        }
    }
    set<int> st;
    for (int i = ar; i <= br; i++){
        for (int j = ac; j <= bc; j++){
            if (a[i][j] == 0) st.insert(getpar(c(i, j)));
        }
    }
    for (int i = ar; i <= br; i++){
        for (int j = ac; j <= bc; j++){
            par[c(i, j)] = c(i, j);
        }
    }
    return (int)st.size();
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 348 KB Output is correct
2 Correct 12 ms 348 KB Output is correct
3 Correct 29 ms 348 KB Output is correct
4 Correct 29 ms 480 KB Output is correct
5 Correct 9 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 24 ms 348 KB Output is correct
12 Correct 21 ms 348 KB Output is correct
13 Correct 11 ms 496 KB Output is correct
14 Correct 11 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Runtime error 1 ms 860 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 348 KB Output is correct
2 Runtime error 1 ms 604 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 3 ms 348 KB Output is correct
2 Correct 12 ms 348 KB Output is correct
3 Correct 29 ms 348 KB Output is correct
4 Correct 29 ms 480 KB Output is correct
5 Correct 9 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 24 ms 348 KB Output is correct
12 Correct 21 ms 348 KB Output is correct
13 Correct 11 ms 496 KB Output is correct
14 Correct 11 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Runtime error 1 ms 964 KB Execution killed with signal 11
19 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 348 KB Output is correct
2 Correct 12 ms 348 KB Output is correct
3 Correct 29 ms 348 KB Output is correct
4 Correct 29 ms 480 KB Output is correct
5 Correct 9 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 24 ms 348 KB Output is correct
12 Correct 21 ms 348 KB Output is correct
13 Correct 11 ms 496 KB Output is correct
14 Correct 11 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Runtime error 1 ms 964 KB Execution killed with signal 11
19 Halted 0 ms 0 KB -