1814F - Communication Towers - CodeForces Solution

#include <iostream>
#include <vector>
#include <fstream>
#include <sstream>
#include <string>
#include <stack>
#include <cassert>
#include <algorithm>
#include <deque>
#include <numeric>
#include <unordered_set>
#include <queue>


struct Bounds {
    int l;
    int r;
};

struct Link {
    int i;
    int j;
};

struct Instance {
    int n;
    int m;
    std::vector<Bounds> bounds;
    std::vector<Link> links;
};

struct Graph {
    std::vector<std::vector<int>> adj;
};

Graph makeGraph(const Instance& instance) {
    Graph g;
    g.adj.resize(instance.n);
    for(auto link : instance.links) {
        Bounds a = instance.bounds[link.i];
        Bounds b = instance.bounds[link.j];
        if(a.r < b.l || b.r < a.l) continue;
        g.adj[link.i].push_back(link.j);
        g.adj[link.j].push_back(link.i);
    }
    return g;
}

static Instance readInstance(std::istream& stream) {
    Instance instance;
    stream >> instance.n;
    stream >> instance.m;
    instance.bounds.reserve(instance.n);
    for(int i = 0; i < instance.n; ++i) {
        Bounds b;
        stream >> b.l;
        stream >> b.r;
        instance.bounds.push_back(b);
    }
    instance.links.reserve(instance.m);
    for(int i = 0; i < instance.m; ++i) {
        Link l;
        stream >> l.i;
        l.i--;
        stream >> l.j;
        l.j--;
        instance.links.push_back(l);
    }
    return instance;
}

static std::vector<int> readSolution(std::string s) {
    std::vector<int> sol;
    std::stringstream ss;
    ss << s;
    while(!ss.eof()) {
        int v;
        ss >> v;
        sol.push_back(v);
    }
    return sol;
}

static std::vector<int> trivialSolution(const Instance& instance) {
    std::vector<int> sol;
    sol.resize(instance.n);
    std::iota(sol.begin(), sol.end(), 1);
    return sol;
}

