oj.uz

Submission #704110

# Submission time Handle Problem Language Result Execution time Memory
704110 2023-03-01T15:25:01 Z Cyanmond Land of the Rainbow Gold (APIO17_rainbow) C++17
23 / 100
 3000 ms 365288 KB 
#include "rainbow.h"
#include <bits/stdc++.h>

void iterate(std::pair<int, int> &x, char c) {
    if (c == 'N') {
        --x.first;
    }
    if (c == 'S') {
        ++x.first;
    }
    if (c == 'E') {
        ++x.second;
    }
    if (c == 'W') {
        --x.second;
    }
}

struct UnionFind {
    int n;
    std::vector<int> data;
    int components;

    UnionFind(int n_) : n(n_), data(n, -1), components(n) {}

    int find(int v) {
        if (data[v] < 0) {
            return v;
        } else {
            return data[v] = find(data[v]);
        }
    }

    void merge(int a, int b) {
        a = find(a);
        b = find(b);
        if (a == b) {
            return;
        }
        if (data[a] > data[b]) {
            std::swap(a, b);
        }
        data[a] += data[b];
        data[b] = a;
        --components;
    }

    int countGroups() {
        return components;
    }
};

int R, C, sR, sC, M;
int msR;
std::string S;
int T;
std::map<std::pair<int, int>, bool> dataMap;
std::array<std::vector<std::pair<int, int>>, 2> landRanges;
std::vector<std::pair<int, int>> vxRanges;

void init(int r, int c, int sr, int sc, int m, char *s) {
    --sr, --sc;
    R = r;
    C = c;
    sR = sr;
    sC = sc;
    msR = sr;
    M = m;
    S.resize(M);
    for (int i = 0; i < M; ++i) {
        S[i] = s[i];
    }

    // check...
    if (R == 2) {
        T = 2;
    } else if (R <= 50 and C <= 50) {
        T = 1;
    } else {
        T = 3;
    }

    auto add = [&](const std::pair<int, int> &v, bool type) {
        if (type) {
            dataMap[v] = true;
        } else {
            if (dataMap.find(v) == dataMap.end()) {
                dataMap[v] = false;
            }
        }
    };
    std::pair<int, int> p = {sR, sC};
    if (T == 2) {
        add(p, true);
        for (int i = 0; i < M; ++i) {
            iterate(p, S[i]);
            add(p, true);
        };
        for (int x = 0; x < 2; ++x) {
            int l = 0;
            for (int i = 0; i < C; ++i) {
                if (dataMap[{x, i}]) {
                    if (l != i) {
                        landRanges[x].push_back({l, i - l});
                    }
                    l = i + 1;
                }
            }
            if (l != C) {
                landRanges[x].push_back({l, C - l});
            }
        }
        int l = 0;
        for (int i = 0; i < C; ++i) {
            if (dataMap[{0, i}] and dataMap[{1, i}]) {
                if (l != i) {
                    vxRanges.push_back({l, i - l});
                }
                l = i + 1;
            }
        }
        if (l != C) {
            vxRanges.push_back({l, C - l});
        }
    } else {
        auto addBlock = [&](const std::pair<int, int> &v) {
            add(v, true);
            for (int ax = -1; ax <= 1; ++ax) {
                for (int ay = -1; ay <= 1; ++ay) {
                    if (ax != 0 and ay != 0) {
                        continue;
                    }
                    if (ax == 0 and ay == 0) {
                        continue;
                    }
                    if (v.first + ax < 0 or v.first + ax >= R or v.second + ay < 0 or v.second + ay >= C) {
                        continue;
                    }
                    add({v.first + ax, v.second + ay}, false);
                }
            }
        };
        addBlock(p);
        for (int i = 0; i < M; ++i) {
            iterate(p, S[i]);
            addBlock(p);
        }

        for (int i = 0; i < R; ++i) for (int j = 0; j < C; ++j) add({i, j}, false);
    }
}

