이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "keys.h"
#include <queue>
#include <tuple>
#include <vector>
#include <utility>
#include <algorithm>
#include <functional>
using namespace std;
bool found[300006], visited[300006], visited_edge[300006];
vector<tuple<int, int, int>> adj[300006];
vector<pair<int, int>> lt[300006];
vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c) {
queue<int> q;
function<void (int)> dfs = [&](int v) {
for (auto &i: lt[r[v]]) if (!visited[i.second]) {
visited[i.second] = true;
q.push(i.second);
if (!found[r[i.second]]) {
found[r[i.second]] = true;
dfs(i.second);
}
}
};
int n = (int)r.size(), m = (int)c.size();
for (int i = 0; i < m; i++) {
adj[u[i]].push_back({ v[i], c[i], i });
adj[v[i]].push_back({ u[i], c[i], i });
}
vector<int> ans(n), p;
for (int i = 0; i < n; i++) {
fill(found, found + n, false);
fill(visited, visited + n, false);
fill(visited_edge, visited_edge + m, false);
for (int i = 0; i < n; i++) lt[i].clear();
visited[i] = true;
found[r[i]] = true;
while (!q.empty()) q.pop();
q.push(i);
while (!q.empty()) {
int t = q.front(); q.pop();
for (auto &i: adj[t]) if (!visited_edge[get<2>(i)]) {
auto [ v, c, j ] = i;
visited_edge[j] = true;
if (found[c]) {
if (!visited[v]) {
visited[v] = true;
q.push(v);
if (!found[r[v]]) {
found[r[v]] = true;
dfs(v);
}
}
} else lt[c].push_back({ j, v });
}
}
int cnt = 0;
for (int i = 0; i < n; i++) if (visited[i]) cnt++;
p.push_back(cnt);
}
int globalMin = *min_element(p.begin(), p.end());
for (int i = 0; i < n; i++) ans[i] = (globalMin == p[i]);
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... |