Submission #198103

#	Time	Username	Problem	Language	Result	Execution time	Memory
198103		model_code	Building Skyscrapers (CEOI19_skyscrapers)	C++17	100 / 100	2782 ms	324140 KiB

skyscrapers

/* Constructs the minimum required grid graph.
   Tracks connected components using union-find.
   Decides which cells may be deleted based on neighbourhoods,
   updates that information when necessary and keeps these cells
   in a set<>.
   O(N log N)
*/
#include <bits/stdc++.h>
using namespace std;

class HashPair {
    static inline size_t hash_combine(size_t h_first, size_t h_second) {
        return h_first ^ (h_second + 0x9e3779b9 + (h_first << 6) + (h_second >> 2));
    }

    static inline size_t hash_int(unsigned int x) {
        x = ((x >> 16) ^ x) * 0x45d9f3b;
        x = ((x >> 16) ^ x) * 0x45d9f3b;
        x = (x >> 16) ^ x;
        return x;
    }

public:
    size_t operator() (const pair<int, int> & p) const {
        size_t h_first  = hash_int(p.first);
        size_t h_second = hash_int(p.second);

        return hash_combine(h_first, h_second);
    }
};

class lego {
    int N, V;
    vector< pair<int, int> > cells, empty_cells;
    unordered_map< pair<int, int>, int, HashPair> cell_indices, empty_cell_indices;
    vector<char> removed;

    set<int> removable;
    vector<char> is_removable;

    vector< vector<int> > G4, G8;

    void construct_graphs(bool only_solvability = false) {
        constexpr static int dx[8] = {-1, -1, -1,  0,  1, 1, 1, 0};
        constexpr static int dy[8] = { 1,  0, -1, -1, -1, 0, 1, 1};

        if(!init_solvability_done) {
            for(int i = 0; i < N; i++) for(int j = 0; j < 8; j++) {
                pair<int, int> p = {cells[i].first + dx[j], cells[i].second + dy[j]};
                auto it = cell_indices.find(p);
                int cell_id = (it == end(cell_indices)) ? -1 : it->second;
                if(cell_id == -1) {
                    auto jt = empty_cell_indices.find(p);
                    if(jt == end(empty_cell_indices)) {
                        empty_cell_indices[p] = empty_cells.size();
                        cell_id = N + empty_cells.size();
                        empty_cells.push_back(p);
                        G4.push_back({});
                        G8.push_back(vector<int>(8, cell_id));
                    }
                    else cell_id = N + jt->second;
                    G8[cell_id][4^j] = i;
                    if(j % 2) G4[cell_id].push_back(i);
                }
                G8[i][j] = cell_id;
                if(j % 2) G4[i].push_back(cell_id);
            }
        }
        if(!init_done && !only_solvability) {
            for(int i = 0; i < (int)empty_cells.size(); i++) for(int j = 0; j < 8; j++) {
                if(G8[N+i][j] != N+i) continue;
                pair<int, int> p = {empty_cells[i].first + dx[j], empty_cells[i].second + dy[j]};
                auto it = empty_cell_indices.find(p);
                if(it == end(empty_cell_indices)) continue;
                int cell_id = N + it->second;
                G8[N+i][j] = cell_id;
                if(j % 2) G4[N+i].push_back(cell_id);
            }
        }
    }

    int outer_component;
    vector< vector<int> > components4, components8;
    vector<int> comp4, comp8;
    vector<int> deg4, deg8; // degree = number of full neighbouring cells

    void find_components(bool only_solvability = false) {
        queue<int> q;

        if(!init_solvability_done) {
            components4.clear(); components4.resize(V);
            components8.clear(); components8.resize(V);
            comp4.clear(); comp4.resize(V, -1);
            comp8.clear(); comp8.resize(V, -1);
            deg4.clear(); deg4.resize(V, 0);
            deg8.clear(); deg8.resize(V, 0);
            for(int i = 0; i < V; i++) if(comp8[i] == -1 && !is_empty(i)) {
                comp8[i] = i;
                components8[i] = {i};
                q.push(i);
                while(!q.empty()) {
                    for(auto v : G8[q.front()]) if(comp8[v] == -1 && !is_empty(v)) {
                        comp8[v] = i;
                        components8[i].push_back(v);
                        q.push(v);
                    } 
                    q.pop();
                }
            }
        }
        if(!init_done && !only_solvability) {
            for(int i = 0; i < V; i++) if(comp4[i] == -1 && is_empty(i)) {
                comp4[i] = i;
                components4[i] = {i};
                q.push(i);
                while(!q.empty()) {
                    for(auto v : G4[q.front()]) if(comp4[v] == -1 && is_empty(v)) {
                        comp4[v] = i;
                        components4[i].push_back(v);
                        q.push(v);
                    } 
                    q.pop();
                }
            }
            for(int i = 0; i < V; i++) {
                for(auto v : G4[i]) if(!is_empty(v)) deg4[i]++;
                for(auto v : G8[i]) if(!is_empty(v)) deg8[i]++;
            }
        }
    }

