oj.uz

Submission #408626

# Submission time Handle Problem Language Result Execution time Memory
408626 2021-05-19T09:59:28 Z syl123456 Land of the Rainbow Gold (APIO17_rainbow) C++17
23 / 100
 3000 ms 1048580 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;
    int _ = 0;
    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;
}
/*
 * Q(NlogM + MlogN)logMN + NMlogNlogM
 *                         ^
 *                         |
 *                      uni-sort
 * QNlogNlogM
 */

Compilation message

rainbow.cpp: In function 'int colour(int, int, int, int)':
rainbow.cpp:46:9: warning: unused variable '_' [-Wunused-variable]
   46 |     int _ = 0;
      |         ^

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 204 KB Output is correct
2 Correct 24 ms 316 KB Output is correct
3 Correct 97 ms 292 KB Output is correct
4 Correct 97 ms 204 KB Output is correct
5 Correct 23 ms 332 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 70 ms 292 KB Output is correct
12 Correct 54 ms 204 KB Output is correct
13 Correct 22 ms 204 KB Output is correct
14 Correct 9 ms 316 KB Output is correct
15 Correct 1 ms 204 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 1 ms 204 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 64 ms 5032 KB Output is correct
4 Correct 62 ms 5056 KB Output is correct
5 Correct 69 ms 4984 KB Output is correct
6 Correct 70 ms 5056 KB Output is correct
7 Correct 65 ms 4996 KB Output is correct
8 Correct 68 ms 4980 KB Output is correct
9 Correct 68 ms 5052 KB Output is correct
10 Correct 68 ms 4956 KB Output is correct
11 Correct 62 ms 5032 KB Output is correct
12 Correct 61 ms 5056 KB Output is correct
13 Correct 58 ms 5060 KB Output is correct
14 Correct 57 ms 5072 KB Output is correct
15 Correct 58 ms 5048 KB Output is correct
16 Correct 63 ms 4988 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Runtime error 447 ms 1048580 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 5 ms 204 KB Output is correct
2 Correct 24 ms 316 KB Output is correct
3 Correct 97 ms 292 KB Output is correct
4 Correct 97 ms 204 KB Output is correct
5 Correct 23 ms 332 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 70 ms 292 KB Output is correct
12 Correct 54 ms 204 KB Output is correct
13 Correct 22 ms 204 KB Output is correct
14 Correct 9 ms 316 KB Output is correct
15 Correct 1 ms 204 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Execution timed out 3063 ms 4500 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 204 KB Output is correct
2 Correct 24 ms 316 KB Output is correct
3 Correct 97 ms 292 KB Output is correct
4 Correct 97 ms 204 KB Output is correct
5 Correct 23 ms 332 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 70 ms 292 KB Output is correct
12 Correct 54 ms 204 KB Output is correct
13 Correct 22 ms 204 KB Output is correct
14 Correct 9 ms 316 KB Output is correct
15 Correct 1 ms 204 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Execution timed out 3063 ms 4500 KB Time limit exceeded
19 Halted 0 ms 0 KB -