int colour(int ar, int ac, int br, int bc) {
    --ar, --ac;
    if (T == 2) {
        const auto &ranges = (br - ar != 2 ? landRanges[ar] : vxRanges);
        auto itr = std::lower_bound(ranges.begin(), ranges.end(), std::make_pair(ac, 0));
        if (itr != ranges.begin()) {
            --itr;
            if (itr->first + itr->second <= ac) {
                ++itr;
            }
        }
        auto itr2 = std::lower_bound(ranges.begin(), ranges.end(), std::make_pair(bc, 0));
        return itr2 - itr;
    } else {
        auto add = [&](const std::pair<int, int> &v, bool type) {
            if (type) {
                dataMap[v] = true;
            } else {
                if (dataMap.find(v) == dataMap.end()) {
                    dataMap[v] = false;
                }
            }
        };
        for (int i = ac; i <= bc; ++i) {
            add({ar, i}, false);
            add({br - 1, i}, false);
            add({msR, i}, false);
        }
        for (int i = ar; i <= br; ++i) {
            add({i, ac}, false);
            add({i, bc - 1}, false);
        }
        std::map<std::pair<int, int>, int> blockId;
        int id = 0;
        int countRiver = 0;
        for (const auto &[pos, type] : dataMap) {
            const auto &[x, y] = pos;
            if (ar <= x and x < br and ac <= y and y < bc) {
                blockId[pos] = id++;
                if (type) {
                    ++countRiver;
                }
            }
        }
        UnionFind uft(id);
        for (const auto &[p, i] : blockId) {
            if (dataMap[p]) {
                continue;
            }
            const auto &[x, y] = p;
            for (int ax = -1; ax <= 1; ++ax) {
                for (int ay = -1; ay <= 1; ++ay) {
                    if (ax != 0 and ay != 0) {
                        continue;
                    }
                    if (ax == 0 and ay == 0) {
                        continue;
                    }
                    const int nx = x + ax, ny = y + ay;
                    auto itr = blockId.find({nx, ny});
                    if (itr == blockId.end()) {
                        continue;
                    }
                    if (not dataMap[itr->first]) {
                        uft.merge(i, itr->second);
                    }
                }
            }
        }

        return uft.countGroups() - countRiver;
    }
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 340 KB Output is correct
2 Correct 186 ms 628 KB Output is correct
3 Correct 500 ms 628 KB Output is correct
4 Correct 514 ms 616 KB Output is correct
5 Correct 208 ms 628 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 437 ms 648 KB Output is correct
12 Correct 361 ms 644 KB Output is correct
13 Correct 316 ms 624 KB Output is correct
14 Correct 239 ms 624 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 0 ms 212 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 185 ms 26664 KB Output is correct
4 Correct 200 ms 26256 KB Output is correct
5 Correct 205 ms 26436 KB Output is correct
6 Correct 213 ms 26520 KB Output is correct
7 Correct 231 ms 26824 KB Output is correct
8 Correct 194 ms 26144 KB Output is correct
9 Correct 195 ms 26584 KB Output is correct
10 Correct 195 ms 26412 KB Output is correct
11 Correct 220 ms 26828 KB Output is correct
12 Correct 188 ms 26220 KB Output is correct
13 Correct 181 ms 26636 KB Output is correct
14 Correct 184 ms 26788 KB Output is correct
15 Correct 212 ms 26872 KB Output is correct
16 Correct 184 ms 26556 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Execution timed out 3044 ms 365288 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 340 KB Output is correct
2 Correct 186 ms 628 KB Output is correct
3 Correct 500 ms 628 KB Output is correct
4 Correct 514 ms 616 KB Output is correct
5 Correct 208 ms 628 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 437 ms 648 KB Output is correct
12 Correct 361 ms 644 KB Output is correct
13 Correct 316 ms 624 KB Output is correct
14 Correct 239 ms 624 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Execution timed out 3032 ms 101220 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 340 KB Output is correct
2 Correct 186 ms 628 KB Output is correct
3 Correct 500 ms 628 KB Output is correct
4 Correct 514 ms 616 KB Output is correct
5 Correct 208 ms 628 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 437 ms 648 KB Output is correct
12 Correct 361 ms 644 KB Output is correct
13 Correct 316 ms 624 KB Output is correct
14 Correct 239 ms 624 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Execution timed out 3032 ms 101220 KB Time limit exceeded
19 Halted 0 ms 0 KB -