# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
821560 |
2023-08-11T11:33:56 Z |
alvingogo |
Keys (IOI21_keys) |
C++17 |
|
375 ms |
129516 KB |
#include <vector>
#include <bits/stdc++.h>
#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;
}
# |
Verdict |
Execution time |
Memory |
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 |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
296 KB |
Output is correct |
7 |
Correct |
0 ms |
300 KB |
Output is correct |
8 |
Correct |
1 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
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 |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
296 KB |
Output is correct |
7 |
Correct |
0 ms |
300 KB |
Output is correct |
8 |
Correct |
1 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
1 ms |
340 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
1 ms |
340 KB |
Output is correct |
13 |
Correct |
0 ms |
296 KB |
Output is correct |
14 |
Correct |
0 ms |
212 KB |
Output is correct |
15 |
Correct |
1 ms |
340 KB |
Output is correct |
16 |
Correct |
0 ms |
212 KB |
Output is correct |
17 |
Correct |
0 ms |
212 KB |
Output is correct |
18 |
Correct |
0 ms |
300 KB |
Output is correct |
19 |
Correct |
0 ms |
212 KB |
Output is correct |
20 |
Correct |
0 ms |
296 KB |
Output is correct |
21 |
Correct |
1 ms |
340 KB |
Output is correct |
22 |
Correct |
0 ms |
212 KB |
Output is correct |
23 |
Correct |
1 ms |
340 KB |
Output is correct |
24 |
Correct |
1 ms |
340 KB |
Output is correct |
25 |
Correct |
1 ms |
340 KB |
Output is correct |
26 |
Correct |
1 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
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 |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
296 KB |
Output is correct |
7 |
Correct |
0 ms |
300 KB |
Output is correct |
8 |
Correct |
1 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
1 ms |
340 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
1 ms |
340 KB |
Output is correct |
13 |
Correct |
0 ms |
296 KB |
Output is correct |
14 |
Correct |
0 ms |
212 KB |
Output is correct |
15 |
Correct |
1 ms |
340 KB |
Output is correct |
16 |
Correct |
0 ms |
212 KB |
Output is correct |
17 |
Correct |
0 ms |
212 KB |
Output is correct |
18 |
Correct |
0 ms |
300 KB |
Output is correct |
19 |
Correct |
0 ms |
212 KB |
Output is correct |
20 |
Correct |
0 ms |
296 KB |
Output is correct |
21 |
Correct |
1 ms |
340 KB |
Output is correct |
22 |
Correct |
0 ms |
212 KB |
Output is correct |
23 |
Correct |
1 ms |
340 KB |
Output is correct |
24 |
Correct |
1 ms |
340 KB |
Output is correct |
25 |
Correct |
1 ms |
340 KB |
Output is correct |
26 |
Correct |
1 ms |
340 KB |
Output is correct |
27 |
Correct |
2 ms |
724 KB |
Output is correct |
28 |
Correct |
2 ms |
852 KB |
Output is correct |
29 |
Correct |
2 ms |
852 KB |
Output is correct |
30 |
Correct |
1 ms |
596 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 |
468 KB |
Output is correct |
34 |
Correct |
1 ms |
724 KB |
Output is correct |
35 |
Correct |
1 ms |
596 KB |
Output is correct |
36 |
Correct |
2 ms |
948 KB |
Output is correct |
37 |
Correct |
2 ms |
980 KB |
Output is correct |
38 |
Correct |
2 ms |
1108 KB |
Output is correct |
39 |
Correct |
2 ms |
1108 KB |
Output is correct |
40 |
Correct |
1 ms |
432 KB |
Output is correct |
41 |
Correct |
1 ms |
568 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
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 |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
296 KB |
Output is correct |
7 |
Correct |
0 ms |
300 KB |
Output is correct |
8 |
Correct |
1 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
159 ms |
43340 KB |
Output is correct |
11 |
Correct |
253 ms |
68052 KB |
Output is correct |
12 |
Correct |
38 ms |
11340 KB |
Output is correct |
13 |
Correct |
211 ms |
57616 KB |
Output is correct |
14 |
Correct |
172 ms |
129000 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
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 |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
296 KB |
Output is correct |
7 |
Correct |
0 ms |
300 KB |
Output is correct |
8 |
Correct |
1 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
1 ms |
340 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
1 ms |
340 KB |
Output is correct |
13 |
Correct |
0 ms |
296 KB |
Output is correct |
14 |
Correct |
0 ms |
212 KB |
Output is correct |
15 |
Correct |
1 ms |
340 KB |
Output is correct |
16 |
Correct |
0 ms |
212 KB |
Output is correct |
17 |
Correct |
0 ms |
212 KB |
Output is correct |
18 |
Correct |
0 ms |
300 KB |
Output is correct |
19 |
Correct |
0 ms |
212 KB |
Output is correct |
20 |
Correct |
0 ms |
296 KB |
Output is correct |
21 |
Correct |
1 ms |
340 KB |
Output is correct |
22 |
Correct |
0 ms |
212 KB |
Output is correct |
23 |
Correct |
1 ms |
340 KB |
Output is correct |
24 |
Correct |
1 ms |
340 KB |
Output is correct |
25 |
Correct |
1 ms |
340 KB |
Output is correct |
26 |
Correct |
1 ms |
340 KB |
Output is correct |
27 |
Correct |
2 ms |
724 KB |
Output is correct |
28 |
Correct |
2 ms |
852 KB |
Output is correct |
29 |
Correct |
2 ms |
852 KB |
Output is correct |
30 |
Correct |
1 ms |
596 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 |
468 KB |
Output is correct |
34 |
Correct |
1 ms |
724 KB |
Output is correct |
35 |
Correct |
1 ms |
596 KB |
Output is correct |
36 |
Correct |
2 ms |
948 KB |
Output is correct |
37 |
Correct |
2 ms |
980 KB |
Output is correct |
38 |
Correct |
2 ms |
1108 KB |
Output is correct |
39 |
Correct |
2 ms |
1108 KB |
Output is correct |
40 |
Correct |
1 ms |
432 KB |
Output is correct |
41 |
Correct |
1 ms |
568 KB |
Output is correct |
42 |
Correct |
159 ms |
43340 KB |
Output is correct |
43 |
Correct |
253 ms |
68052 KB |
Output is correct |
44 |
Correct |
38 ms |
11340 KB |
Output is correct |
45 |
Correct |
211 ms |
57616 KB |
Output is correct |
46 |
Correct |
172 ms |
129000 KB |
Output is correct |
47 |
Correct |
0 ms |
256 KB |
Output is correct |
48 |
Correct |
1 ms |
212 KB |
Output is correct |
49 |
Correct |
1 ms |
296 KB |
Output is correct |
50 |
Correct |
147 ms |
98084 KB |
Output is correct |
51 |
Correct |
171 ms |
99776 KB |
Output is correct |
52 |
Correct |
204 ms |
53592 KB |
Output is correct |
53 |
Correct |
250 ms |
53860 KB |
Output is correct |
54 |
Correct |
237 ms |
66776 KB |
Output is correct |
55 |
Correct |
199 ms |
52744 KB |
Output is correct |
56 |
Correct |
330 ms |
79600 KB |
Output is correct |
57 |
Correct |
202 ms |
73432 KB |
Output is correct |
58 |
Correct |
294 ms |
78540 KB |
Output is correct |
59 |
Correct |
375 ms |
81428 KB |
Output is correct |
60 |
Correct |
366 ms |
101724 KB |
Output is correct |
61 |
Correct |
333 ms |
103388 KB |
Output is correct |
62 |
Correct |
204 ms |
46672 KB |
Output is correct |
63 |
Correct |
132 ms |
51800 KB |
Output is correct |
64 |
Correct |
3 ms |
2388 KB |
Output is correct |
65 |
Correct |
3 ms |
2388 KB |
Output is correct |
66 |
Correct |
234 ms |
46864 KB |
Output is correct |
67 |
Correct |
18 ms |
13160 KB |
Output is correct |
68 |
Correct |
29 ms |
21704 KB |
Output is correct |
69 |
Correct |
346 ms |
82084 KB |
Output is correct |
70 |
Correct |
56 ms |
43196 KB |
Output is correct |
71 |
Correct |
177 ms |
129516 KB |
Output is correct |
72 |
Correct |
347 ms |
82068 KB |
Output is correct |
73 |
Correct |
237 ms |
46912 KB |
Output is correct |