/*
hack test:
11 13
0 1 2 3 3 3 3 3 3 2 1
1 10 1
10 0 1
0 2 1
2 9 2
9 0 2
2 3 1
3 4 3
4 5 3
5 6 3
6 7 3
7 8 3
8 3 3
0 1 0
*/
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast,unroll-loops")
#define fs first
#define sc second
#define p_q priority_queue
using namespace std;
struct DSU{
vector<int> bo;
void init(int n){
bo.resize(n);
iota(bo.begin(),bo.end(),0);
}
int find(int x){
return bo[x]==x?x:bo[x]=find(bo[x]);
}
void merge(int x,int y){
bo[x]=y;
}
}dsu;
vector<int> r,dfn,low,out,inv;
vector<vector<int> > nw;
vector<vector<pair<int,int> > > e;
vector<vector<pair<int,int> > > st;
int cnt=1;
void dfs(int a,int f){
dfn[a]=low[a]=out[a]=cnt;
inv[cnt]=a;
cnt++;
for(auto h:e[a]){
st[h.fs].push_back({a,h.sc});
}
for(auto h:st[r[a]]){
nw[dsu.find(h.fs)].push_back(h.sc);
}
st[r[a]].clear();
while(nw[a].size()){
auto h=nw[a].back();
nw[a].pop_back();
if(dfn[h]){
low[a]=min(low[a],dfn[h]);
continue;
}
dfs(h,a);
low[a]=min(low[a],low[h]);
out[a]=out[h];
for(auto h:st[r[a]]){
nw[dsu.find(h.fs)].push_back(h.sc);
}
st[r[a]].clear();
}
dsu.merge(a,f);
}
vector<int> find_reachable(vector<int> R, vector<int> u, vector<int> v, vector<int> c) {
int n=R.size();
int m=u.size();
dsu.init(n);
e.resize(n);
dfn.resize(n);
low.resize(n);
nw.resize(n);
out.resize(n);
inv.resize(n+1);
st.resize(n);
r=R;
for(int i=0;i<m;i++){
e[u[i]].push_back({c[i],v[i]});
e[v[i]].push_back({c[i],u[i]});
}
for(int i=0;i<n;i++){
if(!dfn[i]){
dfs(i,i);
}
}
int mn=1e9;
for(int i=0;i<n;i++){
if(dfn[i]==low[i]){
mn=min(mn,out[i]-dfn[i]+1);
}
}
vector<int> ans(n);
for(int i=0;i<n;i++){
if(dfn[i]==low[i]){
if(out[i]-dfn[i]+1==mn){
for(int j=dfn[i];j<=out[i];j++){
ans[inv[j]]=1;
}
}
}
}
return ans;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
0 ms |
212 KB |
Output is correct |
8 |
Correct |
0 ms |
212 KB |
Output is correct |
9 |
Correct |
0 ms |
340 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
0 ms |
212 KB |
Output is correct |
8 |
Correct |
0 ms |
212 KB |
Output is correct |
9 |
Correct |
0 ms |
340 KB |
Output is correct |
10 |
Correct |
0 ms |
340 KB |
Output is correct |
11 |
Correct |
0 ms |
212 KB |
Output is correct |
12 |
Correct |
1 ms |
340 KB |
Output is correct |
13 |
Correct |
0 ms |
284 KB |
Output is correct |
14 |
Correct |
0 ms |
212 KB |
Output is correct |
15 |
Correct |
0 ms |
340 KB |
Output is correct |
16 |
Correct |
0 ms |
212 KB |
Output is correct |
17 |
Correct |
1 ms |
212 KB |
Output is correct |
18 |
Correct |
1 ms |
212 KB |
Output is correct |
19 |
Correct |
1 ms |
212 KB |
Output is correct |
20 |
Correct |
0 ms |
212 KB |
Output is correct |
21 |
Correct |
1 ms |
340 KB |
Output is correct |
22 |
Correct |
1 ms |
212 KB |
Output is correct |
23 |
Correct |
0 ms |
340 KB |
Output is correct |
24 |
Correct |
0 ms |
340 KB |
Output is correct |
25 |
Correct |
1 ms |
340 KB |
Output is correct |
26 |
Correct |
0 ms |
340 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
0 ms |
212 KB |
Output is correct |
8 |
Correct |
0 ms |
212 KB |
Output is correct |
9 |
Correct |
0 ms |
340 KB |
Output is correct |
10 |
Correct |
0 ms |
340 KB |
Output is correct |
11 |
Correct |
0 ms |
212 KB |
Output is correct |
12 |
Correct |
1 ms |
340 KB |
Output is correct |
13 |
Correct |
0 ms |
284 KB |
Output is correct |
14 |
Correct |
0 ms |
212 KB |
Output is correct |
15 |
Correct |
0 ms |
340 KB |
Output is correct |
16 |
Correct |
0 ms |
212 KB |
Output is correct |
17 |
Correct |
1 ms |
212 KB |
Output is correct |
18 |
Correct |
1 ms |
212 KB |
Output is correct |
19 |
Correct |
1 ms |
212 KB |
Output is correct |
20 |
Correct |
0 ms |
212 KB |
Output is correct |
21 |
Correct |
1 ms |
340 KB |
Output is correct |
22 |
Correct |
1 ms |
212 KB |
Output is correct |
23 |
Correct |
0 ms |
340 KB |
Output is correct |
24 |
Correct |
0 ms |
340 KB |
Output is correct |
25 |
Correct |
1 ms |
340 KB |
Output is correct |
26 |
Correct |
0 ms |
340 KB |
Output is correct |
27 |
Correct |
2 ms |
724 KB |
Output is correct |
28 |
Correct |
2 ms |
724 KB |
Output is correct |
29 |
Correct |
2 ms |
852 KB |
Output is correct |
30 |
Correct |
1 ms |
468 KB |
Output is correct |
31 |
Correct |
1 ms |
468 KB |
Output is correct |
32 |
Correct |
1 ms |
340 KB |
Output is correct |
33 |
Correct |
1 ms |
340 KB |
Output is correct |
34 |
Correct |
1 ms |
596 KB |
Output is correct |
35 |
Correct |
1 ms |
596 KB |
Output is correct |
36 |
Correct |
1 ms |
852 KB |
Output is correct |
37 |
Correct |
1 ms |
852 KB |
Output is correct |
38 |
Correct |
2 ms |
980 KB |
Output is correct |
39 |
Correct |
2 ms |
1108 KB |
Output is correct |
40 |
Correct |
1 ms |
468 KB |
Output is correct |
41 |
Correct |
1 ms |
468 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
0 ms |
212 KB |
Output is correct |
8 |
Correct |
0 ms |
212 KB |
Output is correct |
9 |
Correct |
0 ms |
340 KB |
Output is correct |
10 |
Correct |
173 ms |
38300 KB |
Output is correct |
11 |
Correct |
282 ms |
63844 KB |
Output is correct |
12 |
Correct |
29 ms |
10452 KB |
Output is correct |
13 |
Correct |
206 ms |
52576 KB |
Output is correct |
14 |
Correct |
169 ms |
118860 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
0 ms |
212 KB |
Output is correct |
8 |
Correct |
0 ms |
212 KB |
Output is correct |
9 |
Correct |
0 ms |
340 KB |
Output is correct |
10 |
Correct |
0 ms |
340 KB |
Output is correct |
11 |
Correct |
0 ms |
212 KB |
Output is correct |
12 |
Correct |
1 ms |
340 KB |
Output is correct |
13 |
Correct |
0 ms |
284 KB |
Output is correct |
14 |
Correct |
0 ms |
212 KB |
Output is correct |
15 |
Correct |
0 ms |
340 KB |
Output is correct |
16 |
Correct |
0 ms |
212 KB |
Output is correct |
17 |
Correct |
1 ms |
212 KB |
Output is correct |
18 |
Correct |
1 ms |
212 KB |
Output is correct |
19 |
Correct |
1 ms |
212 KB |
Output is correct |
20 |
Correct |
0 ms |
212 KB |
Output is correct |
21 |
Correct |
1 ms |
340 KB |
Output is correct |
22 |
Correct |
1 ms |
212 KB |
Output is correct |
23 |
Correct |
0 ms |
340 KB |
Output is correct |
24 |
Correct |
0 ms |
340 KB |
Output is correct |
25 |
Correct |
1 ms |
340 KB |
Output is correct |
26 |
Correct |
0 ms |
340 KB |
Output is correct |
27 |
Correct |
2 ms |
724 KB |
Output is correct |
28 |
Correct |
2 ms |
724 KB |
Output is correct |
29 |
Correct |
2 ms |
852 KB |
Output is correct |
30 |
Correct |
1 ms |
468 KB |
Output is correct |
31 |
Correct |
1 ms |
468 KB |
Output is correct |
32 |
Correct |
1 ms |
340 KB |
Output is correct |
33 |
Correct |
1 ms |
340 KB |
Output is correct |
34 |
Correct |
1 ms |
596 KB |
Output is correct |
35 |
Correct |
1 ms |
596 KB |
Output is correct |
36 |
Correct |
1 ms |
852 KB |
Output is correct |
37 |
Correct |
1 ms |
852 KB |
Output is correct |
38 |
Correct |
2 ms |
980 KB |
Output is correct |
39 |
Correct |
2 ms |
1108 KB |
Output is correct |
40 |
Correct |
1 ms |
468 KB |
Output is correct |
41 |
Correct |
1 ms |
468 KB |
Output is correct |
42 |
Correct |
173 ms |
38300 KB |
Output is correct |
43 |
Correct |
282 ms |
63844 KB |
Output is correct |
44 |
Correct |
29 ms |
10452 KB |
Output is correct |
45 |
Correct |
206 ms |
52576 KB |
Output is correct |
46 |
Correct |
169 ms |
118860 KB |
Output is correct |
47 |
Correct |
0 ms |
212 KB |
Output is correct |
48 |
Correct |
0 ms |
212 KB |
Output is correct |
49 |
Correct |
0 ms |
212 KB |
Output is correct |
50 |
Correct |
146 ms |
91276 KB |
Output is correct |
51 |
Correct |
174 ms |
89840 KB |
Output is correct |
52 |
Correct |
240 ms |
48104 KB |
Output is correct |
53 |
Correct |
207 ms |
48460 KB |
Output is correct |
54 |
Correct |
242 ms |
60400 KB |
Output is correct |
55 |
Correct |
191 ms |
46144 KB |
Output is correct |
56 |
Correct |
354 ms |
70916 KB |
Output is correct |
57 |
Correct |
201 ms |
65512 KB |
Output is correct |
58 |
Correct |
305 ms |
70748 KB |
Output is correct |
59 |
Correct |
351 ms |
72996 KB |
Output is correct |
60 |
Correct |
347 ms |
91840 KB |
Output is correct |
61 |
Correct |
324 ms |
93284 KB |
Output is correct |
62 |
Correct |
243 ms |
40556 KB |
Output is correct |
63 |
Correct |
123 ms |
45160 KB |
Output is correct |
64 |
Correct |
3 ms |
2260 KB |
Output is correct |
65 |
Correct |
3 ms |
2260 KB |
Output is correct |
66 |
Correct |
209 ms |
40808 KB |
Output is correct |
67 |
Correct |
17 ms |
12160 KB |
Output is correct |
68 |
Correct |
28 ms |
20032 KB |
Output is correct |
69 |
Correct |
328 ms |
73548 KB |
Output is correct |
70 |
Correct |
59 ms |
39836 KB |
Output is correct |
71 |
Correct |
194 ms |
118860 KB |
Output is correct |
72 |
Correct |
327 ms |
73628 KB |
Output is correct |
73 |
Correct |
209 ms |
40796 KB |
Output is correct |