이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "keys.h"
#include <bits/stdc++.h>
#define f first
#define s second
using namespace std;
using pi = pair<int,int>;
const int MAX_N = 3e5;
vector<pi> nei[MAX_N];
vector<pi> need_key[MAX_N];
int state[MAX_N];
std::vector<int> find_reachable(std::vector<int> r, std::vector<int> u, std::vector<int> v, std::vector<int> c) {
int n = r.size(), m = u.size();
for(int i = 0;i < m; i ++) {
int a = u[i], b = v[i], t = c[i];
nei[a].push_back({b,t});
nei[b].push_back({a,t});
}
vector<int> res;
int opt_score = n;
for(int i = 0; i < n; i ++) {
vector<bool> vis(n);
vis[i] = true;
stack<int> dfs;
vector<vector<int>> waiting(n);
vector<int> keys(n);
dfs.push(i);
int cnt = 0;
while(!dfs.empty()) {
int cur = dfs.top();
cnt++;
dfs.pop();
keys[r[cur]] = true;
for(int w : waiting[r[cur]]) {
if(!vis[w]) {
vis[w] = true;
dfs.push(w);
}
}
waiting[r[cur]].clear();
for(pi edge : nei[cur]) {
if(keys[edge.s]) {
if(!vis[edge.f]) {
vis[edge.f] = true;
dfs.push(edge.f);
}
} else {
waiting[edge.s].push_back(edge.f);
}
}
}
if(cnt < opt_score) {
res.clear();
opt_score = cnt;
}
if(cnt == opt_score) {
res.push_back(i);
}
}
vector<int> ans(n);
for(int r : res) {
ans[r] = 1;
}
return ans;
}
# | 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... |