oj.uz

Submission #1116753

# Submission time Handle Problem Language Result Execution time Memory
1116753 2024-11-22T10:34:14 Z OI_Account Land of the Rainbow Gold (APIO17_rainbow) C++17
12 / 100
 139 ms 28464 KB 
#include "rainbow.h"
#include <bits/stdc++.h>
using namespace std;

const int N = 200'000;
const int D = 4;
const int DX[D] = {0, 0, -1, 1};
const int DY[D] = {-1, 1, 0, 0};

int n, m, a, b, x1, yyy, x2, y2;
vector<pair<int, int>> path;
vector<char> vecDir = {'W', 'E', 'N', 'S'};
int markSub1[60][60], cnt[3][N + 10], cmpSub2;
int markSub2[3][N + 10], valSub2[N + 10];

void uniquePath() {
    sort(path.begin(), path.end());
    path.resize(unique(path.begin(), path.end()) - path.begin());
}

bool isSub1() {
    return max(n, m) <= 50;
}

bool inPath(int x, int y) {
    int idx = lower_bound(path.begin(), path.end(), make_pair(x, y)) - path.begin();
    return idx < path.size() && path[idx] == make_pair(x, y);
}

bool inSub(int a, int b) {
    bool checkA = (x1 <= a && a <= x2);
    bool checkB = (yyy <= b && b <= y2);
    return checkA && checkB;
}

void initSub1() {
    uniquePath();
}

bool isSub2() {
    return n <= 2 && m <= N;
}

bool inGrid(int x, int y) {
    return min(x, y) >= 1 && x <= n && y <= m;
}

void dfs2(int i, int j) {
    markSub2[i][j] = cmpSub2;
    for (int d = 0; d < D; d++) {
        int nx = i + DX[d];
        int ny = j + DY[d];
        if (inGrid(nx, ny) && !inPath(nx, ny) && !markSub2[nx][ny])
            dfs2(nx, ny);
    }
}

void initSub2() {
    uniquePath();
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) {
            cnt[i][j] = cnt[i][j - 1];
            if ((j == 1 || inPath(i, j - 1)) && !inPath(i, j))
                cnt[i][j]++;
        }
    for (int j = 1; j <= m; j++) {
        for (int i = 1; i <= n; i++)
            if (!inPath(i, j) && !markSub2[i][j]) {
                cmpSub2++;
                dfs2(i, j);
            }
        valSub2[j] = cmpSub2;
    }
}

void init(int R, int C, int sr, int sc, int M, char *S) {
    n = R;
    m = C;
    a = sr;
    b = sc;
    path.push_back({a, b});
    for (int i = 0; i < M; i++) {
        int idx;
        for (int j = 0; j < D; j++)
            if (S[i] == vecDir[j])
                idx = j;
        int nx = path.back().first + DX[idx];
        int ny = path.back().second + DY[idx];
        path.push_back({nx, ny});
    }
    /*if (isSub1())
        initSub1();
    else */if (isSub2())
        initSub2();
}

void dfs(int i, int j) {
    markSub1[i][j] = true;
    for (int d = 0; d < D; d++) {
        int nx = i + DX[d];
        int ny = j + DY[d];
        if (inSub(nx, ny) && !inPath(nx, ny) && !markSub1[nx][ny])
            dfs(nx, ny);
    }
}

int solveSub1() {
    for (int i = x1; i <= x2; i++)  
        for (int j = yyy; j <= y2; j++)
            markSub1[i][j] = 0;
    int ans = 0;
    for (int i = x1; i <= x2; i++)
        for (int j = yyy; j <= y2; j++)
            if (!inPath(i, j) && !markSub1[i][j]) {
                ans++;
                dfs(i, j);
            }
    return ans;
}

int solveSub2() {
    if (x1 == x2)
        return cnt[x2][y2] - cnt[x2][yyy] + (!inPath(x2, yyy));
    bool add = false;
    for (int i = 1; i <= n; i++)
        if (!inPath(i, yyy))
            add = true;
    return valSub2[y2] - valSub2[yyy] + add;
}

int colour(int ar, int ac, int br, int bc) {
    x1 = ar;
    yyy = ac;
    x2 = br;
    y2 = bc;
    /*if (isSub1())
        return solveSub1();*/
    if (isSub2())
        return solveSub2();
    return 0;
}

Compilation message

rainbow.cpp: In function 'bool inPath(int, int)':
rainbow.cpp:27:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |     return idx < path.size() && path[idx] == make_pair(x, y);
      |            ~~~~^~~~~~~~~~~~~
rainbow.cpp: In function 'void init(int, int, int, int, int, char*)':
rainbow.cpp:88:45: warning: 'idx' may be used uninitialized in this function [-Wmaybe-uninitialized]
   88 |         int ny = path.back().second + DY[idx];
      |                                       ~~~~~~^

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 336 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 130 ms 22720 KB Output is correct
4 Correct 130 ms 21632 KB Output is correct
5 Correct 136 ms 22716 KB Output is correct
6 Correct 117 ms 27588 KB Output is correct
7 Correct 137 ms 28464 KB Output is correct
8 Correct 85 ms 21312 KB Output is correct
9 Correct 139 ms 21928 KB Output is correct
10 Correct 118 ms 22628 KB Output is correct
11 Correct 124 ms 27580 KB Output is correct
12 Correct 103 ms 21144 KB Output is correct
13 Correct 97 ms 21524 KB Output is correct
14 Correct 101 ms 22460 KB Output is correct
15 Correct 110 ms 27588 KB Output is correct
16 Correct 115 ms 24252 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Incorrect 3 ms 1480 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 336 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 336 KB Output isn't correct
2 Halted 0 ms 0 KB -