# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
435332 |
2021-06-23T08:14:25 Z |
jangwonyoung |
Keys (IOI21_keys) |
C++17 |
|
1428 ms |
84972 KB |
//////////////////////////////////////////////////////
#include <vector>
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
typedef vector<int> vi;
const int N=3e5+1;
int n,m;
vector<pair<int,int> >adj[N];
vi alive;
bool vis[N];
bool dead[N];
int gp[N];//group of i-th dude
vector<int>oid;//out = group
int ptr=0;
//in = groups
int l[N];
int mn[N];
vector<int>rdy[N];
vector<int>mem[N];
set<pair<int,pair<int,int> > >outs2;//in = late[color] out = edge
int late[N];//late[color]=last
void upd(int sid,int id,int rid){
for(auto c:adj[id]){
outs2.insert({late[c.fi],{id,c.se}});
}
int cur=rid;
while(true){
auto it=outs2.lower_bound({late[cur],{0,0}});
if(it==outs2.end() || it->fi!=late[cur]) break;
rdy[gp[it->se.fi]].push_back(it->se.se);
outs2.erase(it);
}
late[cur]=alive.size();
}
int merge(int p1,int p2){
if(rdy[p1].size()+mem[p1].size()<rdy[p2].size()+mem[p2].size()){
swap(p1,p2);
}
for(auto c:mem[p2]){
mem[p1].push_back(c);
gp[c]=p1;
}
for(auto c:rdy[p2]){
rdy[p1].push_back(c);
}
mem[p2].clear();rdy[p2].clear();
return p1;
}
int ans[N];
vi find_reachable(vi r,vi u,vi v,vi c){
n=r.size();
for(int i=0; i<u.size() ;i++){
adj[u[i]].push_back({c[i],v[i]});
adj[v[i]].push_back({c[i],u[i]});
}
for(int i=0; i<n ;i++) late[i]=-1-i;
for(int i=0; i<n ;i++){
if(!vis[i]){
vis[i]=true;
gp[i]=++ptr;
mem[gp[i]].push_back(i);
l[ptr]=0;
mn[ptr]=alive.size();
oid.push_back(ptr);
upd(ptr,i,r[i]);
alive.push_back(i);
while(true){
int cur=oid.back(),ly=oid.size();
/*cout << "List " << endl;
for(auto c:oid){
cout << "gp " << c << ": " << l[c] << endl;;
cout << "mem: ";
for(auto d:mem[c]){
cout << d << ' ';
}
cout << endl;
cout << "rdy: ";
for(auto d:rdy[c]){
cout << d << ' ';
}
cout << endl;
}*/
if(rdy[cur].empty()){//cycle end
int cnt=0;
for(auto c:alive){
if(l[gp[c]]==ly-1) ++cnt;
else ans[c]=n+1;
dead[c]=true;
late[r[c]]=-1-r[c];
}
for(auto c:alive) if(l[gp[c]]==ly-1) ans[c]=cnt;
alive.clear();oid.clear();outs2.clear();break;
}
int x=rdy[cur].back();rdy[cur].pop_back();
if(dead[x]){
for(auto c:alive){
dead[c]=true;
late[r[c]]=-1-r[c];
ans[c]=n+1;
}
alive.clear();oid.clear();outs2.clear();break;
}
else if(!vis[x]){
vis[x]=true;
gp[x]=++ptr;
mem[gp[x]].push_back(x);
l[ptr]=ly;
mn[ptr]=alive.size();
oid.push_back(ptr);
upd(ptr,x,r[x]);
alive.push_back(x);
}
else{//collapse layers
while(ly!=l[gp[x]]+1){
ly--;
int bad=mn[oid[ly-1]];
while(true){
auto it=outs2.lower_bound({bad,{0,0}});
if(it==outs2.end()) break;
rdy[gp[it->se.fi]].push_back(it->se.se);
outs2.erase(it);
}
mn[oid[ly-1]]=min(mn[oid[ly-1]],mn[oid[ly]]);
mn[oid[ly]]=min(mn[oid[ly-1]],mn[oid[ly]]);
oid[ly-1]=merge(oid[ly-1],oid[ly]);
l[oid[ly-1]]=ly-1;
oid.pop_back();
}
}
}
}
}
int mn=n;
for(int i=0; i<n ;i++) mn=min(mn,ans[i]);
vector<int>res(n);
for(int i=0; i<n ;i++) res[i]=(ans[i]==mn);
return res;
}
/////////////////////////////////////////////////////
Compilation message
keys.cpp: In function 'vi find_reachable(vi, vi, vi, vi)':
keys.cpp:60:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
60 | for(int i=0; i<u.size() ;i++){
| ~^~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
15 ms |
21452 KB |
Output is correct |
2 |
Correct |
15 ms |
21452 KB |
Output is correct |
3 |
Correct |
15 ms |
21472 KB |
Output is correct |
4 |
Correct |
15 ms |
21384 KB |
Output is correct |
5 |
Correct |
16 ms |
21452 KB |
Output is correct |
6 |
Correct |
15 ms |
21400 KB |
Output is correct |
7 |
Correct |
14 ms |
21452 KB |
Output is correct |
8 |
Correct |
14 ms |
21452 KB |
Output is correct |
9 |
Correct |
19 ms |
21468 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
15 ms |
21452 KB |
Output is correct |
2 |
Correct |
15 ms |
21452 KB |
Output is correct |
3 |
Correct |
15 ms |
21472 KB |
Output is correct |
4 |
Correct |
15 ms |
21384 KB |
Output is correct |
5 |
Correct |
16 ms |
21452 KB |
Output is correct |
6 |
Correct |
15 ms |
21400 KB |
Output is correct |
7 |
Correct |
14 ms |
21452 KB |
Output is correct |
8 |
Correct |
14 ms |
21452 KB |
Output is correct |
9 |
Correct |
19 ms |
21468 KB |
Output is correct |
10 |
Correct |
26 ms |
21508 KB |
Output is correct |
11 |
Correct |
14 ms |
21468 KB |
Output is correct |
12 |
Correct |
17 ms |
21452 KB |
Output is correct |
13 |
Correct |
17 ms |
21452 KB |
Output is correct |
14 |
Correct |
17 ms |
21392 KB |
Output is correct |
15 |
Correct |
14 ms |
21452 KB |
Output is correct |
16 |
Correct |
15 ms |
21460 KB |
Output is correct |
17 |
Correct |
13 ms |
21396 KB |
Output is correct |
18 |
Correct |
14 ms |
21452 KB |
Output is correct |
19 |
Correct |
37 ms |
21452 KB |
Output is correct |
20 |
Correct |
14 ms |
21452 KB |
Output is correct |
21 |
Correct |
14 ms |
21508 KB |
Output is correct |
22 |
Correct |
16 ms |
21452 KB |
Output is correct |
23 |
Correct |
16 ms |
21520 KB |
Output is correct |
24 |
Correct |
16 ms |
21620 KB |
Output is correct |
25 |
Correct |
14 ms |
21452 KB |
Output is correct |
26 |
Correct |
16 ms |
21520 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
15 ms |
21452 KB |
Output is correct |
2 |
Correct |
15 ms |
21452 KB |
Output is correct |
3 |
Correct |
15 ms |
21472 KB |
Output is correct |
4 |
Correct |
15 ms |
21384 KB |
Output is correct |
5 |
Correct |
16 ms |
21452 KB |
Output is correct |
6 |
Correct |
15 ms |
21400 KB |
Output is correct |
7 |
Correct |
14 ms |
21452 KB |
Output is correct |
8 |
Correct |
14 ms |
21452 KB |
Output is correct |
9 |
Correct |
19 ms |
21468 KB |
Output is correct |
10 |
Correct |
26 ms |
21508 KB |
Output is correct |
11 |
Correct |
14 ms |
21468 KB |
Output is correct |
12 |
Correct |
17 ms |
21452 KB |
Output is correct |
13 |
Correct |
17 ms |
21452 KB |
Output is correct |
14 |
Correct |
17 ms |
21392 KB |
Output is correct |
15 |
Correct |
14 ms |
21452 KB |
Output is correct |
16 |
Correct |
15 ms |
21460 KB |
Output is correct |
17 |
Correct |
13 ms |
21396 KB |
Output is correct |
18 |
Correct |
14 ms |
21452 KB |
Output is correct |
19 |
Correct |
37 ms |
21452 KB |
Output is correct |
20 |
Correct |
14 ms |
21452 KB |
Output is correct |
21 |
Correct |
14 ms |
21508 KB |
Output is correct |
22 |
Correct |
16 ms |
21452 KB |
Output is correct |
23 |
Correct |
16 ms |
21520 KB |
Output is correct |
24 |
Correct |
16 ms |
21620 KB |
Output is correct |
25 |
Correct |
14 ms |
21452 KB |
Output is correct |
26 |
Correct |
16 ms |
21520 KB |
Output is correct |
27 |
Correct |
19 ms |
21724 KB |
Output is correct |
28 |
Correct |
15 ms |
21708 KB |
Output is correct |
29 |
Correct |
16 ms |
21748 KB |
Output is correct |
30 |
Correct |
15 ms |
21580 KB |
Output is correct |
31 |
Correct |
16 ms |
21628 KB |
Output is correct |
32 |
Correct |
16 ms |
21468 KB |
Output is correct |
33 |
Correct |
17 ms |
21580 KB |
Output is correct |
34 |
Correct |
16 ms |
21580 KB |
Output is correct |
35 |
Correct |
15 ms |
21580 KB |
Output is correct |
36 |
Correct |
18 ms |
21856 KB |
Output is correct |
37 |
Correct |
15 ms |
21836 KB |
Output is correct |
38 |
Correct |
17 ms |
21836 KB |
Output is correct |
39 |
Correct |
17 ms |
21836 KB |
Output is correct |
40 |
Correct |
16 ms |
21580 KB |
Output is correct |
41 |
Correct |
20 ms |
21580 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
15 ms |
21452 KB |
Output is correct |
2 |
Correct |
15 ms |
21452 KB |
Output is correct |
3 |
Correct |
15 ms |
21472 KB |
Output is correct |
4 |
Correct |
15 ms |
21384 KB |
Output is correct |
5 |
Correct |
16 ms |
21452 KB |
Output is correct |
6 |
Correct |
15 ms |
21400 KB |
Output is correct |
7 |
Correct |
14 ms |
21452 KB |
Output is correct |
8 |
Correct |
14 ms |
21452 KB |
Output is correct |
9 |
Correct |
19 ms |
21468 KB |
Output is correct |
10 |
Correct |
587 ms |
52348 KB |
Output is correct |
11 |
Correct |
874 ms |
72908 KB |
Output is correct |
12 |
Correct |
90 ms |
29508 KB |
Output is correct |
13 |
Correct |
466 ms |
62652 KB |
Output is correct |
14 |
Correct |
292 ms |
72352 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
15 ms |
21452 KB |
Output is correct |
2 |
Correct |
15 ms |
21452 KB |
Output is correct |
3 |
Correct |
15 ms |
21472 KB |
Output is correct |
4 |
Correct |
15 ms |
21384 KB |
Output is correct |
5 |
Correct |
16 ms |
21452 KB |
Output is correct |
6 |
Correct |
15 ms |
21400 KB |
Output is correct |
7 |
Correct |
14 ms |
21452 KB |
Output is correct |
8 |
Correct |
14 ms |
21452 KB |
Output is correct |
9 |
Correct |
19 ms |
21468 KB |
Output is correct |
10 |
Correct |
26 ms |
21508 KB |
Output is correct |
11 |
Correct |
14 ms |
21468 KB |
Output is correct |
12 |
Correct |
17 ms |
21452 KB |
Output is correct |
13 |
Correct |
17 ms |
21452 KB |
Output is correct |
14 |
Correct |
17 ms |
21392 KB |
Output is correct |
15 |
Correct |
14 ms |
21452 KB |
Output is correct |
16 |
Correct |
15 ms |
21460 KB |
Output is correct |
17 |
Correct |
13 ms |
21396 KB |
Output is correct |
18 |
Correct |
14 ms |
21452 KB |
Output is correct |
19 |
Correct |
37 ms |
21452 KB |
Output is correct |
20 |
Correct |
14 ms |
21452 KB |
Output is correct |
21 |
Correct |
14 ms |
21508 KB |
Output is correct |
22 |
Correct |
16 ms |
21452 KB |
Output is correct |
23 |
Correct |
16 ms |
21520 KB |
Output is correct |
24 |
Correct |
16 ms |
21620 KB |
Output is correct |
25 |
Correct |
14 ms |
21452 KB |
Output is correct |
26 |
Correct |
16 ms |
21520 KB |
Output is correct |
27 |
Correct |
19 ms |
21724 KB |
Output is correct |
28 |
Correct |
15 ms |
21708 KB |
Output is correct |
29 |
Correct |
16 ms |
21748 KB |
Output is correct |
30 |
Correct |
15 ms |
21580 KB |
Output is correct |
31 |
Correct |
16 ms |
21628 KB |
Output is correct |
32 |
Correct |
16 ms |
21468 KB |
Output is correct |
33 |
Correct |
17 ms |
21580 KB |
Output is correct |
34 |
Correct |
16 ms |
21580 KB |
Output is correct |
35 |
Correct |
15 ms |
21580 KB |
Output is correct |
36 |
Correct |
18 ms |
21856 KB |
Output is correct |
37 |
Correct |
15 ms |
21836 KB |
Output is correct |
38 |
Correct |
17 ms |
21836 KB |
Output is correct |
39 |
Correct |
17 ms |
21836 KB |
Output is correct |
40 |
Correct |
16 ms |
21580 KB |
Output is correct |
41 |
Correct |
20 ms |
21580 KB |
Output is correct |
42 |
Correct |
587 ms |
52348 KB |
Output is correct |
43 |
Correct |
874 ms |
72908 KB |
Output is correct |
44 |
Correct |
90 ms |
29508 KB |
Output is correct |
45 |
Correct |
466 ms |
62652 KB |
Output is correct |
46 |
Correct |
292 ms |
72352 KB |
Output is correct |
47 |
Correct |
17 ms |
21452 KB |
Output is correct |
48 |
Correct |
14 ms |
21404 KB |
Output is correct |
49 |
Correct |
17 ms |
21372 KB |
Output is correct |
50 |
Correct |
324 ms |
72292 KB |
Output is correct |
51 |
Correct |
335 ms |
71696 KB |
Output is correct |
52 |
Correct |
327 ms |
50056 KB |
Output is correct |
53 |
Correct |
393 ms |
50068 KB |
Output is correct |
54 |
Correct |
401 ms |
50088 KB |
Output is correct |
55 |
Correct |
693 ms |
60772 KB |
Output is correct |
56 |
Correct |
648 ms |
64356 KB |
Output is correct |
57 |
Correct |
751 ms |
79384 KB |
Output is correct |
58 |
Correct |
751 ms |
69052 KB |
Output is correct |
59 |
Correct |
1175 ms |
75660 KB |
Output is correct |
60 |
Correct |
942 ms |
62664 KB |
Output is correct |
61 |
Correct |
1209 ms |
84972 KB |
Output is correct |
62 |
Correct |
683 ms |
59916 KB |
Output is correct |
63 |
Correct |
298 ms |
52612 KB |
Output is correct |
64 |
Correct |
18 ms |
22348 KB |
Output is correct |
65 |
Correct |
19 ms |
22336 KB |
Output is correct |
66 |
Correct |
666 ms |
59628 KB |
Output is correct |
67 |
Correct |
69 ms |
26456 KB |
Output is correct |
68 |
Correct |
69 ms |
29824 KB |
Output is correct |
69 |
Correct |
1130 ms |
69092 KB |
Output is correct |
70 |
Correct |
130 ms |
38204 KB |
Output is correct |
71 |
Correct |
321 ms |
72304 KB |
Output is correct |
72 |
Correct |
1428 ms |
75648 KB |
Output is correct |
73 |
Correct |
702 ms |
59496 KB |
Output is correct |