#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
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
