oj.uz

Submission #1116771

# Submission time Handle Problem Language Result Execution time Memory
1116771 2024-11-22T11:00:23 Z OI_Account Land of the Rainbow Gold (APIO17_rainbow) C++17
23 / 100
 3000 ms 36148 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 = 10'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});
            }
    }
    for (int i = 1; i <= a; i++)
        if (!inPath(i, 1))  
            vec3.push_back({i, 1});
    for (int j = 1; j <= b; j++)
        if (!inPath(a, j))
            vec3.push_back({a, j});
    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:164: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]
  164 |     return idx < gv3.size() && gv3[idx] == make_pair(x, y)? idx: -1;
      |            ~~~~^~~~~~~~~~~~
rainbow.cpp: In function 'int solveSub3()':
rainbow.cpp:196: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]
  196 |     for (int i = 0; i < gv3.size(); i++)
      |                     ~~^~~~~~~~~~~~
rainbow.cpp: In function 'void init(int, int, int, int, int, char*)':
rainbow.cpp:110:45: warning: 'idx' may be used uninitialized in this function [-Wmaybe-uninitialized]
  110 |         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 41 ms 500 KB Output is correct
3 Correct 59 ms 592 KB Output is correct
4 Correct 60 ms 612 KB Output is correct
5 Correct 39 ms 540 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 47 ms 584 KB Output is correct
12 Correct 49 ms 572 KB Output is correct
13 Correct 87 ms 548 KB Output is correct
14 Correct 63 ms 336 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 29068 KB Output is correct
4 Correct 124 ms 23996 KB Output is correct
5 Correct 130 ms 25276 KB Output is correct
6 Correct 123 ms 31420 KB Output is correct
7 Correct 128 ms 32188 KB Output is correct
8 Correct 71 ms 23740 KB Output is correct
9 Correct 136 ms 23836 KB Output is correct
10 Correct 126 ms 25208 KB Output is correct
11 Correct 129 ms 31420 KB Output is correct
12 Correct 102 ms 23328 KB Output is correct
13 Correct 101 ms 23824 KB Output is correct
14 Correct 107 ms 25276 KB Output is correct
15 Correct 115 ms 31396 KB Output is correct
16 Correct 115 ms 27580 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 213 ms 36148 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 41 ms 500 KB Output is correct
3 Correct 59 ms 592 KB Output is correct
4 Correct 60 ms 612 KB Output is correct
5 Correct 39 ms 540 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 47 ms 584 KB Output is correct
12 Correct 49 ms 572 KB Output is correct
13 Correct 87 ms 548 KB Output is correct
14 Correct 63 ms 336 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 3043 ms 12480 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 41 ms 500 KB Output is correct
3 Correct 59 ms 592 KB Output is correct
4 Correct 60 ms 612 KB Output is correct
5 Correct 39 ms 540 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 47 ms 584 KB Output is correct
12 Correct 49 ms 572 KB Output is correct
13 Correct 87 ms 548 KB Output is correct
14 Correct 63 ms 336 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 3043 ms 12480 KB Time limit exceeded
19 Halted 0 ms 0 KB -