이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "keys.h"
#include <bits/stdc++.h>
using namespace std;
int n, m;
vector<pair<int, int>> g[300000], temp[300000];
set<int> R[300000];
stack<int> stck;
bool vis[300000];
void dfs1(int u)
{
vis[u] = true;
for (auto [v, c] : g[u])
if (!vis[v] && R[u].find(c) != R[u].end())
dfs1(v);
stck.push(u);
}
int cmp[300000];
void dfs2(int u, int rep)
{
cmp[u] = rep, vis[u] = true;
for (auto [v, c] : g[u])
if (!vis[v] && R[v].find(c) != R[v].end())
dfs2(v, rep);
}
void compress()
{
for (int i = 0; i < n; i++)
cmp[i] = cmp[cmp[i]];
for (int u = 0; u < n; u++)
{
temp[u] = g[u];
g[u] = vector<pair<int, int>>();
}
for (int u = 0; u < n; u++)
for (auto [v, k] : temp[u])
if (cmp[u] != cmp[v])
g[cmp[u]].push_back({cmp[v], k});
for (int i = 0; i < n; i++)
if (cmp[i] != i)
{
for (int r : R[i])
R[cmp[i]].insert(r);
R[i] = set<int>();
}
}
vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c)
{
n = r.size(), m = u.size();
for (int i = 0; i < n; i++)
R[i] = {r[i]};
for (int i = 0; i < m; i++)
{
g[u[i]].push_back({v[i], c[i]});
g[v[i]].push_back({u[i], c[i]});
}
for (int i = 0; i < n; i++)
cmp[i] = i;
while (true)
{
memset(vis, false, sizeof(vis));
for (int i = 0; i < n; i++)
if (i == cmp[i] && !vis[i])
dfs1(i);
bool top_sorted = true;
memset(vis, false, sizeof(vis));
while (!stck.empty())
{
if (!vis[stck.top()])
dfs2(stck.top(), stck.top());
else
top_sorted = false;
stck.pop();
}
compress();
if (top_sorted)
break;
}
vector<int> sz(n, 0);
for (int i = 0; i < n; i++)
sz[cmp[i]]++;
vector<int> out(n, 0), ans(n, 0);
int mn = INT_MAX;
for (int i = 0; i < n; i++)
if (i == cmp[i])
{
for (auto [j, k] : g[i])
if (R[i].find(k) != R[i].end())
out[i]++;
if (out[i] == 0)
mn = min(mn, sz[i]);
}
for (int i = 0; i < n; i++)
if (out[cmp[i]] == 0 && sz[cmp[i]] == mn)
ans[i] = 1;
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:107:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
107 | for (int i = 0; i < n; i++)
| ^~~
keys.cpp:111:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
111 | 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... |