    void add_edge(int v1, int v2) {
        int c1 = comp4[v1], c2 = comp4[v2];
        if(c1 == c2) return;
        if(components4[c1].size() < components4[c2].size()) swap(c1, c2);
        for(auto v : components4[c2]) {
            comp4[v] = c1;
            components4[c1].push_back(v);
        }
        if(c2 == outer_component) outer_component = c1;
        for(auto v : components4[c2])
            for(auto f : G8[v]) if(!is_empty(f)) update(f);
    }

    void update(int v) {
        static vector<char> seen = vector<char>(V, 0);

        bool reachable = false, articulation = false;

        for(auto adj : G4[v]) if(is_empty(adj))
            if(comp4[adj] == outer_component) reachable = true;

        if(deg8[v] <= 1) {
            if(reachable) {
                if(!is_removable[v]) {
                    removable.insert(v);
                    is_removable[v] = 1;
                }
            }
            else if(is_removable[v]) {
                removable.erase(v);
                is_removable[v] = 0;
            }
            return;
        }

        for(int j = 0; j < 8; j++) if(is_empty(G8[v][j])) {
            if(is_empty(G8[v][(j+1)%8])) continue; // 1 cell per region
            if(j % 2 == 0 && !is_empty(G8[v][(j+7)%8])) continue; // ignore corner gaps
            int c = comp4[G8[v][j]];
            if(seen[c]) {
                articulation = true;
                break;
            }
            seen[c]++;
        }
        for(int j = 0; j < 8; j++) if(is_empty(G8[v][j]))
            seen[comp4[G8[v][j]]] = 0;

        if(reachable && !articulation) {
            if(!is_removable[v]) {
                removable.insert(v);
                is_removable[v] = 1;
            }
        }
        else if(is_removable[v]) {
            removable.erase(v);
            is_removable[v] = 0;
        }
    }

    inline bool is_empty(int cell) {
        return (cell >= N || removed[cell]);
    }

    bool init_done, init_solvability_done;

    void init_solvability() {
        if(init_solvability_done) return;
        construct_graphs(true);
        V = G4.size();
        removed.resize(V, false);
        find_components(true);
        init_solvability_done = true;
    }

    void init() {
        if(init_done) return;

        construct_graphs();
        if(!init_solvability_done) {
            V = G4.size();
            removed.resize(V, false);
        }

        find_components();
        int min_coord = cells[0].first;
        for(int i = N; i < V; i++) if(min_coord >= empty_cells[i-N].first) {
            min_coord = empty_cells[i-N].first;
            outer_component = comp4[i];
        }

        is_removable.resize(N, 0);
        for(int i = 0; i < N; i++) update(i);
        
        init_done = init_solvability_done = true;
    }

  public:
    lego(vector< pair<int, int> > cells_) : N(cells_.size()), cells(cells_) {
        for(int i = 0; i < N; i++) cell_indices[cells[i]] = i;
        G4.resize(N);
        G8.resize(N, vector<int>(8));
        G4.reserve(9*N);
        G8.reserve(9*N);
        cell_indices.reserve(N);
        empty_cell_indices.reserve(8*N);
        
        init_done = init_solvability_done = false;
    }
    
    bool solvable() {
        init_solvability();
        return ((int)components8[comp8[0]].size() == N);
    }

    int remove() {
        init();
        if(removable.empty()) return -1;
        int rm_id = *rbegin(removable);

        removable.erase(--end(removable));
        removed[rm_id] = true;

        components4[rm_id] = {rm_id};
        comp4[rm_id] = rm_id;
        for(auto f : G4[rm_id]) if(!is_empty(f)) update(f);
        for(auto v : G4[rm_id]) {
            if(is_empty(v)) add_edge(rm_id, v);
            else deg4[v]--;
        }
        for(auto v : G8[rm_id]) {
            deg8[v]--;
            if(!is_empty(v)) update(v);
        }

        return rm_id;
    }
};

int main() {
    cin.sync_with_stdio(0);
    cin.tie(0);
    int N, t;
    cin >> N >> t;
    vector< pair<int, int> > cells(N);
    for(int i = 0; i < N; i++) cin >> cells[i].first >> cells[i].second;

    lego solver(cells);

    if(!solver.solvable()) {
        cout << "NO\n";
        return 0;
    }

    cout << "YES\n";
    vector<int> build;
    for(int i = 0; i < N; i++) {
        int removed_cell_id = solver.remove();
        assert(removed_cell_id != -1);
        build.push_back(removed_cell_id+1);
    }
    reverse(begin(build), end(build));
    for(int i = 0; i < N; i++) cout << build[i] << "\n";
}

• Subtask 1: 8 / 8
• Subtask 2: 14 / 14
• Subtask 3: 12 / 12
• Subtask 4: 17 / 17
• Subtask 5: 20 / 20
• Subtask 6: 10 / 10
• Subtask 7: 19 / 19