static std::vector<int> solve(const Instance& instance) {
    if(instance.n == 0) return {};
    auto maxl = std::max_element(instance.bounds.begin(), instance.bounds.end(), [](Bounds a, Bounds b) { return a.l < b.l; });
    auto minr = std::max_element(instance.bounds.begin(), instance.bounds.end(), [](Bounds a, Bounds b) { return a.r > b.r; });

    if(maxl->l <= minr->r) return trivialSolution(instance);

    Graph g = makeGraph(instance);

    std::vector<std::vector<Bounds>> accessibilityBounds;
    std::vector<int> accessibilityRange;
    accessibilityBounds.resize(instance.n);
    accessibilityBounds[0].push_back(instance.bounds[0]);
    accessibilityRange.resize(instance.n, 0);
    accessibilityRange[0] = instance.bounds[0].r - instance.bounds[0].l + 1;

    auto checkBounds = [&](int i) -> void {
        const auto& ibounds = accessibilityBounds[i];
        for(size_t k = 0; k < ibounds.size(); ++k) {
            assert(ibounds[k].l <= ibounds[k].r);
        }
        for(size_t k = 0; k+1 < ibounds.size(); ++k) {
            assert(ibounds[k].r < ibounds[k+1].l);
        }
    };

    auto totalRange = [](const std::vector<Bounds>& v) -> int {
        int s = 0;
        for(Bounds b : v) s += b.r - b.l + 1;
        return s;
    };

    auto tryPropagateBounds = [&](int i, int j) -> bool {
        checkBounds(i);
        checkBounds(j);
        std::vector<Bounds> newBounds;
        Bounds bj = instance.bounds[j];
        for(Bounds bi : accessibilityBounds[i]) {
            Bounds intersection = Bounds{std::max(bi.l, bj.l), std::min(bi.r, bj.r)};
            if(intersection.l > intersection.r) continue;
            newBounds.push_back(intersection);
        }

        if(newBounds.empty()) return false;
        newBounds.insert(newBounds.end(), accessibilityBounds[j].begin(), accessibilityBounds[j].end());
        std::sort(newBounds.begin(), newBounds.end(), [](Bounds a, Bounds b) { return a.l < b.l; });

        // try merging bounds
        int cur = 0;
        for(int k = 1; k < newBounds.size(); ++k) {
            if(newBounds[k].l <= newBounds[cur].r) {
                // absorb k into i
                newBounds[cur].r = std::max(newBounds[cur].r, newBounds[k].r);
                newBounds[k].l = -1;
                newBounds[k].r = -1;
            } else {
                // advance to k
                cur = k;
            }
        }
        newBounds.erase(std::remove_if(newBounds.begin(), newBounds.end(), [](Bounds b) { return b.l == -1 && b.r == -1; }), newBounds.end());

        auto& oldBounds = accessibilityBounds[j];
        if(newBounds.size() != oldBounds.size()) {
            oldBounds = newBounds;
            accessibilityRange[j] = totalRange(newBounds);
            return true;
        }
        for(size_t k = 0; k < newBounds.size(); ++k) {
            if(newBounds[k].l != oldBounds[k].l || newBounds[k].r != oldBounds[k].r) {
                oldBounds = newBounds;
                accessibilityRange[j] = totalRange(newBounds);
                return true;
            }
        }

        return false;
    };

    auto comp = [&](int i, int j) {
        return accessibilityRange[i] < accessibilityRange[j];
    };

    std::priority_queue<int, std::vector<int>, decltype(comp)> queue(comp);
    std::vector<char> inQueue;
    std::vector<char> accessible;
    inQueue.resize(instance.n, 0);
    accessible.resize(instance.n, 0);
    int nbAccessible = 0;
    int nbSureInaccessible = std::accumulate(g.adj.begin(), g.adj.end(), 0, [](int sum, const auto& adj) { return sum + adj.empty(); });

    auto push = [&](int i) -> void {
        assert(!inQueue[i]);
        queue.push(i);
        inQueue[i] = 1;
    };

    auto pop = [&]() -> int {
        assert(!queue.empty());
        int i = queue.top();
        queue.pop();
        inQueue[i] = 0;
        return i;
    };

    auto print = [&]() -> void {
        return;
        for(int i = 0; i < instance.n; ++i) {
            std::cout << i+1 << " ";
            for(auto b : accessibilityBounds[i]) {
                std::cout << "[" << b.l << ", " << b.r << "] ";
            }
            std::cout << std::endl;
        }
        std::cout << std::endl;
    };

    print();
    push(0);
    accessible[0] = 1;
    nbAccessible = 1;
    while(!queue.empty()) {
        int i = pop();
        for(int j : g.adj[i]) {
            if(j == 0) continue;
            // std::cout << i+1 << " -> " << j+1 << std::endl;
            bool didSomething = tryPropagateBounds(i, j);
            if(!accessible[j] && !accessibilityBounds[j].empty()) {
                accessible[j] = 1;
                ++nbAccessible;
                if(nbAccessible + nbSureInaccessible == instance.n) break;
            }
            if(!didSomething) continue;
            if(inQueue[j]) continue;
            push(j);
            print();
        }
        if(nbAccessible + nbSureInaccessible == instance.n) break;
    }
    std::vector<int> solution;
    for(int i = 0; i < instance.n; ++i) {
        if(accessible[i]) solution.push_back(i+1);
    }
    return solution;
}

static int compareSolutions(const std::vector<int>& a, const std::vector<int>& b) {
    if(a.size() != b.size()) return 1;
    for(size_t i = 0; i < a.size(); ++i) {
        if(a[i] != b[i]) return 1;
    }
    return 0;
}

static void writeSolution(const std::vector<int>& sol, std::ostream& stream) {
    for(int v : sol) stream << v << " ";
}

int main(int argc, char** argv) {
    if(argc == 3) {
        std::string filename = argv[1];
        std::string result = argv[2];
        std::ifstream file(filename);
        Instance instance = readInstance(file);
        std::vector<int> expectedSolution = readSolution(result);
        std::vector<int> ownSolution = solve(instance);
        std::cout << "Expected :" << std::endl;
        writeSolution(expectedSolution, std::cout);
        std::cout << std::endl;
        std::cout << "Got :" << std::endl;
        writeSolution(ownSolution, std::cout);
        std::cout << std::endl;
        return compareSolutions(expectedSolution, ownSolution);
    }
    Instance instance = readInstance(std::cin);
    std::vector<int> solution = solve(instance);
    writeSolution(solution, std::cout);
    return 0;
}