# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
565882 |
2022-05-21T13:34:28 Z |
Kanon |
Keys (IOI21_keys) |
C++17 |
|
1251 ms |
127516 KB |
#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include "keys.h"
using namespace __gnu_pbds;
using namespace std;
template <typename T>
using ordered_set = tree <T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;
const int N = 3e5 + 10;
int n;
int par[N], sz[N];
map <int, vector <int> > g[N];
set <int> key[N];
vector <int> to[N];
int Find(int u) {
return (u == par[u] ? u : par[u] = Find(par[u]));
}
void Union(int u, int v) {
if ((u = Find(u)) == (v = Find(v))) return;
if (sz[u] < sz[v]) swap(u, v);
par[v] = u;
sz[u] += sz[v];
if (key[u].size() + to[u].size() < key[v].size() + to[v].size()) swap(key[u], key[v]), swap(to[u], to[v]);
for (auto w: to[v]) to[u].push_back(w);
to[v].clear();
for (auto c: key[v]) {
if (g[u].find(c) != g[u].end()) {
for (auto w: g[u][c]) to[u].push_back(w);
g[u].erase(c);
}
}
for (auto [c, _]: g[v]) {
if (key[u].find(c) != key[u].end()) {
for (auto w: g[v][c]) to[u].push_back(w);
} else for (auto w: g[v][c]) g[u][c].push_back(w);
}
g[v].clear();
key[u].insert(key[v].begin(), key[v].end());
key[v].clear();
}
int bad[N];
int state[N];
int last[N];
void dfs(int u) {
state[u] = 0;
while (1) {
u = Find(u);
if (to[u].empty()) break;
int v = to[u].back();
to[u].pop_back();
v = Find(v);
if (u == v) continue;
if (state[v] == -1) {
last[v] = u;
dfs(v);
if (Find(u) != Find(v)) bad[u] = 1;
} else if (state[v] == 0) {
int w = u;
while (1) {
if (Find(w) == Find(v)) break;
Union(w, v);
w = last[w];
}
} else bad[u] = 1;
}
state[u] = 1;
}
std::vector<int> find_reachable(std::vector<int> r, std::vector<int> u, std::vector<int> v, std::vector<int> c) {
int n = r.size();
int m = c.size();
auto add_edge = [&](int u, int v, int c) {
if (r[u] == c) to[u].push_back(v);
else g[u][c].push_back(v);
};
for (int i = 0; i < m; ++i) {
add_edge(u[i], v[i], c[i]);
add_edge(v[i], u[i], c[i]);
}
for (int i = 0; i < n; ++i) par[i] = i, sz[i] = 1, key[i].insert(r[i]);
memset(state, -1, sizeof(state));
for (int i = 0; i < n; ++i) if (state[i] == -1) dfs(i);
for (int i = 0; i < n; ++i) if (bad[i]) bad[Find(i)] = 1;
vector <int> flag(n, 0);
int ans = 1e9;
for (int i = 0; i < n; ++i)
if (i == Find(i) && !bad[i]) ans = min(ans, sz[i]);
for (int i = 0; i < n; ++i)
if (!bad[Find(i)] && sz[Find(i)] == ans) flag[i] = 1;
return flag;
}
//int main() {
// freopen("IOI21_keys.inp", "r", stdin);
//// freopen("IOI21_keys.out", "w", stdout);
// int n, m;
// assert(2 == scanf("%d%d", &n, &m));
// std::vector<int> r(n), u(m), v(m), c(m);
// for(int i=0; i<n; i++) {
// assert(1 == scanf("%d", &r[i]));
// }
// for(int i=0; i<m; i++) {
// assert(3 == scanf("%d %d %d", &u[i], &v[i], &c[i]));
// }
// fclose(stdin);
//
// std::vector<int> ans = find_reachable(r, u, v, c);
//
// for (int i = 0; i < (int) ans.size(); ++i) {
// if(i) putchar(' ');
// putchar(ans[i]+'0');
// }
// printf("\n");
// return 0;
//}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
17 ms |
36692 KB |
Output is correct |
2 |
Correct |
20 ms |
36692 KB |
Output is correct |
3 |
Correct |
18 ms |
36728 KB |
Output is correct |
4 |
Correct |
18 ms |
36692 KB |
Output is correct |
5 |
Correct |
18 ms |
36692 KB |
Output is correct |
6 |
Correct |
18 ms |
36612 KB |
Output is correct |
7 |
Correct |
17 ms |
36724 KB |
Output is correct |
8 |
Correct |
18 ms |
36668 KB |
Output is correct |
9 |
Correct |
18 ms |
36800 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
17 ms |
36692 KB |
Output is correct |
2 |
Correct |
20 ms |
36692 KB |
Output is correct |
3 |
Correct |
18 ms |
36728 KB |
Output is correct |
4 |
Correct |
18 ms |
36692 KB |
Output is correct |
5 |
Correct |
18 ms |
36692 KB |
Output is correct |
6 |
Correct |
18 ms |
36612 KB |
Output is correct |
7 |
Correct |
17 ms |
36724 KB |
Output is correct |
8 |
Correct |
18 ms |
36668 KB |
Output is correct |
9 |
Correct |
18 ms |
36800 KB |
Output is correct |
10 |
Correct |
17 ms |
36712 KB |
Output is correct |
11 |
Correct |
16 ms |
36724 KB |
Output is correct |
12 |
Correct |
17 ms |
36692 KB |
Output is correct |
13 |
Correct |
17 ms |
36696 KB |
Output is correct |
14 |
Correct |
18 ms |
36676 KB |
Output is correct |
15 |
Correct |
24 ms |
36720 KB |
Output is correct |
16 |
Correct |
18 ms |
36672 KB |
Output is correct |
17 |
Correct |
18 ms |
36692 KB |
Output is correct |
18 |
Correct |
18 ms |
36692 KB |
Output is correct |
19 |
Correct |
19 ms |
36624 KB |
Output is correct |
20 |
Correct |
18 ms |
36692 KB |
Output is correct |
21 |
Correct |
18 ms |
36656 KB |
Output is correct |
22 |
Correct |
18 ms |
36672 KB |
Output is correct |
23 |
Correct |
18 ms |
36692 KB |
Output is correct |
24 |
Correct |
17 ms |
36768 KB |
Output is correct |
25 |
Correct |
20 ms |
36692 KB |
Output is correct |
26 |
Correct |
17 ms |
36692 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
17 ms |
36692 KB |
Output is correct |
2 |
Correct |
20 ms |
36692 KB |
Output is correct |
3 |
Correct |
18 ms |
36728 KB |
Output is correct |
4 |
Correct |
18 ms |
36692 KB |
Output is correct |
5 |
Correct |
18 ms |
36692 KB |
Output is correct |
6 |
Correct |
18 ms |
36612 KB |
Output is correct |
7 |
Correct |
17 ms |
36724 KB |
Output is correct |
8 |
Correct |
18 ms |
36668 KB |
Output is correct |
9 |
Correct |
18 ms |
36800 KB |
Output is correct |
10 |
Correct |
17 ms |
36712 KB |
Output is correct |
11 |
Correct |
16 ms |
36724 KB |
Output is correct |
12 |
Correct |
17 ms |
36692 KB |
Output is correct |
13 |
Correct |
17 ms |
36696 KB |
Output is correct |
14 |
Correct |
18 ms |
36676 KB |
Output is correct |
15 |
Correct |
24 ms |
36720 KB |
Output is correct |
16 |
Correct |
18 ms |
36672 KB |
Output is correct |
17 |
Correct |
18 ms |
36692 KB |
Output is correct |
18 |
Correct |
18 ms |
36692 KB |
Output is correct |
19 |
Correct |
19 ms |
36624 KB |
Output is correct |
20 |
Correct |
18 ms |
36692 KB |
Output is correct |
21 |
Correct |
18 ms |
36656 KB |
Output is correct |
22 |
Correct |
18 ms |
36672 KB |
Output is correct |
23 |
Correct |
18 ms |
36692 KB |
Output is correct |
24 |
Correct |
17 ms |
36768 KB |
Output is correct |
25 |
Correct |
20 ms |
36692 KB |
Output is correct |
26 |
Correct |
17 ms |
36692 KB |
Output is correct |
27 |
Correct |
19 ms |
37228 KB |
Output is correct |
28 |
Correct |
20 ms |
37204 KB |
Output is correct |
29 |
Correct |
23 ms |
37184 KB |
Output is correct |
30 |
Correct |
22 ms |
36936 KB |
Output is correct |
31 |
Correct |
19 ms |
36820 KB |
Output is correct |
32 |
Correct |
17 ms |
36704 KB |
Output is correct |
33 |
Correct |
18 ms |
36884 KB |
Output is correct |
34 |
Correct |
18 ms |
36948 KB |
Output is correct |
35 |
Correct |
18 ms |
36940 KB |
Output is correct |
36 |
Correct |
20 ms |
37320 KB |
Output is correct |
37 |
Correct |
20 ms |
37296 KB |
Output is correct |
38 |
Correct |
20 ms |
37376 KB |
Output is correct |
39 |
Correct |
23 ms |
37332 KB |
Output is correct |
40 |
Correct |
21 ms |
36948 KB |
Output is correct |
41 |
Correct |
24 ms |
37204 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
17 ms |
36692 KB |
Output is correct |
2 |
Correct |
20 ms |
36692 KB |
Output is correct |
3 |
Correct |
18 ms |
36728 KB |
Output is correct |
4 |
Correct |
18 ms |
36692 KB |
Output is correct |
5 |
Correct |
18 ms |
36692 KB |
Output is correct |
6 |
Correct |
18 ms |
36612 KB |
Output is correct |
7 |
Correct |
17 ms |
36724 KB |
Output is correct |
8 |
Correct |
18 ms |
36668 KB |
Output is correct |
9 |
Correct |
18 ms |
36800 KB |
Output is correct |
10 |
Correct |
558 ms |
104548 KB |
Output is correct |
11 |
Correct |
396 ms |
96028 KB |
Output is correct |
12 |
Correct |
90 ms |
50732 KB |
Output is correct |
13 |
Correct |
460 ms |
107612 KB |
Output is correct |
14 |
Correct |
197 ms |
109008 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
17 ms |
36692 KB |
Output is correct |
2 |
Correct |
20 ms |
36692 KB |
Output is correct |
3 |
Correct |
18 ms |
36728 KB |
Output is correct |
4 |
Correct |
18 ms |
36692 KB |
Output is correct |
5 |
Correct |
18 ms |
36692 KB |
Output is correct |
6 |
Correct |
18 ms |
36612 KB |
Output is correct |
7 |
Correct |
17 ms |
36724 KB |
Output is correct |
8 |
Correct |
18 ms |
36668 KB |
Output is correct |
9 |
Correct |
18 ms |
36800 KB |
Output is correct |
10 |
Correct |
17 ms |
36712 KB |
Output is correct |
11 |
Correct |
16 ms |
36724 KB |
Output is correct |
12 |
Correct |
17 ms |
36692 KB |
Output is correct |
13 |
Correct |
17 ms |
36696 KB |
Output is correct |
14 |
Correct |
18 ms |
36676 KB |
Output is correct |
15 |
Correct |
24 ms |
36720 KB |
Output is correct |
16 |
Correct |
18 ms |
36672 KB |
Output is correct |
17 |
Correct |
18 ms |
36692 KB |
Output is correct |
18 |
Correct |
18 ms |
36692 KB |
Output is correct |
19 |
Correct |
19 ms |
36624 KB |
Output is correct |
20 |
Correct |
18 ms |
36692 KB |
Output is correct |
21 |
Correct |
18 ms |
36656 KB |
Output is correct |
22 |
Correct |
18 ms |
36672 KB |
Output is correct |
23 |
Correct |
18 ms |
36692 KB |
Output is correct |
24 |
Correct |
17 ms |
36768 KB |
Output is correct |
25 |
Correct |
20 ms |
36692 KB |
Output is correct |
26 |
Correct |
17 ms |
36692 KB |
Output is correct |
27 |
Correct |
19 ms |
37228 KB |
Output is correct |
28 |
Correct |
20 ms |
37204 KB |
Output is correct |
29 |
Correct |
23 ms |
37184 KB |
Output is correct |
30 |
Correct |
22 ms |
36936 KB |
Output is correct |
31 |
Correct |
19 ms |
36820 KB |
Output is correct |
32 |
Correct |
17 ms |
36704 KB |
Output is correct |
33 |
Correct |
18 ms |
36884 KB |
Output is correct |
34 |
Correct |
18 ms |
36948 KB |
Output is correct |
35 |
Correct |
18 ms |
36940 KB |
Output is correct |
36 |
Correct |
20 ms |
37320 KB |
Output is correct |
37 |
Correct |
20 ms |
37296 KB |
Output is correct |
38 |
Correct |
20 ms |
37376 KB |
Output is correct |
39 |
Correct |
23 ms |
37332 KB |
Output is correct |
40 |
Correct |
21 ms |
36948 KB |
Output is correct |
41 |
Correct |
24 ms |
37204 KB |
Output is correct |
42 |
Correct |
558 ms |
104548 KB |
Output is correct |
43 |
Correct |
396 ms |
96028 KB |
Output is correct |
44 |
Correct |
90 ms |
50732 KB |
Output is correct |
45 |
Correct |
460 ms |
107612 KB |
Output is correct |
46 |
Correct |
197 ms |
109008 KB |
Output is correct |
47 |
Correct |
18 ms |
36668 KB |
Output is correct |
48 |
Correct |
23 ms |
36728 KB |
Output is correct |
49 |
Correct |
19 ms |
36688 KB |
Output is correct |
50 |
Correct |
227 ms |
106228 KB |
Output is correct |
51 |
Correct |
209 ms |
109204 KB |
Output is correct |
52 |
Correct |
267 ms |
97412 KB |
Output is correct |
53 |
Correct |
260 ms |
97284 KB |
Output is correct |
54 |
Correct |
277 ms |
97400 KB |
Output is correct |
55 |
Correct |
700 ms |
117512 KB |
Output is correct |
56 |
Correct |
352 ms |
115828 KB |
Output is correct |
57 |
Correct |
267 ms |
105856 KB |
Output is correct |
58 |
Correct |
524 ms |
114964 KB |
Output is correct |
59 |
Correct |
1176 ms |
126312 KB |
Output is correct |
60 |
Correct |
782 ms |
127152 KB |
Output is correct |
61 |
Correct |
814 ms |
127516 KB |
Output is correct |
62 |
Correct |
598 ms |
106184 KB |
Output is correct |
63 |
Correct |
274 ms |
104868 KB |
Output is correct |
64 |
Correct |
22 ms |
37872 KB |
Output is correct |
65 |
Correct |
21 ms |
37872 KB |
Output is correct |
66 |
Correct |
623 ms |
106072 KB |
Output is correct |
67 |
Correct |
37 ms |
44048 KB |
Output is correct |
68 |
Correct |
50 ms |
49016 KB |
Output is correct |
69 |
Correct |
1184 ms |
125952 KB |
Output is correct |
70 |
Correct |
93 ms |
60996 KB |
Output is correct |
71 |
Correct |
203 ms |
109704 KB |
Output is correct |
72 |
Correct |
1251 ms |
125992 KB |
Output is correct |
73 |
Correct |
606 ms |
106140 KB |
Output is correct |