# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
434983 |
2021-06-22T17:21:59 Z |
model_code |
Keys (IOI21_keys) |
C++17 |
|
3000 ms |
80168 KB |
/**
* Task: keys
* Author: Kian Mirjalali
* Solution: m*log(n)
*/
#include "keys.h"
#include <iostream>
#include <memory>
#include <algorithm>
#include <map>
#include <set>
using namespace std;
#define tpc(C) template<class C>
#define allOf(c) ((c).begin()), ((c).end())
#define fori(i, a, b) for (int i = (a); i < int(b); i++)
#define forn(i, n) fori(i, 0, (n))
#define dbg(x) #x << "=" << x
#define show(x) cerr << dbg(x) << endl
typedef vector<int> VI;
typedef vector<bool> VB;
typedef pair<int, int> PII;
tpc(C) inline int sz(const C& c) { return c.size(); }
/////////////////////////
struct DisjointSet {
VI par;
inline DisjointSet(int n): par(n) {
forn(i, n)
par[i] = i;
}
inline int findRoot(int x) {
int i;
for (i = x; par[i] != i; )
i = par[i];
int root = i;
for (i = x; par[i] != i; ) {
int j = par[i];
par[i] = root;
i = j;
}
return root;
}
/// returns true if the merge happened now or false if they are already merged
inline bool merge(int x, int y) {
int x_root = findRoot(x);
int y_root = findRoot(y);
if (x_root == y_root)
return false;
par[x_root] = y_root;
return true;
}
};
/////////////////////////
class IndexDSBase {
protected:
int index_limit_;
VI index_list;
VI index_position;
int list_head;
inline void check_index_validity(int index) const {
if (index < 0 || index_limit_ <= index) {
cerr << "invalid index " << index << endl;
exit(10);
}
}
/// returns true if the index is added now or false if the index already existed
inline bool add(int index) {
//validity of index is checked in contains()
if (contains(index))
return false;
index_position[index] = list_head;
index_list[list_head++] = index;
return true;
}
public:
inline IndexDSBase(int index_limit): index_limit_(index_limit), index_list(index_limit), index_position(index_limit), list_head(0) {
}
inline void clear() {
list_head = 0;
}
inline bool contains(int index) const {
check_index_validity(index);
int pos = index_position[index];
return 0 <= pos && pos < list_head && index_list[pos] == index;
}
};
/// Performs operations in O(1) time
struct IndexSet: public IndexDSBase {
using IndexDSBase::IndexDSBase;
using IndexDSBase::add;
};
/// Performs operations in O(1) time
tpc(T) class IndexMap: public IndexDSBase {
vector<T> index_value;
public:
inline IndexMap(int index_limit): IndexDSBase(index_limit), index_value(index_limit) {
}
inline T& operator[](int index) {
//validity of index is checked in add()
if (add(index))
index_value[index] = T();
return index_value[index];
}
};
/////////////////////////
int n, m, k;
VI vertex_key;
vector<vector<PII>> adj;
unique_ptr<DisjointSet> djs;
/////////////////////////
int span_head;
int valid_root;
VI span;
unique_ptr<IndexSet> mark;
unique_ptr<IndexSet> key_available;
unique_ptr<IndexMap<VI>> key_locked_adj;
inline void add2span(int x) {
if (djs->findRoot(x) != valid_root)
throw x;
mark->add(x);
span[span_head++] = x;
}
inline int compute_span(int root) {
key_available->clear();
span_head = 0;
key_locked_adj->clear();
mark->clear();
valid_root = djs->findRoot(root);
add2span(root);
for (int tail = 0; tail<span_head; tail++) {
//show(tail);
int x = span[tail];
int x_key = vertex_key[x];
if (key_available->add(x_key)) {
for (int y : (*key_locked_adj)[x_key])
if (!mark->contains(y))
add2span(y);
(*key_locked_adj)[x_key].clear();
}
for (auto p: adj[x])
if (!mark->contains(p.first)) {
if (key_available->contains(p.second))
add2span(p.first);
else
(*key_locked_adj)[p.second].push_back(p.first);
}
}
return span_head;
}
VI find_reachable(VI r, VI u, VI v, VI c) {
n = sz(r);
m = sz(c);
k = max(*max_element(allOf(r)), *max_element(allOf(c)))+1;
vertex_key = r;
adj.assign(n, vector<PII>());
forn(j, m) {
adj[u[j]].emplace_back(v[j], c[j]);
adj[v[j]].emplace_back(u[j], c[j]);
}
djs = make_unique<DisjointSet>(n);
mark = make_unique<IndexSet>(n);
key_available = make_unique<IndexSet>(k);
key_locked_adj = make_unique<IndexMap<VI>>(k);
span.resize(n);
map<int, VI> finalized_span;
VI active_roots(n);
forn(i, n)
active_roots[i] = i;
int min_span = n+1;
while (!active_roots.empty()) {
//show(active_roots.size());
vector<PII> to_merge;
VB is_active(n, false);
for (int a : active_roots) {
//show(a);
try {
int ss = compute_span(a);
//show(ss);
min_span = min(min_span, ss);
finalized_span[a] = VI(span.begin(), span.begin()+span_head);
} catch (int b) {
//show(b);
to_merge.emplace_back(a, b);
is_active[a] = true;
}
}
for (auto p : to_merge)
if (djs->merge(p.first, p.second))
is_active[p.first] = false;
active_roots.clear();
forn(i, n)
if (is_active[i])
active_roots.push_back(i);
}
key_locked_adj.reset(nullptr);
key_available.reset(nullptr);
mark.reset(nullptr);
djs.reset(nullptr);
VI ans(n, 0);
for (auto p : finalized_span)
if (sz(p.second) == min_span)
for (int x : p.second)
ans[x] = 1;
return ans;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
332 KB |
Output is correct |
2 |
Correct |
4 ms |
332 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
3 ms |
332 KB |
Output is correct |
5 |
Correct |
2 ms |
332 KB |
Output is correct |
6 |
Correct |
2 ms |
332 KB |
Output is correct |
7 |
Correct |
3 ms |
332 KB |
Output is correct |
8 |
Correct |
6 ms |
332 KB |
Output is correct |
9 |
Correct |
4 ms |
332 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
332 KB |
Output is correct |
2 |
Correct |
4 ms |
332 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
3 ms |
332 KB |
Output is correct |
5 |
Correct |
2 ms |
332 KB |
Output is correct |
6 |
Correct |
2 ms |
332 KB |
Output is correct |
7 |
Correct |
3 ms |
332 KB |
Output is correct |
8 |
Correct |
6 ms |
332 KB |
Output is correct |
9 |
Correct |
4 ms |
332 KB |
Output is correct |
10 |
Correct |
3 ms |
332 KB |
Output is correct |
11 |
Correct |
5 ms |
332 KB |
Output is correct |
12 |
Correct |
4 ms |
332 KB |
Output is correct |
13 |
Correct |
3 ms |
332 KB |
Output is correct |
14 |
Correct |
2 ms |
332 KB |
Output is correct |
15 |
Correct |
3 ms |
332 KB |
Output is correct |
16 |
Correct |
3 ms |
332 KB |
Output is correct |
17 |
Correct |
3 ms |
332 KB |
Output is correct |
18 |
Correct |
3 ms |
332 KB |
Output is correct |
19 |
Correct |
3 ms |
332 KB |
Output is correct |
20 |
Correct |
3 ms |
332 KB |
Output is correct |
21 |
Correct |
5 ms |
332 KB |
Output is correct |
22 |
Correct |
3 ms |
332 KB |
Output is correct |
23 |
Correct |
3 ms |
332 KB |
Output is correct |
24 |
Correct |
3 ms |
380 KB |
Output is correct |
25 |
Correct |
6 ms |
384 KB |
Output is correct |
26 |
Correct |
5 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
332 KB |
Output is correct |
2 |
Correct |
4 ms |
332 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
3 ms |
332 KB |
Output is correct |
5 |
Correct |
2 ms |
332 KB |
Output is correct |
6 |
Correct |
2 ms |
332 KB |
Output is correct |
7 |
Correct |
3 ms |
332 KB |
Output is correct |
8 |
Correct |
6 ms |
332 KB |
Output is correct |
9 |
Correct |
4 ms |
332 KB |
Output is correct |
10 |
Correct |
3 ms |
332 KB |
Output is correct |
11 |
Correct |
5 ms |
332 KB |
Output is correct |
12 |
Correct |
4 ms |
332 KB |
Output is correct |
13 |
Correct |
3 ms |
332 KB |
Output is correct |
14 |
Correct |
2 ms |
332 KB |
Output is correct |
15 |
Correct |
3 ms |
332 KB |
Output is correct |
16 |
Correct |
3 ms |
332 KB |
Output is correct |
17 |
Correct |
3 ms |
332 KB |
Output is correct |
18 |
Correct |
3 ms |
332 KB |
Output is correct |
19 |
Correct |
3 ms |
332 KB |
Output is correct |
20 |
Correct |
3 ms |
332 KB |
Output is correct |
21 |
Correct |
5 ms |
332 KB |
Output is correct |
22 |
Correct |
3 ms |
332 KB |
Output is correct |
23 |
Correct |
3 ms |
332 KB |
Output is correct |
24 |
Correct |
3 ms |
380 KB |
Output is correct |
25 |
Correct |
6 ms |
384 KB |
Output is correct |
26 |
Correct |
5 ms |
384 KB |
Output is correct |
27 |
Correct |
16 ms |
716 KB |
Output is correct |
28 |
Correct |
9 ms |
716 KB |
Output is correct |
29 |
Correct |
9 ms |
708 KB |
Output is correct |
30 |
Correct |
9 ms |
492 KB |
Output is correct |
31 |
Correct |
4 ms |
592 KB |
Output is correct |
32 |
Correct |
6 ms |
340 KB |
Output is correct |
33 |
Correct |
8 ms |
468 KB |
Output is correct |
34 |
Correct |
11 ms |
460 KB |
Output is correct |
35 |
Correct |
13 ms |
484 KB |
Output is correct |
36 |
Correct |
15 ms |
616 KB |
Output is correct |
37 |
Correct |
14 ms |
608 KB |
Output is correct |
38 |
Correct |
13 ms |
588 KB |
Output is correct |
39 |
Correct |
15 ms |
640 KB |
Output is correct |
40 |
Correct |
9 ms |
484 KB |
Output is correct |
41 |
Correct |
12 ms |
540 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
332 KB |
Output is correct |
2 |
Correct |
4 ms |
332 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
3 ms |
332 KB |
Output is correct |
5 |
Correct |
2 ms |
332 KB |
Output is correct |
6 |
Correct |
2 ms |
332 KB |
Output is correct |
7 |
Correct |
3 ms |
332 KB |
Output is correct |
8 |
Correct |
6 ms |
332 KB |
Output is correct |
9 |
Correct |
4 ms |
332 KB |
Output is correct |
10 |
Correct |
1075 ms |
24680 KB |
Output is correct |
11 |
Correct |
2568 ms |
41720 KB |
Output is correct |
12 |
Correct |
363 ms |
7716 KB |
Output is correct |
13 |
Correct |
2346 ms |
40156 KB |
Output is correct |
14 |
Correct |
2041 ms |
37384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
332 KB |
Output is correct |
2 |
Correct |
4 ms |
332 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
3 ms |
332 KB |
Output is correct |
5 |
Correct |
2 ms |
332 KB |
Output is correct |
6 |
Correct |
2 ms |
332 KB |
Output is correct |
7 |
Correct |
3 ms |
332 KB |
Output is correct |
8 |
Correct |
6 ms |
332 KB |
Output is correct |
9 |
Correct |
4 ms |
332 KB |
Output is correct |
10 |
Correct |
3 ms |
332 KB |
Output is correct |
11 |
Correct |
5 ms |
332 KB |
Output is correct |
12 |
Correct |
4 ms |
332 KB |
Output is correct |
13 |
Correct |
3 ms |
332 KB |
Output is correct |
14 |
Correct |
2 ms |
332 KB |
Output is correct |
15 |
Correct |
3 ms |
332 KB |
Output is correct |
16 |
Correct |
3 ms |
332 KB |
Output is correct |
17 |
Correct |
3 ms |
332 KB |
Output is correct |
18 |
Correct |
3 ms |
332 KB |
Output is correct |
19 |
Correct |
3 ms |
332 KB |
Output is correct |
20 |
Correct |
3 ms |
332 KB |
Output is correct |
21 |
Correct |
5 ms |
332 KB |
Output is correct |
22 |
Correct |
3 ms |
332 KB |
Output is correct |
23 |
Correct |
3 ms |
332 KB |
Output is correct |
24 |
Correct |
3 ms |
380 KB |
Output is correct |
25 |
Correct |
6 ms |
384 KB |
Output is correct |
26 |
Correct |
5 ms |
384 KB |
Output is correct |
27 |
Correct |
16 ms |
716 KB |
Output is correct |
28 |
Correct |
9 ms |
716 KB |
Output is correct |
29 |
Correct |
9 ms |
708 KB |
Output is correct |
30 |
Correct |
9 ms |
492 KB |
Output is correct |
31 |
Correct |
4 ms |
592 KB |
Output is correct |
32 |
Correct |
6 ms |
340 KB |
Output is correct |
33 |
Correct |
8 ms |
468 KB |
Output is correct |
34 |
Correct |
11 ms |
460 KB |
Output is correct |
35 |
Correct |
13 ms |
484 KB |
Output is correct |
36 |
Correct |
15 ms |
616 KB |
Output is correct |
37 |
Correct |
14 ms |
608 KB |
Output is correct |
38 |
Correct |
13 ms |
588 KB |
Output is correct |
39 |
Correct |
15 ms |
640 KB |
Output is correct |
40 |
Correct |
9 ms |
484 KB |
Output is correct |
41 |
Correct |
12 ms |
540 KB |
Output is correct |
42 |
Correct |
1075 ms |
24680 KB |
Output is correct |
43 |
Correct |
2568 ms |
41720 KB |
Output is correct |
44 |
Correct |
363 ms |
7716 KB |
Output is correct |
45 |
Correct |
2346 ms |
40156 KB |
Output is correct |
46 |
Correct |
2041 ms |
37384 KB |
Output is correct |
47 |
Correct |
4 ms |
336 KB |
Output is correct |
48 |
Correct |
3 ms |
336 KB |
Output is correct |
49 |
Correct |
11 ms |
420 KB |
Output is correct |
50 |
Correct |
1862 ms |
38584 KB |
Output is correct |
51 |
Correct |
2977 ms |
49528 KB |
Output is correct |
52 |
Correct |
1136 ms |
46216 KB |
Output is correct |
53 |
Correct |
1025 ms |
46200 KB |
Output is correct |
54 |
Correct |
1047 ms |
46276 KB |
Output is correct |
55 |
Correct |
862 ms |
31472 KB |
Output is correct |
56 |
Correct |
1215 ms |
70032 KB |
Output is correct |
57 |
Correct |
535 ms |
80168 KB |
Output is correct |
58 |
Correct |
2082 ms |
58988 KB |
Output is correct |
59 |
Correct |
1816 ms |
40768 KB |
Output is correct |
60 |
Correct |
1931 ms |
38608 KB |
Output is correct |
61 |
Correct |
1746 ms |
38640 KB |
Output is correct |
62 |
Execution timed out |
3055 ms |
31068 KB |
Time limit exceeded |
63 |
Halted |
0 ms |
0 KB |
- |