#include <bits/stdc++.h>
#pragma GCC optimize("O3")
using namespace std;
// typedef int int;
typedef pair<int,int>pairll;
#define N 150007
#define pb push_back
#define fr first
#define sc second
vector<int> ans;
int p[2*N],f[2*N],n,m,d[2*N],sz[2*N],fr[2*N];
unordered_map<int,vector<int> >v[2*N];
vector<int>v2[2*N];
vector<pairll> v1[2*N];
set<int>s[2*N],del[2*N],a[2*N];
int P(int x){
if(p[x]!=x)p[x]=P(p[x]);
return p[x];
}
void A(int x,int y){
if(P(x)==P(y))return ;
x=P(x);
y=P(y);
p[y]=x;
if(v2[x].size()<v2[y].size())swap(v2[x],v2[y]);
for(auto& val : v2[y]) v2[x].push_back(val);
if(v1[x].size()<v1[y].size()){
swap(v1[x],v1[y]);
}
for(auto& val : v1[y]) v1[x].push_back(val);
if(a[x].size()<a[y].size()){
swap(s[x],s[y]);
swap(v[x],v[y]);
swap(a[x],a[y]);
}
for(auto& it:a[y]){
if(s[x].count(it)){
for(auto& val : v[y][it]) v2[x].push_back(val);
v[x][it].clear();
}else{
if(s[y].count(it)!=0){
for(auto& val : v[x][it]) v2[x].push_back(val);
s[x].insert(it);
v[y][it].clear();
}else{
if(v[y][it].size()>v[x][it].size())swap(v[x][it],v[y][it]);
for(auto& val : v[y][it]) v[x][it].push_back(val);
}
}
a[x].insert(it);
}
sz[x]+=sz[y];
return ;
}
int S(int x,int y){
x=P(x);
//cout<<x<<" "<<y<<" "<<f[x]<<" "<<s[x].size()<<endl;
if(f[x]==2)return x;
if(f[x]==1)return 0;
//cout<<1<<endl;
f[x]=2;
while(v2[x].size()>0){
int m1=v2[x].back();
v2[x].pop_back();
if(P(m1)!=P(x)){
int g=S(m1,x);
if(g!=0){
if(x==g){
x=P(x);
}else{
A(x,y);
return g;
}
}
}
}
f[x]=1;
return 0;
}
vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> w, vector<int> c) {
n=r.size();
for(int i=1;i<=n;i++){
d[i]=r[i-1];
p[i]=i;
s[i].insert(d[i]);
sz[i]=1;
}
m=u.size();
for(int i=0;i<m;i++){
u[i]++;
w[i]++;
v[u[i]][c[i]].pb(w[i]);
v[w[i]][c[i]].pb(u[i]);
v1[u[i]].emplace_back(c[i],w[i]);
v1[w[i]].emplace_back(c[i],u[i]);
if(c[i]==d[u[i]]){
v2[u[i]].pb(w[i]);
}
if(c[i]==d[w[i]]){
v2[w[i]].pb(u[i]);
}
a[u[i]].insert(c[i]);
a[w[i]].insert(c[i]);
}
for(int i=1;i<=n;i++){
if(f[i]==0)S(i,i);
}
for(int i=1;i<=n;i++){
s[i].clear();
}
for(int i=1;i<=n;i++){
s[P(i)].insert(d[i]);
}
int mn=n;
for(int i=1;i<=n;i++){
if(p[i]==i){
for(auto& it:v1[i]){
if(s[i].count(it.fr)!=0 && P(it.sc)!=i)fr[i]=1;
}
if(fr[i]==0) mn=min(mn,sz[i]);
}
//cout<<i<<" "<<P(i)<<endl;
}
ans.resize(n);
for(int i=1;i<=n;i++){
if(fr[P(i)]==0 && sz[P(i)]==mn)ans[i-1]=1;
}
return ans;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
29 ms |
73112 KB |
Output is correct |
2 |
Correct |
29 ms |
73136 KB |
Output is correct |
3 |
Correct |
32 ms |
73080 KB |
Output is correct |
4 |
Correct |
34 ms |
73180 KB |
Output is correct |
5 |
Correct |
36 ms |
73044 KB |
Output is correct |
6 |
Correct |
37 ms |
73068 KB |
Output is correct |
7 |
Correct |
30 ms |
73008 KB |
Output is correct |
8 |
Correct |
29 ms |
73144 KB |
Output is correct |
9 |
Correct |
29 ms |
73188 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
29 ms |
73112 KB |
Output is correct |
2 |
Correct |
29 ms |
73136 KB |
Output is correct |
3 |
Correct |
32 ms |
73080 KB |
Output is correct |
4 |
Correct |
34 ms |
73180 KB |
Output is correct |
5 |
Correct |
36 ms |
73044 KB |
Output is correct |
6 |
Correct |
37 ms |
73068 KB |
Output is correct |
7 |
Correct |
30 ms |
73008 KB |
Output is correct |
8 |
Correct |
29 ms |
73144 KB |
Output is correct |
9 |
Correct |
29 ms |
73188 KB |
Output is correct |
10 |
Correct |
29 ms |
73120 KB |
Output is correct |
11 |
Correct |
32 ms |
73212 KB |
Output is correct |
12 |
Correct |
31 ms |
73212 KB |
Output is correct |
13 |
Correct |
35 ms |
73044 KB |
Output is correct |
14 |
Correct |
34 ms |
73108 KB |
Output is correct |
15 |
Correct |
37 ms |
73128 KB |
Output is correct |
16 |
Correct |
31 ms |
73124 KB |
Output is correct |
17 |
Correct |
32 ms |
73004 KB |
Output is correct |
18 |
Correct |
36 ms |
73160 KB |
Output is correct |
19 |
Correct |
28 ms |
73044 KB |
Output is correct |
20 |
Correct |
32 ms |
73112 KB |
Output is correct |
21 |
Correct |
29 ms |
73184 KB |
Output is correct |
22 |
Correct |
32 ms |
73156 KB |
Output is correct |
23 |
Correct |
30 ms |
73232 KB |
Output is correct |
24 |
Correct |
31 ms |
73240 KB |
Output is correct |
25 |
Correct |
36 ms |
73244 KB |
Output is correct |
26 |
Correct |
31 ms |
73196 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
29 ms |
73112 KB |
Output is correct |
2 |
Correct |
29 ms |
73136 KB |
Output is correct |
3 |
Correct |
32 ms |
73080 KB |
Output is correct |
4 |
Correct |
34 ms |
73180 KB |
Output is correct |
5 |
Correct |
36 ms |
73044 KB |
Output is correct |
6 |
Correct |
37 ms |
73068 KB |
Output is correct |
7 |
Correct |
30 ms |
73008 KB |
Output is correct |
8 |
Correct |
29 ms |
73144 KB |
Output is correct |
9 |
Correct |
29 ms |
73188 KB |
Output is correct |
10 |
Correct |
29 ms |
73120 KB |
Output is correct |
11 |
Correct |
32 ms |
73212 KB |
Output is correct |
12 |
Correct |
31 ms |
73212 KB |
Output is correct |
13 |
Correct |
35 ms |
73044 KB |
Output is correct |
14 |
Correct |
34 ms |
73108 KB |
Output is correct |
15 |
Correct |
37 ms |
73128 KB |
Output is correct |
16 |
Correct |
31 ms |
73124 KB |
Output is correct |
17 |
Correct |
32 ms |
73004 KB |
Output is correct |
18 |
Correct |
36 ms |
73160 KB |
Output is correct |
19 |
Correct |
28 ms |
73044 KB |
Output is correct |
20 |
Correct |
32 ms |
73112 KB |
Output is correct |
21 |
Correct |
29 ms |
73184 KB |
Output is correct |
22 |
Correct |
32 ms |
73156 KB |
Output is correct |
23 |
Correct |
30 ms |
73232 KB |
Output is correct |
24 |
Correct |
31 ms |
73240 KB |
Output is correct |
25 |
Correct |
36 ms |
73244 KB |
Output is correct |
26 |
Correct |
31 ms |
73196 KB |
Output is correct |
27 |
Correct |
32 ms |
74068 KB |
Output is correct |
28 |
Correct |
41 ms |
74068 KB |
Output is correct |
29 |
Correct |
35 ms |
74088 KB |
Output is correct |
30 |
Correct |
32 ms |
73712 KB |
Output is correct |
31 |
Correct |
38 ms |
73484 KB |
Output is correct |
32 |
Correct |
36 ms |
73248 KB |
Output is correct |
33 |
Correct |
31 ms |
73672 KB |
Output is correct |
34 |
Correct |
31 ms |
73636 KB |
Output is correct |
35 |
Correct |
32 ms |
73684 KB |
Output is correct |
36 |
Correct |
34 ms |
74376 KB |
Output is correct |
37 |
Correct |
34 ms |
74324 KB |
Output is correct |
38 |
Correct |
33 ms |
74552 KB |
Output is correct |
39 |
Correct |
35 ms |
74600 KB |
Output is correct |
40 |
Correct |
32 ms |
73716 KB |
Output is correct |
41 |
Correct |
33 ms |
74144 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
29 ms |
73112 KB |
Output is correct |
2 |
Correct |
29 ms |
73136 KB |
Output is correct |
3 |
Correct |
32 ms |
73080 KB |
Output is correct |
4 |
Correct |
34 ms |
73180 KB |
Output is correct |
5 |
Correct |
36 ms |
73044 KB |
Output is correct |
6 |
Correct |
37 ms |
73068 KB |
Output is correct |
7 |
Correct |
30 ms |
73008 KB |
Output is correct |
8 |
Correct |
29 ms |
73144 KB |
Output is correct |
9 |
Correct |
29 ms |
73188 KB |
Output is correct |
10 |
Correct |
1109 ms |
176620 KB |
Output is correct |
11 |
Correct |
909 ms |
201120 KB |
Output is correct |
12 |
Correct |
171 ms |
107292 KB |
Output is correct |
13 |
Correct |
860 ms |
240256 KB |
Output is correct |
14 |
Correct |
364 ms |
225340 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
29 ms |
73112 KB |
Output is correct |
2 |
Correct |
29 ms |
73136 KB |
Output is correct |
3 |
Correct |
32 ms |
73080 KB |
Output is correct |
4 |
Correct |
34 ms |
73180 KB |
Output is correct |
5 |
Correct |
36 ms |
73044 KB |
Output is correct |
6 |
Correct |
37 ms |
73068 KB |
Output is correct |
7 |
Correct |
30 ms |
73008 KB |
Output is correct |
8 |
Correct |
29 ms |
73144 KB |
Output is correct |
9 |
Correct |
29 ms |
73188 KB |
Output is correct |
10 |
Correct |
29 ms |
73120 KB |
Output is correct |
11 |
Correct |
32 ms |
73212 KB |
Output is correct |
12 |
Correct |
31 ms |
73212 KB |
Output is correct |
13 |
Correct |
35 ms |
73044 KB |
Output is correct |
14 |
Correct |
34 ms |
73108 KB |
Output is correct |
15 |
Correct |
37 ms |
73128 KB |
Output is correct |
16 |
Correct |
31 ms |
73124 KB |
Output is correct |
17 |
Correct |
32 ms |
73004 KB |
Output is correct |
18 |
Correct |
36 ms |
73160 KB |
Output is correct |
19 |
Correct |
28 ms |
73044 KB |
Output is correct |
20 |
Correct |
32 ms |
73112 KB |
Output is correct |
21 |
Correct |
29 ms |
73184 KB |
Output is correct |
22 |
Correct |
32 ms |
73156 KB |
Output is correct |
23 |
Correct |
30 ms |
73232 KB |
Output is correct |
24 |
Correct |
31 ms |
73240 KB |
Output is correct |
25 |
Correct |
36 ms |
73244 KB |
Output is correct |
26 |
Correct |
31 ms |
73196 KB |
Output is correct |
27 |
Correct |
32 ms |
74068 KB |
Output is correct |
28 |
Correct |
41 ms |
74068 KB |
Output is correct |
29 |
Correct |
35 ms |
74088 KB |
Output is correct |
30 |
Correct |
32 ms |
73712 KB |
Output is correct |
31 |
Correct |
38 ms |
73484 KB |
Output is correct |
32 |
Correct |
36 ms |
73248 KB |
Output is correct |
33 |
Correct |
31 ms |
73672 KB |
Output is correct |
34 |
Correct |
31 ms |
73636 KB |
Output is correct |
35 |
Correct |
32 ms |
73684 KB |
Output is correct |
36 |
Correct |
34 ms |
74376 KB |
Output is correct |
37 |
Correct |
34 ms |
74324 KB |
Output is correct |
38 |
Correct |
33 ms |
74552 KB |
Output is correct |
39 |
Correct |
35 ms |
74600 KB |
Output is correct |
40 |
Correct |
32 ms |
73716 KB |
Output is correct |
41 |
Correct |
33 ms |
74144 KB |
Output is correct |
42 |
Correct |
1109 ms |
176620 KB |
Output is correct |
43 |
Correct |
909 ms |
201120 KB |
Output is correct |
44 |
Correct |
171 ms |
107292 KB |
Output is correct |
45 |
Correct |
860 ms |
240256 KB |
Output is correct |
46 |
Correct |
364 ms |
225340 KB |
Output is correct |
47 |
Correct |
36 ms |
73112 KB |
Output is correct |
48 |
Correct |
33 ms |
73120 KB |
Output is correct |
49 |
Correct |
30 ms |
73120 KB |
Output is correct |
50 |
Correct |
343 ms |
216272 KB |
Output is correct |
51 |
Correct |
434 ms |
200020 KB |
Output is correct |
52 |
Correct |
533 ms |
177240 KB |
Output is correct |
53 |
Correct |
545 ms |
177124 KB |
Output is correct |
54 |
Correct |
578 ms |
177140 KB |
Output is correct |
55 |
Correct |
1288 ms |
193060 KB |
Output is correct |
56 |
Correct |
632 ms |
210000 KB |
Output is correct |
57 |
Correct |
657 ms |
188176 KB |
Output is correct |
58 |
Correct |
1327 ms |
236660 KB |
Output is correct |
59 |
Correct |
2047 ms |
255188 KB |
Output is correct |
60 |
Correct |
1857 ms |
251548 KB |
Output is correct |
61 |
Correct |
1895 ms |
251584 KB |
Output is correct |
62 |
Correct |
2047 ms |
405716 KB |
Output is correct |
63 |
Correct |
461 ms |
220488 KB |
Output is correct |
64 |
Correct |
36 ms |
75732 KB |
Output is correct |
65 |
Correct |
36 ms |
75724 KB |
Output is correct |
66 |
Correct |
2071 ms |
405400 KB |
Output is correct |
67 |
Correct |
62 ms |
88244 KB |
Output is correct |
68 |
Correct |
81 ms |
98512 KB |
Output is correct |
69 |
Correct |
2056 ms |
247344 KB |
Output is correct |
70 |
Correct |
179 ms |
123804 KB |
Output is correct |
71 |
Correct |
366 ms |
225416 KB |
Output is correct |
72 |
Correct |
1966 ms |
248992 KB |
Output is correct |
73 |
Correct |
2016 ms |
405288 KB |
Output is correct |