oj.uz

Submission #1116766

# Submission time Handle Problem Language Result Execution time Memory
1116766 2024-11-22T10:54:04 Z OI_Account Land of the Rainbow Gold (APIO17_rainbow) C++17
23 / 100
 3000 ms 30652 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};
const int S3 = 4'000'000;

int n, m, a, b, x1, yyy, x2, y2;
vector<pair<int, int>> path, vec3, gv3;
vector<char> vecDir = {'W', 'E', 'N', 'S'};
int markSub1[60][60], cnt[3][N + 10], cmpSub2;
int markSub2[3][N + 10], valSub2[N + 10], mark3[S3 + 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 initSub3() {
    uniquePath();
    for (auto [x, y]: path) {
        for (int i = -2; i <= 2; i++)
            for (int j = -2; j <= 2; j++) {
                int nx = x + i, ny = y + j;
                if (inGrid(nx, ny) && !inPath(nx, ny))
                    vec3.push_back({nx, ny});
            }
    }
    sort(vec3.begin(), vec3.end());
    vec3.resize(unique(vec3.begin(), vec3.end()) - vec3.begin());
}

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();
    else
        initSub3();
}

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;
}

void calcGV3() {
    gv3.clear();
    for (auto [x, y]: vec3)
        if (inSub(x, y))
            gv3.push_back({x, y});
}

int inGV3(int x, int y) {
    int idx = lower_bound(gv3.begin(), gv3.end(), make_pair(x, y)) - gv3.begin();
    return idx < gv3.size() && gv3[idx] == make_pair(x, y)? idx: -1;
}

void dfs3(int i, int j, int id) {
    mark3[id] = true;
    for (int d = 0; d < D; d++) {
        int nx = i + DX[d];
        int ny = j + DY[d];
        int nId = inGV3(nx, ny);
        if (nId != -1 && !mark3[nId])
            dfs3(nx, ny, nId);
    }
}

int solveSub3() {
    calcGV3();
    for (int i = x1; i <= x2; i++) {
        gv3.push_back({i, yyy});
        gv3.push_back({i, y2});
    }
    for (int i = yyy; i <= y2; i++) {
        gv3.push_back({x1, i});
        gv3.push_back({x2, i});
    }
    sort(gv3.begin(), gv3.end());
    gv3.resize(unique(gv3.begin(), gv3.end()) - gv3.begin());
    vector<pair<int, int>> vec;
    for (auto [x, y]: vec)
        if (!inPath(x, y))
            vec.push_back({x, y});
    gv3 = vec;
    int ans = 0;
    for (int i = 0; i < gv3.size(); i++)
        if (!mark3[i]) {
            ans++;
            dfs3(gv3[i].first, gv3[i].second, i);
        }
    fill(mark3, mark3 + gv3.size(), 0);
    return ans;
}

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 solveSub3();
}

Compilation message

rainbow.cpp: In function 'bool inPath(int, int)':
rainbow.cpp:29: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]
   29 |     return idx < path.size() && path[idx] == make_pair(x, y);
      |            ~~~~^~~~~~~~~~~~~
rainbow.cpp: In function 'int inGV3(int, int)':
rainbow.cpp:158: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]
  158 |     return idx < gv3.size() && gv3[idx] == make_pair(x, y)? idx: -1;
      |            ~~~~^~~~~~~~~~~~
rainbow.cpp: In function 'int solveSub3()':
rainbow.cpp:190:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  190 |     for (int i = 0; i < gv3.size(); i++)
      |                     ~~^~~~~~~~~~~~
rainbow.cpp: In function 'void init(int, int, int, int, int, char*)':
rainbow.cpp:104:45: warning: 'idx' may be used uninitialized in this function [-Wmaybe-uninitialized]
  104 |         int ny = path.back().second + DY[idx];
      |                                       ~~~~~~^

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 336 KB Output is correct
2 Correct 44 ms 504 KB Output is correct
3 Correct 59 ms 764 KB Output is correct
4 Correct 58 ms 592 KB Output is correct
5 Correct 42 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 48 ms 580 KB Output is correct
12 Correct 57 ms 580 KB Output is correct
13 Correct 75 ms 336 KB Output is correct
14 Correct 66 ms 532 KB Output is correct
15 Correct 1 ms 336 KB Output is correct
16 Correct 1 ms 336 KB Output is correct
17 Correct 1 ms 336 KB Output is correct

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 119 ms 28456 KB Output is correct
4 Correct 139 ms 23208 KB Output is correct
5 Correct 158 ms 24508 KB Output is correct
6 Correct 144 ms 30652 KB Output is correct
7 Correct 143 ms 30396 KB Output is correct
8 Correct 71 ms 22972 KB Output is correct
9 Correct 127 ms 23228 KB Output is correct
10 Correct 137 ms 24532 KB Output is correct
11 Correct 130 ms 30652 KB Output is correct
12 Correct 119 ms 22620 KB Output is correct
13 Correct 103 ms 23136 KB Output is correct
14 Correct 109 ms 24508 KB Output is correct
15 Correct 125 ms 30652 KB Output is correct
16 Correct 127 ms 26564 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 201 ms 25632 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 336 KB Output is correct
2 Correct 44 ms 504 KB Output is correct
3 Correct 59 ms 764 KB Output is correct
4 Correct 58 ms 592 KB Output is correct
5 Correct 42 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 48 ms 580 KB Output is correct
12 Correct 57 ms 580 KB Output is correct
13 Correct 75 ms 336 KB Output is correct
14 Correct 66 ms 532 KB Output is correct
15 Correct 1 ms 336 KB Output is correct
16 Correct 1 ms 336 KB Output is correct
17 Correct 1 ms 336 KB Output is correct
18 Execution timed out 3055 ms 12668 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 336 KB Output is correct
2 Correct 44 ms 504 KB Output is correct
3 Correct 59 ms 764 KB Output is correct
4 Correct 58 ms 592 KB Output is correct
5 Correct 42 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 48 ms 580 KB Output is correct
12 Correct 57 ms 580 KB Output is correct
13 Correct 75 ms 336 KB Output is correct
14 Correct 66 ms 532 KB Output is correct
15 Correct 1 ms 336 KB Output is correct
16 Correct 1 ms 336 KB Output is correct
17 Correct 1 ms 336 KB Output is correct
18 Execution timed out 3055 ms 12668 KB Time limit exceeded
19 Halted 0 ms 0 KB -