이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <vector>
#include <bits/stdc++.h>
using namespace std;
int n;
vector<int> r;
vector<int> cnts;
vector<int> ans;
struct edge {
int k;
int v;
};
vector<vector<edge>> adj;
unordered_map<int, int> visited_sets;
vector<unordered_set<int>> setlist;
int min_count = 1e9;
bool a_contains_all_b(unordered_set<int>& a, unordered_set<int>& b) {
for(int i : b) {
if (a.count(i) == 0) return false;
}
return true;
}
void compute_cnt(int start) {
unordered_set<int> vis;
unordered_set<int> collected_keys;
queue<int> to_visit {{ start }};
unordered_map<int, vector<int>> next_unlocked;
while (!to_visit.empty()) {
int u = to_visit.front(); to_visit.pop();
if (vis.count(u) > 0) continue;
vis.insert(u);
if (cnts[u] > 0) {
// we know what happens if we start from u
if (cnts[u] == min_count && a_contains_all_b(setlist[visited_sets[u]], vis)) {
// u has the minimum size, check if we are inside or not
// contains all, ok
cnts[start] = cnts[u];
visited_sets[start] = visited_sets[u];
} else {
cnts[start] = min_count+1;
}
break;
}
if (collected_keys.insert(r[u]).second) {
for (int v : next_unlocked[r[u]]) {
to_visit.push(v);
}
}
for (edge e : adj[u]) {
if (collected_keys.count(e.k) > 0) {
to_visit.push(e.v);
} else {
next_unlocked[e.k].push_back(e.v);
}
}
}
if (cnts[start] == 0) {
cnts[start] = vis.size();
visited_sets[start] = setlist.size();
setlist.push_back(move(vis));
//cerr << "Full computation for start = " << start << endl;
}
min_count = min(cnts[start], min_count);
}
mt19937 gen(58);
std::vector<int> find_reachable(std::vector<int> r_, std::vector<int> u, std::vector<int> v, std::vector<int> c) {
r = r_;
n = r.size();
cnts = vector<int>(r.size(), 0);
adj.resize(n);
for (int i = 0; i < u.size(); ++i) {
adj[u[i]].push_back(edge({c[i], v[i]}));
adj[v[i]].push_back(edge({c[i], u[i]}));
}
vector<int> ilist(n);
for (int i = 0; i < n; ++i) ilist[i] = i;
shuffle(ilist.begin(), ilist.end(), gen);
for (int i : ilist) {
compute_cnt(i);
}
ans = vector<int>(n, 0);
for (int i = 0; i < n; ++i) {
ans[i] = cnts[i] == min_count;
}
return ans;
}
컴파일 시 표준 에러 (stderr) 메시지
keys.cpp: In function 'std::vector<int> find_reachable(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
keys.cpp:82:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
82 | for (int i = 0; i < u.size(); ++i) {
| ~~^~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |