oj.uz

Submission #747880

# Submission time Handle Problem Language Result Execution time Memory
747880 2023-05-25T04:36:29 Z vjudge1 Land of the Rainbow Gold (APIO17_rainbow) C++17
23 / 100
 3000 ms 1048576 KB 
#include "rainbow.h"
#include <bits/stdc++.h>
using namespace std;
vector<vector<bool>> b;
vector<int> p, cnt1, cnt2, cnt3;
int n, m;
void init2() {
    cnt1 = cnt2 = cnt3 = vector<int>(m, 0);
    cnt1[0] = !b[0][0];
    cnt2[0] = !b[1][0];
    cnt3[0] = cnt1[0] | cnt2[0];
    for (int i = 1; i < m; ++i) {
        cnt1[i] = cnt1[i - 1] + (!b[0][i] && b[0][i - 1]);
        cnt2[i] = cnt2[i - 1] + (!b[1][i] && b[1][i - 1]);
        if (!b[0][i] && !b[1][i])
            cnt3[i] = cnt3[i - 1] + (b[0][i - 1] && b[1][i - 1]);
        else
            cnt3[i] = cnt3[i - 1] + (!b[0][i] && b[0][i - 1]) + (!b[1][i] && b[1][i - 1]);
    }
}
void init(int R, int C, int sr, int sc, int M, char *S) {
    n = R, m = C;
    b.assign(R, vector<bool>(C, false));
    --sr, --sc;
    b[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;
        b[sr][sc] = true;
    }
    if (n == 2) init2();
    p.resize(R * C);
}
int colour2(int ar, int ac, int br, int bc) {
    --ar, --ac, --br, --bc;
    if (ar == 1) return cnt2[bc] - cnt2[ac] + (!b[1][ac]);
    if (br == 0) return cnt1[bc] - cnt1[ac] + (!b[0][ac]);
    return cnt3[bc] - cnt3[ac] + (!b[0][ac] || !b[1][ac]);
}
int colour(int ar, int ac, int br, int bc) {
    if (n == 2) return colour2(ar, ac, br, bc);
    --ar, --ac;
    for (int i = ar; i < br; ++i) for (int j = ac; j < bc; ++j)
        p[i * m + j] = i * m + j;
    function<int(int)> find = [&](int i) {
        return p[i] = p[i] == i ? i : find(p[i]);
    };
    for (int i = ar; i < br; ++i) for (int j = ac; j < bc; ++j) if (!b[i][j]) {
        if (i < br - 1 && !b[i + 1][j])
            p[find(i * m + j)] = find((i + 1) * m + j);
        if (j < bc - 1 && !b[i][j + 1])
            p[find(i * m + j)] = find(i * m + j + 1);
    }
    int ans = 0;
    for (int i = ar; i < br; ++i) for (int j = ac; j < bc; ++j) if (!b[i][j])
        ans += find(i * m + j) == i * m + j;
    return ans;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 324 KB Output is correct
2 Correct 22 ms 352 KB Output is correct
3 Correct 87 ms 340 KB Output is correct
4 Correct 86 ms 340 KB Output is correct
5 Correct 20 ms 364 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 256 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 308 KB Output is correct
11 Correct 62 ms 464 KB Output is correct
12 Correct 48 ms 340 KB Output is correct
13 Correct 19 ms 324 KB Output is correct
14 Correct 8 ms 320 KB Output is correct
15 Correct 1 ms 312 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 1 ms 212 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 55 ms 7868 KB Output is correct
4 Correct 56 ms 7872 KB Output is correct
5 Correct 54 ms 7888 KB Output is correct
6 Correct 54 ms 7928 KB Output is correct
7 Correct 54 ms 7904 KB Output is correct
8 Correct 51 ms 7880 KB Output is correct
9 Correct 54 ms 8016 KB Output is correct
10 Correct 54 ms 7932 KB Output is correct
11 Correct 59 ms 7856 KB Output is correct
12 Correct 51 ms 7924 KB Output is correct
13 Correct 50 ms 7916 KB Output is correct
14 Correct 50 ms 7844 KB Output is correct
15 Correct 50 ms 7900 KB Output is correct
16 Correct 54 ms 7888 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 312 KB Output is correct
2 Runtime error 441 ms 1048576 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 324 KB Output is correct
2 Correct 22 ms 352 KB Output is correct
3 Correct 87 ms 340 KB Output is correct
4 Correct 86 ms 340 KB Output is correct
5 Correct 20 ms 364 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 256 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 308 KB Output is correct
11 Correct 62 ms 464 KB Output is correct
12 Correct 48 ms 340 KB Output is correct
13 Correct 19 ms 324 KB Output is correct
14 Correct 8 ms 320 KB Output is correct
15 Correct 1 ms 312 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Execution timed out 3034 ms 4692 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 324 KB Output is correct
2 Correct 22 ms 352 KB Output is correct
3 Correct 87 ms 340 KB Output is correct
4 Correct 86 ms 340 KB Output is correct
5 Correct 20 ms 364 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 256 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 308 KB Output is correct
11 Correct 62 ms 464 KB Output is correct
12 Correct 48 ms 340 KB Output is correct
13 Correct 19 ms 324 KB Output is correct
14 Correct 8 ms 320 KB Output is correct
15 Correct 1 ms 312 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Execution timed out 3034 ms 4692 KB Time limit exceeded
19 Halted 0 ms 0 KB -