oj.uz

Submission #704112

# Submission time Handle Problem Language Result Execution time Memory
704112 2023-03-01T15:32:31 Z Cyanmond Land of the Rainbow Gold (APIO17_rainbow) C++17
23 / 100
 3000 ms 358492 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::vector<std::pair<int, int>> ids;
        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) {
                ids.push_back(pos);
                if (type) {
                    ++countRiver;
                }
            }
        }
        std::sort(ids.begin(), ids.end());
        ids.erase(std::unique(ids.begin(), ids.end()), ids.end());
        auto getid = [&](const std::pair<int, int> &p) {
            auto itr = std::lower_bound(ids.begin(), ids.end(), p);
            if (*itr != p) {
                return -1;
            }
            return (int)(itr - ids.begin());
        };
        UnionFind uft(ids.size());
        for (int i = 0; i < (int)ids.size(); ++i) {
            const auto &p = ids[i];
            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;
                    if (not(ar <= nx and nx < br and ac <= ny and ny < bc)) {
                        continue;
                    }
                    const int nid = getid({nx, ny});
                    if (nid == -1) {
                        continue;
                    }
                    if (not dataMap[{nx, ny}]) {
                        uft.merge(i, nid);
                    }
                }
            }
        }

        return uft.countGroups() - countRiver;
    }
}

Compilation message

rainbow.cpp: In function 'int colour(int, int, int, int)':
rainbow.cpp:186:13: warning: unused variable 'id' [-Wunused-variable]
  186 |         int id = 0;
      |             ^~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 364 KB Output is correct
2 Correct 146 ms 536 KB Output is correct
3 Correct 406 ms 516 KB Output is correct
4 Correct 400 ms 468 KB Output is correct
5 Correct 155 ms 532 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 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 316 ms 548 KB Output is correct
12 Correct 273 ms 520 KB Output is correct
13 Correct 226 ms 660 KB Output is correct
14 Correct 160 ms 588 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 1 ms 212 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 176 ms 26576 KB Output is correct
4 Correct 192 ms 26276 KB Output is correct
5 Correct 182 ms 26436 KB Output is correct
6 Correct 197 ms 26540 KB Output is correct
7 Correct 216 ms 26784 KB Output is correct
8 Correct 185 ms 26164 KB Output is correct
9 Correct 172 ms 26712 KB Output is correct
10 Correct 182 ms 26444 KB Output is correct
11 Correct 199 ms 27032 KB Output is correct
12 Correct 193 ms 26216 KB Output is correct
13 Correct 191 ms 26764 KB Output is correct
14 Correct 179 ms 27008 KB Output is correct
15 Correct 200 ms 26844 KB Output is correct
16 Correct 177 ms 26708 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 3049 ms 358492 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 364 KB Output is correct
2 Correct 146 ms 536 KB Output is correct
3 Correct 406 ms 516 KB Output is correct
4 Correct 400 ms 468 KB Output is correct
5 Correct 155 ms 532 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 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 316 ms 548 KB Output is correct
12 Correct 273 ms 520 KB Output is correct
13 Correct 226 ms 660 KB Output is correct
14 Correct 160 ms 588 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Execution timed out 3029 ms 75552 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 364 KB Output is correct
2 Correct 146 ms 536 KB Output is correct
3 Correct 406 ms 516 KB Output is correct
4 Correct 400 ms 468 KB Output is correct
5 Correct 155 ms 532 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 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 316 ms 548 KB Output is correct
12 Correct 273 ms 520 KB Output is correct
13 Correct 226 ms 660 KB Output is correct
14 Correct 160 ms 588 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Execution timed out 3029 ms 75552 KB Time limit exceeded
19 Halted 0 ms 0 KB -