제출 #704105

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
704105		Cyanmond	무지개나라 (APIO17_rainbow)	C++17	11 / 100	3071 ms	364580 KiB

rainbow

#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;
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;
    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::upper_bound(ranges.begin(), ranges.end(), std::make_pair(ac, 0));
        if (itr != ranges.begin()) {
            --itr;
            if (itr->first + itr->second <= ar) {
                ++itr;
            }
        }
        auto itr2 = std::lower_bound(ranges.begin(), ranges.end(), std::make_pair(bc, 0));
        return itr2 - itr;
    } else {
        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 / 11
• Subtask 2: 0 / 12
• Subtask 3: 0 / 24
• Subtask 4: 0 / 27
• Subtask 5: 0 / 26