# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
533093 |
2022-03-04T18:15:07 Z |
VodkaInTheJar |
Keys (IOI21_keys) |
C++17 |
|
824 ms |
147656 KB |
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#include "keys.h"
using namespace std;
const int maxn = 3e5 + 3;
vector <pair <int, int> > adj_all[maxn];
vector <int> adj[maxn], adj_rev[maxn];
vector <int> order;
bool used[maxn];
unordered_set <int> keys[maxn];
int par[maxn], sz[maxn];
inline int find_root(int ver) {
if (ver == par[ver])
return ver;
return par[ver] = find_root(par[ver]);
}
void merge(int a, int b) {
a = find_root(a), b = find_root(b);
if (a == b)
return;
if (sz[a] < sz[b])
swap(a, b);
for (auto i: keys[b])
keys[a].insert(i);
sz[a] += sz[b];
par[b] = a;
}
void dfs(int ver) {
used[ver] = true;
for (auto i: adj[ver])
if (!used[i])
dfs(i);
order.push_back(ver);
}
void dfs_rev(int ver, int root) {
merge(ver, root);
used[ver] = true;
for (auto i: adj_rev[ver])
if (!used[i])
dfs_rev(i, root);
}
vector <int> comp[maxn];
vector <int> find_reachable(vector <int> r, vector <int> u, vector <int> v, vector <int> c) {
int n = (int)r.size(), m = (int)u.size();
for (int i = 0; i < m; i++) {
adj_all[v[i]].push_back(make_pair(u[i], c[i]));
adj_all[u[i]].push_back(make_pair(v[i], c[i]));
}
for (int i = 0; i < n; i++) {
par[i] = i;
sz[i] = 1;
keys[i].insert(r[i]);
}
for (int iter = 1; iter <= 3; iter++) {
for (int i = 0; i < n; i++) {
adj[i].clear();
adj_rev[i].clear();
}
for (int i = 0; i < n; i++) {
int root = find_root(i);
for (auto j: adj_all[i])
if (keys[root].find(j.second) != keys[root].end()) {
adj[root].push_back(find_root(j.first));
adj_rev[find_root(j.first)].push_back(root);
}
}
memset(used, false, sizeof(used));
order.clear();
for (int i = 0; i < n; i++)
if (i == find_root(i) && !used[i])
dfs(i);
memset(used, false, sizeof(used));
reverse(order.begin(), order.end());
for (auto i: order)
if (!used[i])
dfs_rev(i, i);
}
int mins = INT_MAX;
vector <int> smallest;
for (int i = 0; i < n; i++)
comp[find_root(i)].push_back(i);
for (int i = 0; i < n; i++)
if (!comp[i].empty()) {
bool is = true;
for (auto j: comp[i])
for (auto k: adj_all[j])
if (keys[i].find(k.second) != keys[i].end())
if (find_root(k.first) != i) {
is = false;
break;
}
if (is) {
if ((int)comp[i].size() < mins) {
mins = comp[i].size();
smallest.clear();
}
if ((int)comp[i].size() == mins)
for (auto j: comp[i])
smallest.push_back(j);
}
}
vector <int> ans(n, false);
for (auto i: smallest)
ans[i] = true;
return ans;
}
/*
int n, m;
vector <int> r, u, v, c;
int main() {
cin >> n >> m;
r.resize(n), u.resize(m), v.resize(m), c.resize(m);
for (int i = 0; i < n; i++)
cin >> r[i];
for (int i = 0; i < m; i++)
cin >> u[i] >> v[i] >> c[i];
auto ans = find_reachable({0, 1, 1, 2, 2, 1, 2},{0, 0, 1, 1, 2, 3, 3, 4, 4, 5},{1, 2, 2, 3, 3, 4, 5, 5, 6, 6},{0, 0, 1, 0, 0, 1, 2, 0, 2, 1});
for (auto i: ans)
cout << i << " ";
cout << endl;
}
*/
/*
4 5
0 1 1 2
0 1 0
0 2 0
1 2 1
1 3 0
3 1 2
*/
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
28 ms |
45132 KB |
Output is correct |
2 |
Correct |
25 ms |
45180 KB |
Output is correct |
3 |
Correct |
30 ms |
45132 KB |
Output is correct |
4 |
Correct |
25 ms |
45272 KB |
Output is correct |
5 |
Correct |
30 ms |
45116 KB |
Output is correct |
6 |
Correct |
23 ms |
45132 KB |
Output is correct |
7 |
Correct |
23 ms |
45212 KB |
Output is correct |
8 |
Correct |
24 ms |
45260 KB |
Output is correct |
9 |
Correct |
27 ms |
45160 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
28 ms |
45132 KB |
Output is correct |
2 |
Correct |
25 ms |
45180 KB |
Output is correct |
3 |
Correct |
30 ms |
45132 KB |
Output is correct |
4 |
Correct |
25 ms |
45272 KB |
Output is correct |
5 |
Correct |
30 ms |
45116 KB |
Output is correct |
6 |
Correct |
23 ms |
45132 KB |
Output is correct |
7 |
Correct |
23 ms |
45212 KB |
Output is correct |
8 |
Correct |
24 ms |
45260 KB |
Output is correct |
9 |
Correct |
27 ms |
45160 KB |
Output is correct |
10 |
Correct |
23 ms |
45172 KB |
Output is correct |
11 |
Correct |
24 ms |
45180 KB |
Output is correct |
12 |
Correct |
25 ms |
45176 KB |
Output is correct |
13 |
Correct |
31 ms |
45088 KB |
Output is correct |
14 |
Correct |
25 ms |
45220 KB |
Output is correct |
15 |
Correct |
22 ms |
45140 KB |
Output is correct |
16 |
Correct |
23 ms |
45132 KB |
Output is correct |
17 |
Correct |
24 ms |
45216 KB |
Output is correct |
18 |
Correct |
24 ms |
45164 KB |
Output is correct |
19 |
Correct |
26 ms |
45120 KB |
Output is correct |
20 |
Correct |
27 ms |
45132 KB |
Output is correct |
21 |
Correct |
23 ms |
45260 KB |
Output is correct |
22 |
Correct |
25 ms |
45172 KB |
Output is correct |
23 |
Correct |
23 ms |
45240 KB |
Output is correct |
24 |
Correct |
24 ms |
45284 KB |
Output is correct |
25 |
Correct |
23 ms |
45260 KB |
Output is correct |
26 |
Correct |
28 ms |
45268 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
28 ms |
45132 KB |
Output is correct |
2 |
Correct |
25 ms |
45180 KB |
Output is correct |
3 |
Correct |
30 ms |
45132 KB |
Output is correct |
4 |
Correct |
25 ms |
45272 KB |
Output is correct |
5 |
Correct |
30 ms |
45116 KB |
Output is correct |
6 |
Correct |
23 ms |
45132 KB |
Output is correct |
7 |
Correct |
23 ms |
45212 KB |
Output is correct |
8 |
Correct |
24 ms |
45260 KB |
Output is correct |
9 |
Correct |
27 ms |
45160 KB |
Output is correct |
10 |
Correct |
23 ms |
45172 KB |
Output is correct |
11 |
Correct |
24 ms |
45180 KB |
Output is correct |
12 |
Correct |
25 ms |
45176 KB |
Output is correct |
13 |
Correct |
31 ms |
45088 KB |
Output is correct |
14 |
Correct |
25 ms |
45220 KB |
Output is correct |
15 |
Correct |
22 ms |
45140 KB |
Output is correct |
16 |
Correct |
23 ms |
45132 KB |
Output is correct |
17 |
Correct |
24 ms |
45216 KB |
Output is correct |
18 |
Correct |
24 ms |
45164 KB |
Output is correct |
19 |
Correct |
26 ms |
45120 KB |
Output is correct |
20 |
Correct |
27 ms |
45132 KB |
Output is correct |
21 |
Correct |
23 ms |
45260 KB |
Output is correct |
22 |
Correct |
25 ms |
45172 KB |
Output is correct |
23 |
Correct |
23 ms |
45240 KB |
Output is correct |
24 |
Correct |
24 ms |
45284 KB |
Output is correct |
25 |
Correct |
23 ms |
45260 KB |
Output is correct |
26 |
Correct |
28 ms |
45268 KB |
Output is correct |
27 |
Correct |
30 ms |
45768 KB |
Output is correct |
28 |
Correct |
32 ms |
45828 KB |
Output is correct |
29 |
Correct |
27 ms |
45732 KB |
Output is correct |
30 |
Correct |
32 ms |
45456 KB |
Output is correct |
31 |
Correct |
24 ms |
45460 KB |
Output is correct |
32 |
Correct |
25 ms |
45220 KB |
Output is correct |
33 |
Correct |
25 ms |
45516 KB |
Output is correct |
34 |
Correct |
25 ms |
45540 KB |
Output is correct |
35 |
Correct |
26 ms |
45516 KB |
Output is correct |
36 |
Correct |
27 ms |
45748 KB |
Output is correct |
37 |
Correct |
26 ms |
45776 KB |
Output is correct |
38 |
Correct |
27 ms |
45928 KB |
Output is correct |
39 |
Correct |
26 ms |
45892 KB |
Output is correct |
40 |
Correct |
25 ms |
45492 KB |
Output is correct |
41 |
Correct |
25 ms |
45632 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
28 ms |
45132 KB |
Output is correct |
2 |
Correct |
25 ms |
45180 KB |
Output is correct |
3 |
Correct |
30 ms |
45132 KB |
Output is correct |
4 |
Correct |
25 ms |
45272 KB |
Output is correct |
5 |
Correct |
30 ms |
45116 KB |
Output is correct |
6 |
Correct |
23 ms |
45132 KB |
Output is correct |
7 |
Correct |
23 ms |
45212 KB |
Output is correct |
8 |
Correct |
24 ms |
45260 KB |
Output is correct |
9 |
Correct |
27 ms |
45160 KB |
Output is correct |
10 |
Correct |
350 ms |
87340 KB |
Output is correct |
11 |
Correct |
504 ms |
140728 KB |
Output is correct |
12 |
Correct |
145 ms |
63296 KB |
Output is correct |
13 |
Correct |
824 ms |
137580 KB |
Output is correct |
14 |
Correct |
345 ms |
147656 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
28 ms |
45132 KB |
Output is correct |
2 |
Correct |
25 ms |
45180 KB |
Output is correct |
3 |
Correct |
30 ms |
45132 KB |
Output is correct |
4 |
Correct |
25 ms |
45272 KB |
Output is correct |
5 |
Correct |
30 ms |
45116 KB |
Output is correct |
6 |
Correct |
23 ms |
45132 KB |
Output is correct |
7 |
Correct |
23 ms |
45212 KB |
Output is correct |
8 |
Correct |
24 ms |
45260 KB |
Output is correct |
9 |
Correct |
27 ms |
45160 KB |
Output is correct |
10 |
Correct |
23 ms |
45172 KB |
Output is correct |
11 |
Correct |
24 ms |
45180 KB |
Output is correct |
12 |
Correct |
25 ms |
45176 KB |
Output is correct |
13 |
Correct |
31 ms |
45088 KB |
Output is correct |
14 |
Correct |
25 ms |
45220 KB |
Output is correct |
15 |
Correct |
22 ms |
45140 KB |
Output is correct |
16 |
Correct |
23 ms |
45132 KB |
Output is correct |
17 |
Correct |
24 ms |
45216 KB |
Output is correct |
18 |
Correct |
24 ms |
45164 KB |
Output is correct |
19 |
Correct |
26 ms |
45120 KB |
Output is correct |
20 |
Correct |
27 ms |
45132 KB |
Output is correct |
21 |
Correct |
23 ms |
45260 KB |
Output is correct |
22 |
Correct |
25 ms |
45172 KB |
Output is correct |
23 |
Correct |
23 ms |
45240 KB |
Output is correct |
24 |
Correct |
24 ms |
45284 KB |
Output is correct |
25 |
Correct |
23 ms |
45260 KB |
Output is correct |
26 |
Correct |
28 ms |
45268 KB |
Output is correct |
27 |
Correct |
30 ms |
45768 KB |
Output is correct |
28 |
Correct |
32 ms |
45828 KB |
Output is correct |
29 |
Correct |
27 ms |
45732 KB |
Output is correct |
30 |
Correct |
32 ms |
45456 KB |
Output is correct |
31 |
Correct |
24 ms |
45460 KB |
Output is correct |
32 |
Correct |
25 ms |
45220 KB |
Output is correct |
33 |
Correct |
25 ms |
45516 KB |
Output is correct |
34 |
Correct |
25 ms |
45540 KB |
Output is correct |
35 |
Correct |
26 ms |
45516 KB |
Output is correct |
36 |
Correct |
27 ms |
45748 KB |
Output is correct |
37 |
Correct |
26 ms |
45776 KB |
Output is correct |
38 |
Correct |
27 ms |
45928 KB |
Output is correct |
39 |
Correct |
26 ms |
45892 KB |
Output is correct |
40 |
Correct |
25 ms |
45492 KB |
Output is correct |
41 |
Correct |
25 ms |
45632 KB |
Output is correct |
42 |
Correct |
350 ms |
87340 KB |
Output is correct |
43 |
Correct |
504 ms |
140728 KB |
Output is correct |
44 |
Correct |
145 ms |
63296 KB |
Output is correct |
45 |
Correct |
824 ms |
137580 KB |
Output is correct |
46 |
Correct |
345 ms |
147656 KB |
Output is correct |
47 |
Correct |
24 ms |
45132 KB |
Output is correct |
48 |
Correct |
22 ms |
45124 KB |
Output is correct |
49 |
Correct |
22 ms |
45132 KB |
Output is correct |
50 |
Correct |
317 ms |
145852 KB |
Output is correct |
51 |
Correct |
357 ms |
144656 KB |
Output is correct |
52 |
Correct |
349 ms |
105632 KB |
Output is correct |
53 |
Correct |
350 ms |
105752 KB |
Output is correct |
54 |
Correct |
340 ms |
105572 KB |
Output is correct |
55 |
Correct |
311 ms |
87140 KB |
Output is correct |
56 |
Correct |
701 ms |
141172 KB |
Output is correct |
57 |
Correct |
497 ms |
136844 KB |
Output is correct |
58 |
Correct |
426 ms |
134720 KB |
Output is correct |
59 |
Correct |
609 ms |
120368 KB |
Output is correct |
60 |
Correct |
636 ms |
127308 KB |
Output is correct |
61 |
Correct |
618 ms |
127272 KB |
Output is correct |
62 |
Correct |
607 ms |
103588 KB |
Output is correct |
63 |
Correct |
307 ms |
115700 KB |
Output is correct |
64 |
Correct |
33 ms |
47004 KB |
Output is correct |
65 |
Correct |
33 ms |
47044 KB |
Output is correct |
66 |
Correct |
579 ms |
103536 KB |
Output is correct |
67 |
Correct |
55 ms |
55936 KB |
Output is correct |
68 |
Correct |
74 ms |
62752 KB |
Output is correct |
69 |
Correct |
611 ms |
119376 KB |
Output is correct |
70 |
Correct |
145 ms |
79936 KB |
Output is correct |
71 |
Correct |
332 ms |
147000 KB |
Output is correct |
72 |
Correct |
653 ms |
119924 KB |
Output is correct |
73 |
Correct |
563 ms |
103388 KB |
Output is correct |