oj.uz

Submission #704114

# Submission time Handle Problem Language Result Execution time Memory
704114 2023-03-01T15:34:59 Z Cyanmond Land of the Rainbow Gold (APIO17_rainbow) C++17
23 / 100
 3000 ms 350104 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 {
        if (R > 50 and C > 50) {
            return 0;
        }
        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:189:13: warning: unused variable 'id' [-Wunused-variable]
  189 |         int id = 0;
      |             ^~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 356 KB Output is correct
2 Correct 152 ms 616 KB Output is correct
3 Correct 397 ms 524 KB Output is correct
4 Correct 398 ms 540 KB Output is correct
5 Correct 155 ms 520 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 311 ms 548 KB Output is correct
12 Correct 272 ms 612 KB Output is correct
13 Correct 249 ms 628 KB Output is correct
14 Correct 155 ms 552 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 0 ms 212 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 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 172 ms 26144 KB Output is correct
4 Correct 172 ms 26188 KB Output is correct
5 Correct 181 ms 26500 KB Output is correct
6 Correct 200 ms 26480 KB Output is correct
7 Correct 210 ms 26892 KB Output is correct
8 Correct 182 ms 26312 KB Output is correct
9 Correct 173 ms 26168 KB Output is correct
10 Correct 175 ms 26456 KB Output is correct
11 Correct 215 ms 26532 KB Output is correct
12 Correct 177 ms 26204 KB Output is correct
13 Correct 166 ms 26188 KB Output is correct
14 Correct 167 ms 26472 KB Output is correct
15 Correct 200 ms 26476 KB Output is correct
16 Correct 169 ms 26188 KB Output is correct

Subtask #3
0 / 24.0

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

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 356 KB Output is correct
2 Correct 152 ms 616 KB Output is correct
3 Correct 397 ms 524 KB Output is correct
4 Correct 398 ms 540 KB Output is correct
5 Correct 155 ms 520 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 311 ms 548 KB Output is correct
12 Correct 272 ms 612 KB Output is correct
13 Correct 249 ms 628 KB Output is correct
14 Correct 155 ms 552 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Incorrect 351 ms 66468 KB Output isn't correct
19 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 356 KB Output is correct
2 Correct 152 ms 616 KB Output is correct
3 Correct 397 ms 524 KB Output is correct
4 Correct 398 ms 540 KB Output is correct
5 Correct 155 ms 520 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 311 ms 548 KB Output is correct
12 Correct 272 ms 612 KB Output is correct
13 Correct 249 ms 628 KB Output is correct
14 Correct 155 ms 552 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Incorrect 351 ms 66468 KB Output isn't correct
19 Halted 0 ms 0 KB -