Submission #1116770

#	Time	Username	Problem	Language	Result	Execution time	Memory
1116770		OI_Account	Land of the Rainbow Gold (APIO17_rainbow)	C++17	23 / 100	3058 ms	36280 KiB

rainbow

#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 (stderr)

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 / 11
• Subtask 2: 12 / 12
• Subtask 3: 0 / 24
• Subtask 4: 0 / 27
• Subtask 5: 0 / 26