#include <bits/stdc++.h>
using namespace std;
vector <int> ke[300001],res;
int n,m,isInStack[300001],low[300001],idx[300001],R[300001],cnt[300001],ch[300001],id=1,mn=1e9;
stack <int> s;
void ssc(int v){
idx[v]=id;
low[v]=id;
id++;
s.push(v);
isInStack[v]=1;
for (int w:ke[v]){
if (idx[w]==0){
ssc(w);
low[v]=min(low[w],low[v]);
}
else if (isInStack[w])
low[v]=min(low[v],idx[w]);
}
if (low[v]==idx[v]){
while (s.top()!=v){
isInStack[s.top()]=false;
R[s.top()]=v;
cnt[v]++;
s.pop();
}
isInStack[v]=false;
cnt[v]++;
s.pop();
}
}
void tarjan(){
iota(R,R+n,0);
for (int i=0;i<n;i++)
if (idx[i]==0)
ssc(i);
}
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<m;i++){
if (r[u[i]]==c[i])
ke[u[i]].push_back(v[i]);
if (r[v[i]]==c[i])
ke[v[i]].push_back(u[i]);
}
tarjan();
for (int i=0;i<n;i++)
for (int j:ke[i])
if (R[j]!=R[i])
ch[R[i]]=1;
for (int i=0;i<n;i++)
if (i==R[i]&&!ch[i])
mn=min(mn,cnt[i]);
for (int i=0;i<n;i++)
res.push_back(!ch[R[i]]&&cnt[R[i]]==mn);
return res;
}
Compilation message
keys.cpp: In function 'std::vector<int> find_reachable(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
keys.cpp:55:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
55 | for (int i=0;i<n;i++)
| ^~~
keys.cpp:57:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
57 | return res;
| ^~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
3 ms |
12120 KB |
Output is correct |
| 2 |
Correct |
3 ms |
12124 KB |
Output is correct |
| 3 |
Correct |
2 ms |
12124 KB |
Output is correct |
| 4 |
Correct |
3 ms |
12296 KB |
Output is correct |
| 5 |
Correct |
3 ms |
12124 KB |
Output is correct |
| 6 |
Correct |
2 ms |
12124 KB |
Output is correct |
| 7 |
Correct |
3 ms |
12124 KB |
Output is correct |
| 8 |
Correct |
3 ms |
12124 KB |
Output is correct |
| 9 |
Correct |
2 ms |
12124 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
3 ms |
12120 KB |
Output is correct |
| 2 |
Correct |
3 ms |
12124 KB |
Output is correct |
| 3 |
Correct |
2 ms |
12124 KB |
Output is correct |
| 4 |
Correct |
3 ms |
12296 KB |
Output is correct |
| 5 |
Correct |
3 ms |
12124 KB |
Output is correct |
| 6 |
Correct |
2 ms |
12124 KB |
Output is correct |
| 7 |
Correct |
3 ms |
12124 KB |
Output is correct |
| 8 |
Correct |
3 ms |
12124 KB |
Output is correct |
| 9 |
Correct |
2 ms |
12124 KB |
Output is correct |
| 10 |
Correct |
3 ms |
12124 KB |
Output is correct |
| 11 |
Correct |
3 ms |
12124 KB |
Output is correct |
| 12 |
Correct |
2 ms |
12124 KB |
Output is correct |
| 13 |
Correct |
2 ms |
12124 KB |
Output is correct |
| 14 |
Correct |
3 ms |
12124 KB |
Output is correct |
| 15 |
Correct |
2 ms |
12124 KB |
Output is correct |
| 16 |
Correct |
2 ms |
12124 KB |
Output is correct |
| 17 |
Incorrect |
3 ms |
12376 KB |
Output isn't correct |
| 18 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
3 ms |
12120 KB |
Output is correct |
| 2 |
Correct |
3 ms |
12124 KB |
Output is correct |
| 3 |
Correct |
2 ms |
12124 KB |
Output is correct |
| 4 |
Correct |
3 ms |
12296 KB |
Output is correct |
| 5 |
Correct |
3 ms |
12124 KB |
Output is correct |
| 6 |
Correct |
2 ms |
12124 KB |
Output is correct |
| 7 |
Correct |
3 ms |
12124 KB |
Output is correct |
| 8 |
Correct |
3 ms |
12124 KB |
Output is correct |
| 9 |
Correct |
2 ms |
12124 KB |
Output is correct |
| 10 |
Correct |
3 ms |
12124 KB |
Output is correct |
| 11 |
Correct |
3 ms |
12124 KB |
Output is correct |
| 12 |
Correct |
2 ms |
12124 KB |
Output is correct |
| 13 |
Correct |
2 ms |
12124 KB |
Output is correct |
| 14 |
Correct |
3 ms |
12124 KB |
Output is correct |
| 15 |
Correct |
2 ms |
12124 KB |
Output is correct |
| 16 |
Correct |
2 ms |
12124 KB |
Output is correct |
| 17 |
Incorrect |
3 ms |
12376 KB |
Output isn't correct |
| 18 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
3 ms |
12120 KB |
Output is correct |
| 2 |
Correct |
3 ms |
12124 KB |
Output is correct |
| 3 |
Correct |
2 ms |
12124 KB |
Output is correct |
| 4 |
Correct |
3 ms |
12296 KB |
Output is correct |
| 5 |
Correct |
3 ms |
12124 KB |
Output is correct |
| 6 |
Correct |
2 ms |
12124 KB |
Output is correct |
| 7 |
Correct |
3 ms |
12124 KB |
Output is correct |
| 8 |
Correct |
3 ms |
12124 KB |
Output is correct |
| 9 |
Correct |
2 ms |
12124 KB |
Output is correct |
| 10 |
Correct |
88 ms |
31688 KB |
Output is correct |
| 11 |
Incorrect |
124 ms |
39652 KB |
Output isn't correct |
| 12 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
3 ms |
12120 KB |
Output is correct |
| 2 |
Correct |
3 ms |
12124 KB |
Output is correct |
| 3 |
Correct |
2 ms |
12124 KB |
Output is correct |
| 4 |
Correct |
3 ms |
12296 KB |
Output is correct |
| 5 |
Correct |
3 ms |
12124 KB |
Output is correct |
| 6 |
Correct |
2 ms |
12124 KB |
Output is correct |
| 7 |
Correct |
3 ms |
12124 KB |
Output is correct |
| 8 |
Correct |
3 ms |
12124 KB |
Output is correct |
| 9 |
Correct |
2 ms |
12124 KB |
Output is correct |
| 10 |
Correct |
3 ms |
12124 KB |
Output is correct |
| 11 |
Correct |
3 ms |
12124 KB |
Output is correct |
| 12 |
Correct |
2 ms |
12124 KB |
Output is correct |
| 13 |
Correct |
2 ms |
12124 KB |
Output is correct |
| 14 |
Correct |
3 ms |
12124 KB |
Output is correct |
| 15 |
Correct |
2 ms |
12124 KB |
Output is correct |
| 16 |
Correct |
2 ms |
12124 KB |
Output is correct |
| 17 |
Incorrect |
3 ms |
12376 KB |
Output isn't correct |
| 18 |
Halted |
0 ms |
0 KB |
- |
