# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
600484 |
2022-07-20T22:34:35 Z |
2fat2code |
Keys (IOI21_keys) |
C++17 |
|
1962 ms |
61988 KB |
#include <bits/stdc++.h>
#define fr first
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#define sc second
#define all(s) s.begin(), s.end()
#define rc(s) return cout << s, 0
using namespace std;
const int nmax = 300005;
int n, m, par[nmax], kek[nmax];
bitset<nmax>viz, keys;
vector<pair<int,int>>nod[nmax];
vector<int>waiting[nmax];
vector<pair<int,int>>change;
vector<int>lmao;
int findpar(int x){
if(par[x] != x){
par[x] = findpar(par[x]);
}
return par[x];
}
void bfs(int s, vector<int>&type){
keys.reset();
viz.reset();
queue<int>q;
q.push(s);
lmao.push_back(s);
viz[s] = 1;
vector<int>zb;
while(q.size()){
auto it = q.front();
keys[type[it-1]] = 1;
q.pop();
for(auto it1 : waiting[type[it-1]]){
if(findpar(it1) != s){
change.push_back({s, par[it1]});
goto next;
}
if(!viz[it1]){
q.push(it1);
lmao.push_back(it1);
viz[it1] = 1;
}
}
waiting[type[it-1]].clear();
for(auto it1 : nod[it]){
if(findpar(it1.fr) != s && keys[it1.sc]){
change.push_back({s, par[it1.fr]});
goto next;
}
if(keys[it1.sc] && !viz[it1.fr]){
q.push(it1.fr);
viz[it1.fr] = 1;
lmao.push_back(it1.fr);
}
else if(!keys[it1.sc]){
waiting[it1.sc].push_back(it1.fr);
zb.push_back(it1.sc);
}
}
}
next:;
for(auto it : zb) waiting[it].clear();
}
vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c) {
n = r.size();
vector<int>ans(n);
m = u.size();
for(int i=0;i<m;i++){
nod[u[i]+1].push_back({v[i]+1, c[i]});
nod[v[i]+1].push_back({u[i]+1, c[i]});
}
for(int i=1;i<=n;i++) par[i] = i;
while(true){
change.clear();
vector<int>roots;
for(int i=1;i<=n;i++){
if(par[i] == i){
roots.push_back(i);
}
}
for(auto it : roots){
bfs(it, r);
}
if(!change.size()) break;
else{
for(auto it : change){
if(findpar(it.fr) != findpar(it.sc)){
par[it.fr] = it.sc;
}
}
}
}
for(int i=1;i<=n;i++){
if(par[i] == i){
lmao.clear();
bfs(i, r);
int xd = lmao.size();
for(auto it : lmao){
kek[it] = xd;
}
}
}
int maxi = 1e18;
for(int i=1;i<=n;i++){
if(kek[i] && maxi > kek[i]) maxi = kek[i];
}
for(int i=1;i<=n;i++){
if(maxi == kek[i]) ans[i - 1] = 1;
}
return ans;
}
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:109:16: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
109 | int maxi = 1e18;
| ^~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
14420 KB |
Output is correct |
2 |
Correct |
8 ms |
14420 KB |
Output is correct |
3 |
Correct |
8 ms |
14476 KB |
Output is correct |
4 |
Correct |
8 ms |
14420 KB |
Output is correct |
5 |
Correct |
9 ms |
14420 KB |
Output is correct |
6 |
Correct |
7 ms |
14420 KB |
Output is correct |
7 |
Correct |
7 ms |
14420 KB |
Output is correct |
8 |
Correct |
8 ms |
14420 KB |
Output is correct |
9 |
Correct |
8 ms |
14420 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
14420 KB |
Output is correct |
2 |
Correct |
8 ms |
14420 KB |
Output is correct |
3 |
Correct |
8 ms |
14476 KB |
Output is correct |
4 |
Correct |
8 ms |
14420 KB |
Output is correct |
5 |
Correct |
9 ms |
14420 KB |
Output is correct |
6 |
Correct |
7 ms |
14420 KB |
Output is correct |
7 |
Correct |
7 ms |
14420 KB |
Output is correct |
8 |
Correct |
8 ms |
14420 KB |
Output is correct |
9 |
Correct |
8 ms |
14420 KB |
Output is correct |
10 |
Correct |
8 ms |
14420 KB |
Output is correct |
11 |
Correct |
8 ms |
14500 KB |
Output is correct |
12 |
Correct |
8 ms |
14420 KB |
Output is correct |
13 |
Correct |
10 ms |
14544 KB |
Output is correct |
14 |
Correct |
9 ms |
14420 KB |
Output is correct |
15 |
Correct |
10 ms |
14420 KB |
Output is correct |
16 |
Correct |
10 ms |
14476 KB |
Output is correct |
17 |
Correct |
8 ms |
14420 KB |
Output is correct |
18 |
Correct |
8 ms |
14420 KB |
Output is correct |
19 |
Correct |
7 ms |
14456 KB |
Output is correct |
20 |
Correct |
7 ms |
14420 KB |
Output is correct |
21 |
Correct |
9 ms |
14420 KB |
Output is correct |
22 |
Correct |
10 ms |
14420 KB |
Output is correct |
23 |
Correct |
9 ms |
14420 KB |
Output is correct |
24 |
Correct |
8 ms |
14460 KB |
Output is correct |
25 |
Correct |
7 ms |
14420 KB |
Output is correct |
26 |
Correct |
7 ms |
14420 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
14420 KB |
Output is correct |
2 |
Correct |
8 ms |
14420 KB |
Output is correct |
3 |
Correct |
8 ms |
14476 KB |
Output is correct |
4 |
Correct |
8 ms |
14420 KB |
Output is correct |
5 |
Correct |
9 ms |
14420 KB |
Output is correct |
6 |
Correct |
7 ms |
14420 KB |
Output is correct |
7 |
Correct |
7 ms |
14420 KB |
Output is correct |
8 |
Correct |
8 ms |
14420 KB |
Output is correct |
9 |
Correct |
8 ms |
14420 KB |
Output is correct |
10 |
Correct |
8 ms |
14420 KB |
Output is correct |
11 |
Correct |
8 ms |
14500 KB |
Output is correct |
12 |
Correct |
8 ms |
14420 KB |
Output is correct |
13 |
Correct |
10 ms |
14544 KB |
Output is correct |
14 |
Correct |
9 ms |
14420 KB |
Output is correct |
15 |
Correct |
10 ms |
14420 KB |
Output is correct |
16 |
Correct |
10 ms |
14476 KB |
Output is correct |
17 |
Correct |
8 ms |
14420 KB |
Output is correct |
18 |
Correct |
8 ms |
14420 KB |
Output is correct |
19 |
Correct |
7 ms |
14456 KB |
Output is correct |
20 |
Correct |
7 ms |
14420 KB |
Output is correct |
21 |
Correct |
9 ms |
14420 KB |
Output is correct |
22 |
Correct |
10 ms |
14420 KB |
Output is correct |
23 |
Correct |
9 ms |
14420 KB |
Output is correct |
24 |
Correct |
8 ms |
14460 KB |
Output is correct |
25 |
Correct |
7 ms |
14420 KB |
Output is correct |
26 |
Correct |
7 ms |
14420 KB |
Output is correct |
27 |
Correct |
17 ms |
14628 KB |
Output is correct |
28 |
Correct |
22 ms |
14608 KB |
Output is correct |
29 |
Correct |
18 ms |
14716 KB |
Output is correct |
30 |
Correct |
10 ms |
14548 KB |
Output is correct |
31 |
Correct |
14 ms |
14540 KB |
Output is correct |
32 |
Correct |
8 ms |
14416 KB |
Output is correct |
33 |
Correct |
10 ms |
14592 KB |
Output is correct |
34 |
Correct |
10 ms |
14580 KB |
Output is correct |
35 |
Correct |
9 ms |
14548 KB |
Output is correct |
36 |
Correct |
12 ms |
14552 KB |
Output is correct |
37 |
Correct |
15 ms |
14676 KB |
Output is correct |
38 |
Correct |
13 ms |
14676 KB |
Output is correct |
39 |
Correct |
15 ms |
14628 KB |
Output is correct |
40 |
Correct |
16 ms |
14548 KB |
Output is correct |
41 |
Correct |
11 ms |
14620 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
14420 KB |
Output is correct |
2 |
Correct |
8 ms |
14420 KB |
Output is correct |
3 |
Correct |
8 ms |
14476 KB |
Output is correct |
4 |
Correct |
8 ms |
14420 KB |
Output is correct |
5 |
Correct |
9 ms |
14420 KB |
Output is correct |
6 |
Correct |
7 ms |
14420 KB |
Output is correct |
7 |
Correct |
7 ms |
14420 KB |
Output is correct |
8 |
Correct |
8 ms |
14420 KB |
Output is correct |
9 |
Correct |
8 ms |
14420 KB |
Output is correct |
10 |
Correct |
643 ms |
37716 KB |
Output is correct |
11 |
Correct |
830 ms |
51444 KB |
Output is correct |
12 |
Correct |
284 ms |
20488 KB |
Output is correct |
13 |
Correct |
1782 ms |
48256 KB |
Output is correct |
14 |
Correct |
761 ms |
42896 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
14420 KB |
Output is correct |
2 |
Correct |
8 ms |
14420 KB |
Output is correct |
3 |
Correct |
8 ms |
14476 KB |
Output is correct |
4 |
Correct |
8 ms |
14420 KB |
Output is correct |
5 |
Correct |
9 ms |
14420 KB |
Output is correct |
6 |
Correct |
7 ms |
14420 KB |
Output is correct |
7 |
Correct |
7 ms |
14420 KB |
Output is correct |
8 |
Correct |
8 ms |
14420 KB |
Output is correct |
9 |
Correct |
8 ms |
14420 KB |
Output is correct |
10 |
Correct |
8 ms |
14420 KB |
Output is correct |
11 |
Correct |
8 ms |
14500 KB |
Output is correct |
12 |
Correct |
8 ms |
14420 KB |
Output is correct |
13 |
Correct |
10 ms |
14544 KB |
Output is correct |
14 |
Correct |
9 ms |
14420 KB |
Output is correct |
15 |
Correct |
10 ms |
14420 KB |
Output is correct |
16 |
Correct |
10 ms |
14476 KB |
Output is correct |
17 |
Correct |
8 ms |
14420 KB |
Output is correct |
18 |
Correct |
8 ms |
14420 KB |
Output is correct |
19 |
Correct |
7 ms |
14456 KB |
Output is correct |
20 |
Correct |
7 ms |
14420 KB |
Output is correct |
21 |
Correct |
9 ms |
14420 KB |
Output is correct |
22 |
Correct |
10 ms |
14420 KB |
Output is correct |
23 |
Correct |
9 ms |
14420 KB |
Output is correct |
24 |
Correct |
8 ms |
14460 KB |
Output is correct |
25 |
Correct |
7 ms |
14420 KB |
Output is correct |
26 |
Correct |
7 ms |
14420 KB |
Output is correct |
27 |
Correct |
17 ms |
14628 KB |
Output is correct |
28 |
Correct |
22 ms |
14608 KB |
Output is correct |
29 |
Correct |
18 ms |
14716 KB |
Output is correct |
30 |
Correct |
10 ms |
14548 KB |
Output is correct |
31 |
Correct |
14 ms |
14540 KB |
Output is correct |
32 |
Correct |
8 ms |
14416 KB |
Output is correct |
33 |
Correct |
10 ms |
14592 KB |
Output is correct |
34 |
Correct |
10 ms |
14580 KB |
Output is correct |
35 |
Correct |
9 ms |
14548 KB |
Output is correct |
36 |
Correct |
12 ms |
14552 KB |
Output is correct |
37 |
Correct |
15 ms |
14676 KB |
Output is correct |
38 |
Correct |
13 ms |
14676 KB |
Output is correct |
39 |
Correct |
15 ms |
14628 KB |
Output is correct |
40 |
Correct |
16 ms |
14548 KB |
Output is correct |
41 |
Correct |
11 ms |
14620 KB |
Output is correct |
42 |
Correct |
643 ms |
37716 KB |
Output is correct |
43 |
Correct |
830 ms |
51444 KB |
Output is correct |
44 |
Correct |
284 ms |
20488 KB |
Output is correct |
45 |
Correct |
1782 ms |
48256 KB |
Output is correct |
46 |
Correct |
761 ms |
42896 KB |
Output is correct |
47 |
Correct |
10 ms |
14420 KB |
Output is correct |
48 |
Correct |
9 ms |
14452 KB |
Output is correct |
49 |
Correct |
10 ms |
14420 KB |
Output is correct |
50 |
Correct |
711 ms |
46032 KB |
Output is correct |
51 |
Correct |
937 ms |
46056 KB |
Output is correct |
52 |
Correct |
1035 ms |
39132 KB |
Output is correct |
53 |
Correct |
1051 ms |
39212 KB |
Output is correct |
54 |
Correct |
1155 ms |
39068 KB |
Output is correct |
55 |
Correct |
658 ms |
36556 KB |
Output is correct |
56 |
Correct |
1598 ms |
45716 KB |
Output is correct |
57 |
Correct |
1962 ms |
54596 KB |
Output is correct |
58 |
Correct |
900 ms |
61988 KB |
Output is correct |
59 |
Correct |
736 ms |
54152 KB |
Output is correct |
60 |
Correct |
676 ms |
49296 KB |
Output is correct |
61 |
Correct |
761 ms |
50628 KB |
Output is correct |
62 |
Correct |
1594 ms |
61772 KB |
Output is correct |
63 |
Correct |
833 ms |
48356 KB |
Output is correct |
64 |
Correct |
20 ms |
15060 KB |
Output is correct |
65 |
Correct |
25 ms |
15056 KB |
Output is correct |
66 |
Correct |
1608 ms |
61796 KB |
Output is correct |
67 |
Correct |
87 ms |
18008 KB |
Output is correct |
68 |
Correct |
134 ms |
20488 KB |
Output is correct |
69 |
Correct |
784 ms |
54112 KB |
Output is correct |
70 |
Correct |
226 ms |
26552 KB |
Output is correct |
71 |
Correct |
697 ms |
48824 KB |
Output is correct |
72 |
Correct |
855 ms |
54244 KB |
Output is correct |
73 |
Correct |
1595 ms |
61688 KB |
Output is correct |