oj.uz

Submission #1116770

# Submission time Handle Problem Language Result Execution time Memory
1116770 2024-11-22T10:59:19 Z OI_Account Land of the Rainbow Gold (APIO17_rainbow) C++17
23 / 100
 3000 ms 36280 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++)
        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:163: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]
  163 |     return idx < gv3.size() && gv3[idx] == make_pair(x, y)? idx: -1;
      |            ~~~~^~~~~~~~~~~~
rainbow.cpp: In function 'int solveSub3()':
rainbow.cpp:195: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]
  195 |     for (int i = 0; i < gv3.size(); i++)
      |                     ~~^~~~~~~~~~~~
rainbow.cpp: In function 'void init(int, int, int, int, int, char*)':
rainbow.cpp:109:45: warning: 'idx' may be used uninitialized in this function [-Wmaybe-uninitialized]
  109 |         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 508 KB Output is correct
3 Correct 59 ms 592 KB Output is correct
4 Correct 57 ms 612 KB Output is correct
5 Correct 44 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 504 KB Output is correct
10 Correct 1 ms 504 KB Output is correct
11 Correct 48 ms 584 KB Output is correct
12 Correct 49 ms 584 KB Output is correct
13 Correct 75 ms 336 KB Output is correct
14 Correct 62 ms 544 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 123 ms 29048 KB Output is correct
4 Correct 122 ms 23852 KB Output is correct
5 Correct 124 ms 25276 KB Output is correct
6 Correct 126 ms 31408 KB Output is correct
7 Correct 126 ms 32188 KB Output is correct
8 Correct 75 ms 23728 KB Output is correct
9 Correct 118 ms 23996 KB Output is correct
10 Correct 166 ms 25276 KB Output is correct
11 Correct 145 ms 31560 KB Output is correct
12 Correct 106 ms 23368 KB Output is correct
13 Correct 102 ms 24008 KB Output is correct
14 Correct 107 ms 25276 KB Output is correct
15 Correct 121 ms 31420 KB Output is correct
16 Correct 117 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 223 ms 36280 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 508 KB Output is correct
3 Correct 59 ms 592 KB Output is correct
4 Correct 57 ms 612 KB Output is correct
5 Correct 44 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 504 KB Output is correct
10 Correct 1 ms 504 KB Output is correct
11 Correct 48 ms 584 KB Output is correct
12 Correct 49 ms 584 KB Output is correct
13 Correct 75 ms 336 KB Output is correct
14 Correct 62 ms 544 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 3058 ms 12660 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 508 KB Output is correct
3 Correct 59 ms 592 KB Output is correct
4 Correct 57 ms 612 KB Output is correct
5 Correct 44 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 504 KB Output is correct
10 Correct 1 ms 504 KB Output is correct
11 Correct 48 ms 584 KB Output is correct
12 Correct 49 ms 584 KB Output is correct
13 Correct 75 ms 336 KB Output is correct
14 Correct 62 ms 544 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 3058 ms 12660 KB Time limit exceeded
19 Halted 0 ms 0 KB -