| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 579160 | KoD | 열쇠 (IOI21_keys) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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::map<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;
std::queue<int> que;
seen[src] = true;
que.push(src);
memo.push_back(src);
if ([&]() -> bool {
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] : 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[u] = n;
// for (const int u : visited) {
// reach[u] = std::min(reach[u], n);
// }
}
for (const int u : memo) {
seen[u] = 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(src);
// 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;
}