# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
590412 |
2022-07-05T22:31:07 Z |
oleh1421 |
Keys (IOI21_keys) |
C++17 |
|
2166 ms |
117956 KB |
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N=500100;
vector<pair<int,int> >g[N];
vector<int>go[N];
vector<int>go1[N];
int ind[N];
int ind1[N];
int cnt[N];
bool used[N];
vector<int>order;
void dfs1(int v){
used[v]=true;
for (int to:go1[v]){
if (!used[to]){
dfs1(to);
}
}
order.push_back(v);
}
void dfs(int v){
used[v]=true;
for (int to:go[v]){
if (!used[to]){
dfs(to);
}
}
order.push_back(v);
}
vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c) {
int n=r.size();
int m=u.size();
for (int i=0;i<m;i++){
g[u[i]].push_back({c[i],v[i]});
g[v[i]].push_back({c[i],u[i]});
}
for (int i=0;i<n;i++){
sort(g[i].begin(),g[i].end());
}
vector<pair<int,int> >ans;
vector<vector<int> >comp;
for (int i=0;i<n;i++){
comp.push_back({i});
ind[i]=i;
}
int Cnt=-1;
while (!comp.empty()){
// if ((int)comp.size()>Cnt) exit(1);
Cnt++;
// cout<<"IT\n";
for (auto u:comp){
set<int>st;
for (int v:u) st.insert(r[v]);
// for (int x:st) cout<<x<<" ";
// cout<<endl;
if (st.size()<Cnt) goto A;
int cnt=0;
for (int v:u){
for (auto [c,to]:g[v]){
if (st.find(c)==st.end()) continue;
if (ind[v]==ind[to] || ind[to]==-1) continue;
go[ind[v]].push_back(ind[to]);
go1[ind[to]].push_back(ind[v]);
}
}
if (go[ind[u[0]]].empty()){
for (int v:u){
ans.push_back({u.size(),v});
}
}
}
bool ok=false;
for (int i=0;i<n;i++){
if (ind[i]==i && !used[i]){
if (go[i].empty()){
ok=true;
dfs1(i);
}
}
}
vector<int>V;
for (int i=0;i<n;i++){
if (ind[i]!=i) continue;
if (!used[i]){
V.push_back(i);
}
}
for (int i=0;i<n;i++){
if (ind[i]==-1) continue;
if (used[ind[i]]) ind[i]=-1;
}
order.clear();
for (int i:V){
if (!used[i]) dfs(i);
}
reverse(order.begin(),order.end());
V=order;
order.clear();
for (int i:V) used[i]=false;
int last=comp.size();
comp.clear();
int cn=0;
set<int>st;
for (int i:V){
// cout<<"X "<<i<<endl;
if (!used[i]){
dfs1(i);
for (int j:order) ind1[j]=i;
if (order.size()>1) ok=true;
order.clear();
cn++;
st.insert(i);
}
}
for (int i=0;i<n;i++){
go[i].clear();
go1[i].clear();
cnt[i]=0;
used[i]=false;
}
for (int i=0;i<n;i++){
if (ind[i]==-1) continue;
ind[i]=ind1[ind[i]];
go[ind[i]].push_back(i);
}
for (int i=0;i<n;i++){
if (!go[i].empty()) {
if (st.find(i)==st.end()) exit(1);
comp.push_back(go[i]);
}
go[i].clear();
}
}
A:;
sort(ans.begin(),ans.end());
while (!ans.empty() && ans[0].first<ans.back().first) ans.pop_back();
vector<int>bt(n,0);
for (auto cur:ans) bt[cur.second]=1;
return bt;
}
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:59:26: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
59 | if (st.size()<Cnt) goto A;
| ~~~~~~~~~^~~~
keys.cpp:60:17: warning: unused variable 'cnt' [-Wunused-variable]
60 | int cnt=0;
| ^~~
keys.cpp:76:14: warning: variable 'ok' set but not used [-Wunused-but-set-variable]
76 | bool ok=false;
| ^~
keys.cpp:105:13: warning: unused variable 'last' [-Wunused-variable]
105 | int last=comp.size();
| ^~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
17 ms |
35540 KB |
Output is correct |
2 |
Correct |
17 ms |
35540 KB |
Output is correct |
3 |
Correct |
17 ms |
35548 KB |
Output is correct |
4 |
Correct |
18 ms |
35596 KB |
Output is correct |
5 |
Correct |
17 ms |
35464 KB |
Output is correct |
6 |
Correct |
17 ms |
35508 KB |
Output is correct |
7 |
Correct |
20 ms |
35540 KB |
Output is correct |
8 |
Correct |
18 ms |
35540 KB |
Output is correct |
9 |
Correct |
20 ms |
35540 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
17 ms |
35540 KB |
Output is correct |
2 |
Correct |
17 ms |
35540 KB |
Output is correct |
3 |
Correct |
17 ms |
35548 KB |
Output is correct |
4 |
Correct |
18 ms |
35596 KB |
Output is correct |
5 |
Correct |
17 ms |
35464 KB |
Output is correct |
6 |
Correct |
17 ms |
35508 KB |
Output is correct |
7 |
Correct |
20 ms |
35540 KB |
Output is correct |
8 |
Correct |
18 ms |
35540 KB |
Output is correct |
9 |
Correct |
20 ms |
35540 KB |
Output is correct |
10 |
Correct |
18 ms |
35564 KB |
Output is correct |
11 |
Correct |
21 ms |
35460 KB |
Output is correct |
12 |
Correct |
17 ms |
35540 KB |
Output is correct |
13 |
Correct |
18 ms |
35532 KB |
Output is correct |
14 |
Correct |
17 ms |
35540 KB |
Output is correct |
15 |
Correct |
17 ms |
35580 KB |
Output is correct |
16 |
Correct |
18 ms |
35436 KB |
Output is correct |
17 |
Correct |
16 ms |
35528 KB |
Output is correct |
18 |
Correct |
17 ms |
35504 KB |
Output is correct |
19 |
Correct |
17 ms |
35556 KB |
Output is correct |
20 |
Correct |
17 ms |
35448 KB |
Output is correct |
21 |
Correct |
17 ms |
35540 KB |
Output is correct |
22 |
Correct |
20 ms |
35504 KB |
Output is correct |
23 |
Correct |
17 ms |
35540 KB |
Output is correct |
24 |
Correct |
17 ms |
35540 KB |
Output is correct |
25 |
Correct |
17 ms |
35540 KB |
Output is correct |
26 |
Correct |
18 ms |
35532 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
17 ms |
35540 KB |
Output is correct |
2 |
Correct |
17 ms |
35540 KB |
Output is correct |
3 |
Correct |
17 ms |
35548 KB |
Output is correct |
4 |
Correct |
18 ms |
35596 KB |
Output is correct |
5 |
Correct |
17 ms |
35464 KB |
Output is correct |
6 |
Correct |
17 ms |
35508 KB |
Output is correct |
7 |
Correct |
20 ms |
35540 KB |
Output is correct |
8 |
Correct |
18 ms |
35540 KB |
Output is correct |
9 |
Correct |
20 ms |
35540 KB |
Output is correct |
10 |
Correct |
18 ms |
35564 KB |
Output is correct |
11 |
Correct |
21 ms |
35460 KB |
Output is correct |
12 |
Correct |
17 ms |
35540 KB |
Output is correct |
13 |
Correct |
18 ms |
35532 KB |
Output is correct |
14 |
Correct |
17 ms |
35540 KB |
Output is correct |
15 |
Correct |
17 ms |
35580 KB |
Output is correct |
16 |
Correct |
18 ms |
35436 KB |
Output is correct |
17 |
Correct |
16 ms |
35528 KB |
Output is correct |
18 |
Correct |
17 ms |
35504 KB |
Output is correct |
19 |
Correct |
17 ms |
35556 KB |
Output is correct |
20 |
Correct |
17 ms |
35448 KB |
Output is correct |
21 |
Correct |
17 ms |
35540 KB |
Output is correct |
22 |
Correct |
20 ms |
35504 KB |
Output is correct |
23 |
Correct |
17 ms |
35540 KB |
Output is correct |
24 |
Correct |
17 ms |
35540 KB |
Output is correct |
25 |
Correct |
17 ms |
35540 KB |
Output is correct |
26 |
Correct |
18 ms |
35532 KB |
Output is correct |
27 |
Correct |
20 ms |
35796 KB |
Output is correct |
28 |
Correct |
18 ms |
35796 KB |
Output is correct |
29 |
Correct |
19 ms |
35780 KB |
Output is correct |
30 |
Correct |
19 ms |
35772 KB |
Output is correct |
31 |
Correct |
17 ms |
35668 KB |
Output is correct |
32 |
Correct |
17 ms |
35580 KB |
Output is correct |
33 |
Correct |
18 ms |
35704 KB |
Output is correct |
34 |
Correct |
17 ms |
35796 KB |
Output is correct |
35 |
Correct |
16 ms |
35668 KB |
Output is correct |
36 |
Correct |
18 ms |
35924 KB |
Output is correct |
37 |
Correct |
18 ms |
35980 KB |
Output is correct |
38 |
Correct |
19 ms |
35924 KB |
Output is correct |
39 |
Correct |
19 ms |
36052 KB |
Output is correct |
40 |
Correct |
22 ms |
35668 KB |
Output is correct |
41 |
Correct |
21 ms |
35748 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
17 ms |
35540 KB |
Output is correct |
2 |
Correct |
17 ms |
35540 KB |
Output is correct |
3 |
Correct |
17 ms |
35548 KB |
Output is correct |
4 |
Correct |
18 ms |
35596 KB |
Output is correct |
5 |
Correct |
17 ms |
35464 KB |
Output is correct |
6 |
Correct |
17 ms |
35508 KB |
Output is correct |
7 |
Correct |
20 ms |
35540 KB |
Output is correct |
8 |
Correct |
18 ms |
35540 KB |
Output is correct |
9 |
Correct |
20 ms |
35540 KB |
Output is correct |
10 |
Correct |
320 ms |
67976 KB |
Output is correct |
11 |
Correct |
512 ms |
108548 KB |
Output is correct |
12 |
Correct |
100 ms |
47440 KB |
Output is correct |
13 |
Correct |
495 ms |
100428 KB |
Output is correct |
14 |
Correct |
270 ms |
117340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
17 ms |
35540 KB |
Output is correct |
2 |
Correct |
17 ms |
35540 KB |
Output is correct |
3 |
Correct |
17 ms |
35548 KB |
Output is correct |
4 |
Correct |
18 ms |
35596 KB |
Output is correct |
5 |
Correct |
17 ms |
35464 KB |
Output is correct |
6 |
Correct |
17 ms |
35508 KB |
Output is correct |
7 |
Correct |
20 ms |
35540 KB |
Output is correct |
8 |
Correct |
18 ms |
35540 KB |
Output is correct |
9 |
Correct |
20 ms |
35540 KB |
Output is correct |
10 |
Correct |
18 ms |
35564 KB |
Output is correct |
11 |
Correct |
21 ms |
35460 KB |
Output is correct |
12 |
Correct |
17 ms |
35540 KB |
Output is correct |
13 |
Correct |
18 ms |
35532 KB |
Output is correct |
14 |
Correct |
17 ms |
35540 KB |
Output is correct |
15 |
Correct |
17 ms |
35580 KB |
Output is correct |
16 |
Correct |
18 ms |
35436 KB |
Output is correct |
17 |
Correct |
16 ms |
35528 KB |
Output is correct |
18 |
Correct |
17 ms |
35504 KB |
Output is correct |
19 |
Correct |
17 ms |
35556 KB |
Output is correct |
20 |
Correct |
17 ms |
35448 KB |
Output is correct |
21 |
Correct |
17 ms |
35540 KB |
Output is correct |
22 |
Correct |
20 ms |
35504 KB |
Output is correct |
23 |
Correct |
17 ms |
35540 KB |
Output is correct |
24 |
Correct |
17 ms |
35540 KB |
Output is correct |
25 |
Correct |
17 ms |
35540 KB |
Output is correct |
26 |
Correct |
18 ms |
35532 KB |
Output is correct |
27 |
Correct |
20 ms |
35796 KB |
Output is correct |
28 |
Correct |
18 ms |
35796 KB |
Output is correct |
29 |
Correct |
19 ms |
35780 KB |
Output is correct |
30 |
Correct |
19 ms |
35772 KB |
Output is correct |
31 |
Correct |
17 ms |
35668 KB |
Output is correct |
32 |
Correct |
17 ms |
35580 KB |
Output is correct |
33 |
Correct |
18 ms |
35704 KB |
Output is correct |
34 |
Correct |
17 ms |
35796 KB |
Output is correct |
35 |
Correct |
16 ms |
35668 KB |
Output is correct |
36 |
Correct |
18 ms |
35924 KB |
Output is correct |
37 |
Correct |
18 ms |
35980 KB |
Output is correct |
38 |
Correct |
19 ms |
35924 KB |
Output is correct |
39 |
Correct |
19 ms |
36052 KB |
Output is correct |
40 |
Correct |
22 ms |
35668 KB |
Output is correct |
41 |
Correct |
21 ms |
35748 KB |
Output is correct |
42 |
Correct |
320 ms |
67976 KB |
Output is correct |
43 |
Correct |
512 ms |
108548 KB |
Output is correct |
44 |
Correct |
100 ms |
47440 KB |
Output is correct |
45 |
Correct |
495 ms |
100428 KB |
Output is correct |
46 |
Correct |
270 ms |
117340 KB |
Output is correct |
47 |
Correct |
17 ms |
35544 KB |
Output is correct |
48 |
Correct |
22 ms |
35532 KB |
Output is correct |
49 |
Correct |
20 ms |
35540 KB |
Output is correct |
50 |
Correct |
259 ms |
112100 KB |
Output is correct |
51 |
Correct |
274 ms |
114416 KB |
Output is correct |
52 |
Correct |
255 ms |
76344 KB |
Output is correct |
53 |
Correct |
234 ms |
76268 KB |
Output is correct |
54 |
Correct |
245 ms |
76332 KB |
Output is correct |
55 |
Correct |
306 ms |
72168 KB |
Output is correct |
56 |
Correct |
476 ms |
107188 KB |
Output is correct |
57 |
Correct |
315 ms |
99824 KB |
Output is correct |
58 |
Correct |
282 ms |
97516 KB |
Output is correct |
59 |
Correct |
599 ms |
94076 KB |
Output is correct |
60 |
Correct |
346 ms |
96372 KB |
Output is correct |
61 |
Correct |
661 ms |
106488 KB |
Output is correct |
62 |
Correct |
2053 ms |
86644 KB |
Output is correct |
63 |
Correct |
297 ms |
82856 KB |
Output is correct |
64 |
Correct |
23 ms |
36952 KB |
Output is correct |
65 |
Correct |
19 ms |
36880 KB |
Output is correct |
66 |
Correct |
2166 ms |
86656 KB |
Output is correct |
67 |
Correct |
41 ms |
43652 KB |
Output is correct |
68 |
Correct |
57 ms |
49020 KB |
Output is correct |
69 |
Correct |
586 ms |
94440 KB |
Output is correct |
70 |
Correct |
103 ms |
62736 KB |
Output is correct |
71 |
Correct |
276 ms |
117956 KB |
Output is correct |
72 |
Correct |
584 ms |
94184 KB |
Output is correct |
73 |
Correct |
2023 ms |
86664 KB |
Output is correct |