# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
598747 |
2022-07-18T21:44:46 Z |
sofapuden |
Keys (IOI21_keys) |
C++17 |
|
2076 ms |
271376 KB |
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")
#include<bits/stdc++.h>
using namespace std;
struct DSU {
int n;
vector<int> p;
DSU(int _n) : n(_n) {
p.resize(n);
iota(p.begin(),p.end(),0);
}
int get(int x){
return x ^ p[x] ? p[x] = get(p[x]) : x;
}
void unite(int a, int b){
a = get(a), b = get(b);
p[a] = b;
}
};
struct info {
unordered_map<int,vector<int>> blo;
unordered_set<int> unl;
};
vector<info> inf;
vector<int> vis;
bool step(vector<int> &r, vector<vector<pair<int,int>>> &gr, DSU &d){
bool ok = 0;
int n = r.size();
vis.clear();
vis.resize(n,0);
queue<pair<int,int>> Q;
for(int i = 0; i < n; ++i){
if(i == d.get(i)){
Q.push({i,i});
while(Q.size()){
auto x = Q.front();
Q.pop();
if(x.second != d.get(x.second))continue;
if(d.get(x.first) != x.second){
ok = 1;
d.unite(x.second,x.first);
continue;
}
if(vis[x.first])continue;
vis[x.first] = 1;
for(auto y : gr[x.first]){
if(inf[x.second].unl.count(y.second))Q.push({y.first,x.second});
else inf[x.second].blo[y.second].push_back(y.first);
}
inf[x.second].unl.insert(r[x.first]);
for(auto y : inf[x.second].blo[r[x.first]])Q.push({y,x.second});
inf[x.second].blo[r[x.first]].clear();
}
}
}
return ok;
}
vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c){
int n = r.size();
int m = u.size();
inf.resize(n);
DSU d(n);
vector<vector<pair<int,int>>> gr(n);
for(int i = 0; i < m; ++i){
gr[u[i]].push_back({v[i],c[i]});
gr[v[i]].push_back({u[i],c[i]});
}
while(step(r,gr,d));
vector<int> nsiz(n,0);
int mn = n+1;
for(int i = 0; i < n; ++i){
if(vis[i])nsiz[d.get(i)]++;
}
for(int i = 0; i < n; ++i){
mn = min(mn,nsiz[d.get(i)]);
}
for(int i = 0; i < n; ++i){
if(mn != nsiz[d.get(i)])vis[i] = 0;
}
return vis;
}
# |
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 |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
0 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
340 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 |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
0 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
340 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 |
212 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 |
1 ms |
340 KB |
Output is correct |
19 |
Correct |
1 ms |
212 KB |
Output is correct |
20 |
Correct |
0 ms |
212 KB |
Output is correct |
21 |
Correct |
1 ms |
340 KB |
Output is correct |
22 |
Correct |
1 ms |
340 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 |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
0 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
340 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 |
212 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 |
1 ms |
340 KB |
Output is correct |
19 |
Correct |
1 ms |
212 KB |
Output is correct |
20 |
Correct |
0 ms |
212 KB |
Output is correct |
21 |
Correct |
1 ms |
340 KB |
Output is correct |
22 |
Correct |
1 ms |
340 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 |
3 ms |
1492 KB |
Output is correct |
28 |
Correct |
3 ms |
1492 KB |
Output is correct |
29 |
Correct |
3 ms |
1492 KB |
Output is correct |
30 |
Correct |
2 ms |
852 KB |
Output is correct |
31 |
Correct |
2 ms |
852 KB |
Output is correct |
32 |
Correct |
1 ms |
468 KB |
Output is correct |
33 |
Correct |
2 ms |
852 KB |
Output is correct |
34 |
Correct |
2 ms |
852 KB |
Output is correct |
35 |
Correct |
2 ms |
724 KB |
Output is correct |
36 |
Correct |
3 ms |
1236 KB |
Output is correct |
37 |
Correct |
3 ms |
1492 KB |
Output is correct |
38 |
Correct |
3 ms |
1492 KB |
Output is correct |
39 |
Correct |
4 ms |
1748 KB |
Output is correct |
40 |
Correct |
3 ms |
980 KB |
Output is correct |
41 |
Correct |
3 ms |
1108 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 |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
0 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
364 ms |
96492 KB |
Output is correct |
11 |
Correct |
545 ms |
168328 KB |
Output is correct |
12 |
Correct |
113 ms |
36440 KB |
Output is correct |
13 |
Correct |
653 ms |
181436 KB |
Output is correct |
14 |
Correct |
403 ms |
165780 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 |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
0 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
340 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 |
212 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 |
1 ms |
340 KB |
Output is correct |
19 |
Correct |
1 ms |
212 KB |
Output is correct |
20 |
Correct |
0 ms |
212 KB |
Output is correct |
21 |
Correct |
1 ms |
340 KB |
Output is correct |
22 |
Correct |
1 ms |
340 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 |
3 ms |
1492 KB |
Output is correct |
28 |
Correct |
3 ms |
1492 KB |
Output is correct |
29 |
Correct |
3 ms |
1492 KB |
Output is correct |
30 |
Correct |
2 ms |
852 KB |
Output is correct |
31 |
Correct |
2 ms |
852 KB |
Output is correct |
32 |
Correct |
1 ms |
468 KB |
Output is correct |
33 |
Correct |
2 ms |
852 KB |
Output is correct |
34 |
Correct |
2 ms |
852 KB |
Output is correct |
35 |
Correct |
2 ms |
724 KB |
Output is correct |
36 |
Correct |
3 ms |
1236 KB |
Output is correct |
37 |
Correct |
3 ms |
1492 KB |
Output is correct |
38 |
Correct |
3 ms |
1492 KB |
Output is correct |
39 |
Correct |
4 ms |
1748 KB |
Output is correct |
40 |
Correct |
3 ms |
980 KB |
Output is correct |
41 |
Correct |
3 ms |
1108 KB |
Output is correct |
42 |
Correct |
364 ms |
96492 KB |
Output is correct |
43 |
Correct |
545 ms |
168328 KB |
Output is correct |
44 |
Correct |
113 ms |
36440 KB |
Output is correct |
45 |
Correct |
653 ms |
181436 KB |
Output is correct |
46 |
Correct |
403 ms |
165780 KB |
Output is correct |
47 |
Correct |
0 ms |
212 KB |
Output is correct |
48 |
Correct |
1 ms |
212 KB |
Output is correct |
49 |
Correct |
0 ms |
212 KB |
Output is correct |
50 |
Correct |
311 ms |
164084 KB |
Output is correct |
51 |
Correct |
378 ms |
166128 KB |
Output is correct |
52 |
Correct |
385 ms |
130304 KB |
Output is correct |
53 |
Correct |
392 ms |
130328 KB |
Output is correct |
54 |
Correct |
408 ms |
130320 KB |
Output is correct |
55 |
Correct |
449 ms |
108136 KB |
Output is correct |
56 |
Correct |
583 ms |
183124 KB |
Output is correct |
57 |
Correct |
531 ms |
179980 KB |
Output is correct |
58 |
Correct |
560 ms |
190812 KB |
Output is correct |
59 |
Correct |
780 ms |
168696 KB |
Output is correct |
60 |
Correct |
617 ms |
164244 KB |
Output is correct |
61 |
Correct |
664 ms |
167192 KB |
Output is correct |
62 |
Correct |
2076 ms |
265080 KB |
Output is correct |
63 |
Correct |
441 ms |
153280 KB |
Output is correct |
64 |
Correct |
7 ms |
3128 KB |
Output is correct |
65 |
Correct |
7 ms |
3148 KB |
Output is correct |
66 |
Correct |
2070 ms |
271376 KB |
Output is correct |
67 |
Correct |
31 ms |
17380 KB |
Output is correct |
68 |
Correct |
51 ms |
28848 KB |
Output is correct |
69 |
Correct |
797 ms |
175640 KB |
Output is correct |
70 |
Correct |
102 ms |
57420 KB |
Output is correct |
71 |
Correct |
402 ms |
171984 KB |
Output is correct |
72 |
Correct |
784 ms |
175636 KB |
Output is correct |
73 |
Correct |
1967 ms |
271136 KB |
Output is correct |