Submission #579188

#	Time	Username	Problem	Language	Result	Execution time	Memory
579188		KoD	Fountain Parks (IOI21_parks)	C++17	Compilation error	0 ms	0 KiB

parks

#include <vector>
#include <bits/stdc++.h>

using std::array;
using std::pair;
using std::tuple;
using std::vector;

using ll = long long;

template <class T>
constexpr T infty = std::numeric_limits<T>::max() / 2;

template <class F>
struct fixed : private F {
    explicit fixed(F&& f) : F(std::forward<F>(f)) {}
    template <class... Args>
    decltype(auto) operator()(Args&&... args) const {
        return F::operator()(*this, std::forward<Args>(args)...);
    }
};

vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c) {
    const int N = (int)r.size();
    const int M = (int)u.size();
    const int K = std::max(*std::max_element(r.begin(), r.end()), *std::max_element(c.begin(), c.end())) + 1;
    vector<vector<pair<int, int>>> original_graph(N);
    vector<std::set<pair<int, int>>> graph(N);
    vector<std::set<int>> bad(N);
    for (int i = 0; i < M; ++i) {
        graph[u[i]].emplace(v[i], c[i]);
        graph[v[i]].emplace(u[i], c[i]);
        original_graph[u[i]].emplace_back(v[i], c[i]);
        original_graph[v[i]].emplace_back(u[i], c[i]);
    }
    vector<int> perm(N);
    std::iota(perm.begin(), perm.end(), 0);
    std::default_random_engine engine(904);
    std::shuffle(perm.begin(), perm.end(), engine);

    vector<char> found(K), prohibited(K);
    vector<vector<int>> waiting(K);
    vector<char> seen(N);
    vector<int> reach(N, N + 1);
    for (const int src : perm) {
        vector<int> visited, memo;
        if ([&]() -> bool {
            std::queue<int> que;
            que.push(src);
            seen[src] = true;
            memo.push_back(src);
            while (!que.empty()) {
                const int u = que.front();
                que.pop();
                visited.push_back(u);
                // if (prohibited[r[u]]) {
                //     return false;
                // }
                found[r[u]] = true;
                for (const int v : waiting[r[u]]) {
                    que.push(v);
                }
                waiting[r[u]].clear();
                for (const auto& [v, c] : original_graph[u]) {
                    if (!seen[v]) {
                        seen[v] = true;
                        memo.push_back(v);
                        if (found[c]) {
                            que.push(v);
                        } else {
                            waiting[c].push_back(v);
                        }
                    }
                }
                // for (const int c : bad[u]) {
                //     if (found[c]) {
                //         return false;
                //     }
                //     prohibited[c] = true;
                // }
            }
            return true;
        }()) {
            const int n = (int)visited.size();
            reach[src] = true;
            // for (const int u : visited) {
            //     reach[u] = std::min(reach[u], n);
            // }
        } 
        // for (const int u : memo) {
        //     seen[u] = false;
        // }
        std::fill(seen.begin(), seen.end(), false);
        for (int i = 0; i < K; ++i) {
            found[i] = prohibited[i] = false;
            waiting[i].clear();
        }
        // for (const auto& [u, c] : original_graph[src]) {
        //     graph[u].erase(pair(src, c));
        //     bad[u].insert(c);
        // }
    }
    const int min = *std::min_element(reach.begin(), reach.end());
    vector<int> ret(N);
    for (int i = 0; i < N; ++i) {
        ret[i] = (reach[i] == min);
    }
    return ret;
}

Compilation message (stderr)

parks.cpp: In function 'std::vector<int> find_reachable(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
parks.cpp:84:23: warning: unused variable 'n' [-Wunused-variable]
   84 |             const int n = (int)visited.size();
      |                       ^
/usr/bin/ld: /tmp/ccSyF9PC.o: in function `main':
grader.cpp:(.text.startup+0x23c): undefined reference to `construct_roads(std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >)'
collect2: error: ld returned 1 exit status