# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
680336 |
2023-01-10T15:19:00 Z |
DennisTran |
Keys (IOI21_keys) |
C++17 |
|
709 ms |
44568 KB |
#include <bits/stdc++.h>
using namespace std;
// randomized
const int n_max = 300500;
int visited_list[n_max];
bool has_key[n_max];
bool visited[n_max];
int homekey[n_max];
int a[n_max];
pair<int,int> adj[2*n_max];
pair<int,int>* z[n_max];
bool finished[n_max];
// essentially, this stores the blocked position
// vector<int> blocked[max_keys] with push/pop is too slow
// we need to manage this ourself instead of relying on library
int blocked_counter[n_max];
int blocked3[n_max]; // stores the actual values
int* blocked2[n_max]; // stores pointers
int s = 1e6;
int counter = 0;
void cleanup() {
for(int j=0; j<counter; j++) {
int i = visited_list[j];
visited[i] = false;
has_key[homekey[i]] = false;
for(pair<int,int>* p = z[i]; p<z[i+1]; p++) {
blocked_counter[p->first] = 0;
}
}
}
int dfs_stack[n_max];
int explore(int x) { // returns min(limit, size of component)
int* pt = dfs_stack;
*pt = x;
pt++; // stack always points to 1 higher
counter = 1;
visited_list[0] = x;
visited[x] = true;
while(pt > dfs_stack) {
if(counter>s) {
return 1e6;
}
pt--; // pop item
int next = *pt;
if(!has_key[homekey[next]]) {
has_key[homekey[next]] = true;
for(int j=0; j<blocked_counter[homekey[next]]; j++) {
int i = blocked2[homekey[next]][j];
if(!visited[i]) {
if(finished[i] || a[i]!=a[x]) {
return 1e6;
}
visited[i] = true;
visited_list[counter] = i;
counter++;
*pt = i; // push item
pt++;
}
}
blocked_counter[homekey[next]] = 0;
}
for(pair<int,int>* p = z[next]; p<z[next+1]; p++) {
//assert(p<z[next+1]);
if(visited[p->second]) continue;
// we can effectively delete edges that go to a bigger component
// if you cant use this edge eventually, good
// else, you use this edge eventually
// but this means we must have came from a different component
// in which answer is not optimal anyway
// we can pretend this edge does not exist(!)
if(a[p->second] > a[x]) continue;
if(has_key[p->first]) {
if(finished[p->second] || a[p->second] != a[x]) {
return 1e6;
}
visited_list[counter] = p->second;
visited[p->second] = true;
counter++;
*pt = p->second; // push item
pt++;
} else {
blocked2[p->first][blocked_counter[p->first]] = p->second;
blocked_counter[p->first]++;
}
}
}
for(int* p=visited_list; p<visited_list+counter; p++) {
int i = *p;
a[i] = min(a[i], counter);
}
return counter;
}
tuple<int,int,int> t[2*n_max];
vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c) {
int m = c.size();
int n = r.size();
for(int i=0; i<n; i++) {
a[i] = 1e6;
}
for(int i=0; i<m; i++) {
//adj[u[i]].emplace_back(c[i], v[i]);
//adj[v[i]].emplace_back(c[i], u[i]);
blocked_counter[c[i]]++;
t[2*i] = make_tuple(u[i], v[i], c[i]);
t[2*i+1] = make_tuple(v[i], u[i], c[i]);
}
sort(t, t+2*m);
z[0] = adj;
for(int i=0; i<2*m; i++) {
adj[i] = make_pair(get<2>(t[i]), get<1>(t[i]));
if(i!=0 && get<0>(t[i])!=get<0>(t[i-1])) {
for(int j=get<0>(t[i-1])+1; j<=get<0>(t[i]); j++) {
z[j] = adj + i;
}
}
}
z[get<0>(t[2*m-1])+1] = adj + 2*m;
blocked2[0] = blocked3;
for(int i=1; i<n_max; i++) {
blocked2[i] = blocked2[i-1] + blocked_counter[i-1];
}
for(int i=0; i<n_max; i++) {
blocked_counter[i] = 0;
}
for(int i=0; i<n; i++) {
homekey[i] = r[i];
}
vector<int> p(2*m);
for(int i=0; i<m; i++) {
p[2*i] = u[i];
p[2*i+1] = v[i];
}
random_shuffle(p.begin(), p.end());
for(int i: p) {
if(!finished[i]) {
s = min(s, explore(i));
finished[i] = true;
cleanup();
}
}
for(int i=0; i<n; i++) {
if(!finished[i]) {
s = min(s, explore(i));
finished[i] = true;
cleanup();
}
}
vector<int> ans(n);
for(int i=0; i<n; i++) {
if(a[i]==s) {
ans[i] = 1;
}
}
return ans;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
3796 KB |
Output is correct |
2 |
Correct |
2 ms |
3796 KB |
Output is correct |
3 |
Correct |
3 ms |
3788 KB |
Output is correct |
4 |
Correct |
2 ms |
3924 KB |
Output is correct |
5 |
Correct |
2 ms |
3796 KB |
Output is correct |
6 |
Correct |
2 ms |
3896 KB |
Output is correct |
7 |
Correct |
2 ms |
3896 KB |
Output is correct |
8 |
Correct |
2 ms |
3924 KB |
Output is correct |
9 |
Correct |
2 ms |
3924 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
3796 KB |
Output is correct |
2 |
Correct |
2 ms |
3796 KB |
Output is correct |
3 |
Correct |
3 ms |
3788 KB |
Output is correct |
4 |
Correct |
2 ms |
3924 KB |
Output is correct |
5 |
Correct |
2 ms |
3796 KB |
Output is correct |
6 |
Correct |
2 ms |
3896 KB |
Output is correct |
7 |
Correct |
2 ms |
3896 KB |
Output is correct |
8 |
Correct |
2 ms |
3924 KB |
Output is correct |
9 |
Correct |
2 ms |
3924 KB |
Output is correct |
10 |
Correct |
2 ms |
3796 KB |
Output is correct |
11 |
Correct |
2 ms |
3924 KB |
Output is correct |
12 |
Correct |
2 ms |
3796 KB |
Output is correct |
13 |
Correct |
2 ms |
3796 KB |
Output is correct |
14 |
Correct |
2 ms |
3796 KB |
Output is correct |
15 |
Correct |
2 ms |
3896 KB |
Output is correct |
16 |
Correct |
2 ms |
3796 KB |
Output is correct |
17 |
Correct |
2 ms |
3796 KB |
Output is correct |
18 |
Correct |
2 ms |
3796 KB |
Output is correct |
19 |
Correct |
2 ms |
3796 KB |
Output is correct |
20 |
Correct |
3 ms |
3796 KB |
Output is correct |
21 |
Correct |
2 ms |
3924 KB |
Output is correct |
22 |
Correct |
2 ms |
3900 KB |
Output is correct |
23 |
Correct |
2 ms |
3796 KB |
Output is correct |
24 |
Correct |
2 ms |
3924 KB |
Output is correct |
25 |
Correct |
2 ms |
3796 KB |
Output is correct |
26 |
Correct |
2 ms |
3924 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
3796 KB |
Output is correct |
2 |
Correct |
2 ms |
3796 KB |
Output is correct |
3 |
Correct |
3 ms |
3788 KB |
Output is correct |
4 |
Correct |
2 ms |
3924 KB |
Output is correct |
5 |
Correct |
2 ms |
3796 KB |
Output is correct |
6 |
Correct |
2 ms |
3896 KB |
Output is correct |
7 |
Correct |
2 ms |
3896 KB |
Output is correct |
8 |
Correct |
2 ms |
3924 KB |
Output is correct |
9 |
Correct |
2 ms |
3924 KB |
Output is correct |
10 |
Correct |
2 ms |
3796 KB |
Output is correct |
11 |
Correct |
2 ms |
3924 KB |
Output is correct |
12 |
Correct |
2 ms |
3796 KB |
Output is correct |
13 |
Correct |
2 ms |
3796 KB |
Output is correct |
14 |
Correct |
2 ms |
3796 KB |
Output is correct |
15 |
Correct |
2 ms |
3896 KB |
Output is correct |
16 |
Correct |
2 ms |
3796 KB |
Output is correct |
17 |
Correct |
2 ms |
3796 KB |
Output is correct |
18 |
Correct |
2 ms |
3796 KB |
Output is correct |
19 |
Correct |
2 ms |
3796 KB |
Output is correct |
20 |
Correct |
3 ms |
3796 KB |
Output is correct |
21 |
Correct |
2 ms |
3924 KB |
Output is correct |
22 |
Correct |
2 ms |
3900 KB |
Output is correct |
23 |
Correct |
2 ms |
3796 KB |
Output is correct |
24 |
Correct |
2 ms |
3924 KB |
Output is correct |
25 |
Correct |
2 ms |
3796 KB |
Output is correct |
26 |
Correct |
2 ms |
3924 KB |
Output is correct |
27 |
Correct |
5 ms |
4052 KB |
Output is correct |
28 |
Correct |
4 ms |
4052 KB |
Output is correct |
29 |
Correct |
3 ms |
4052 KB |
Output is correct |
30 |
Correct |
3 ms |
3924 KB |
Output is correct |
31 |
Correct |
3 ms |
3904 KB |
Output is correct |
32 |
Correct |
2 ms |
3900 KB |
Output is correct |
33 |
Correct |
3 ms |
3924 KB |
Output is correct |
34 |
Correct |
3 ms |
3924 KB |
Output is correct |
35 |
Correct |
3 ms |
3924 KB |
Output is correct |
36 |
Correct |
4 ms |
4036 KB |
Output is correct |
37 |
Correct |
4 ms |
4052 KB |
Output is correct |
38 |
Correct |
4 ms |
4052 KB |
Output is correct |
39 |
Correct |
4 ms |
4052 KB |
Output is correct |
40 |
Correct |
3 ms |
3924 KB |
Output is correct |
41 |
Correct |
3 ms |
4052 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
3796 KB |
Output is correct |
2 |
Correct |
2 ms |
3796 KB |
Output is correct |
3 |
Correct |
3 ms |
3788 KB |
Output is correct |
4 |
Correct |
2 ms |
3924 KB |
Output is correct |
5 |
Correct |
2 ms |
3796 KB |
Output is correct |
6 |
Correct |
2 ms |
3896 KB |
Output is correct |
7 |
Correct |
2 ms |
3896 KB |
Output is correct |
8 |
Correct |
2 ms |
3924 KB |
Output is correct |
9 |
Correct |
2 ms |
3924 KB |
Output is correct |
10 |
Correct |
196 ms |
33132 KB |
Output is correct |
11 |
Correct |
230 ms |
39880 KB |
Output is correct |
12 |
Correct |
42 ms |
10572 KB |
Output is correct |
13 |
Correct |
239 ms |
36724 KB |
Output is correct |
14 |
Correct |
289 ms |
40452 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
3796 KB |
Output is correct |
2 |
Correct |
2 ms |
3796 KB |
Output is correct |
3 |
Correct |
3 ms |
3788 KB |
Output is correct |
4 |
Correct |
2 ms |
3924 KB |
Output is correct |
5 |
Correct |
2 ms |
3796 KB |
Output is correct |
6 |
Correct |
2 ms |
3896 KB |
Output is correct |
7 |
Correct |
2 ms |
3896 KB |
Output is correct |
8 |
Correct |
2 ms |
3924 KB |
Output is correct |
9 |
Correct |
2 ms |
3924 KB |
Output is correct |
10 |
Correct |
2 ms |
3796 KB |
Output is correct |
11 |
Correct |
2 ms |
3924 KB |
Output is correct |
12 |
Correct |
2 ms |
3796 KB |
Output is correct |
13 |
Correct |
2 ms |
3796 KB |
Output is correct |
14 |
Correct |
2 ms |
3796 KB |
Output is correct |
15 |
Correct |
2 ms |
3896 KB |
Output is correct |
16 |
Correct |
2 ms |
3796 KB |
Output is correct |
17 |
Correct |
2 ms |
3796 KB |
Output is correct |
18 |
Correct |
2 ms |
3796 KB |
Output is correct |
19 |
Correct |
2 ms |
3796 KB |
Output is correct |
20 |
Correct |
3 ms |
3796 KB |
Output is correct |
21 |
Correct |
2 ms |
3924 KB |
Output is correct |
22 |
Correct |
2 ms |
3900 KB |
Output is correct |
23 |
Correct |
2 ms |
3796 KB |
Output is correct |
24 |
Correct |
2 ms |
3924 KB |
Output is correct |
25 |
Correct |
2 ms |
3796 KB |
Output is correct |
26 |
Correct |
2 ms |
3924 KB |
Output is correct |
27 |
Correct |
5 ms |
4052 KB |
Output is correct |
28 |
Correct |
4 ms |
4052 KB |
Output is correct |
29 |
Correct |
3 ms |
4052 KB |
Output is correct |
30 |
Correct |
3 ms |
3924 KB |
Output is correct |
31 |
Correct |
3 ms |
3904 KB |
Output is correct |
32 |
Correct |
2 ms |
3900 KB |
Output is correct |
33 |
Correct |
3 ms |
3924 KB |
Output is correct |
34 |
Correct |
3 ms |
3924 KB |
Output is correct |
35 |
Correct |
3 ms |
3924 KB |
Output is correct |
36 |
Correct |
4 ms |
4036 KB |
Output is correct |
37 |
Correct |
4 ms |
4052 KB |
Output is correct |
38 |
Correct |
4 ms |
4052 KB |
Output is correct |
39 |
Correct |
4 ms |
4052 KB |
Output is correct |
40 |
Correct |
3 ms |
3924 KB |
Output is correct |
41 |
Correct |
3 ms |
4052 KB |
Output is correct |
42 |
Correct |
196 ms |
33132 KB |
Output is correct |
43 |
Correct |
230 ms |
39880 KB |
Output is correct |
44 |
Correct |
42 ms |
10572 KB |
Output is correct |
45 |
Correct |
239 ms |
36724 KB |
Output is correct |
46 |
Correct |
289 ms |
40452 KB |
Output is correct |
47 |
Correct |
2 ms |
3796 KB |
Output is correct |
48 |
Correct |
2 ms |
3796 KB |
Output is correct |
49 |
Correct |
2 ms |
3796 KB |
Output is correct |
50 |
Correct |
215 ms |
39936 KB |
Output is correct |
51 |
Correct |
239 ms |
42884 KB |
Output is correct |
52 |
Correct |
233 ms |
30568 KB |
Output is correct |
53 |
Correct |
193 ms |
29876 KB |
Output is correct |
54 |
Correct |
231 ms |
30384 KB |
Output is correct |
55 |
Correct |
251 ms |
35120 KB |
Output is correct |
56 |
Correct |
327 ms |
44568 KB |
Output is correct |
57 |
Correct |
234 ms |
42160 KB |
Output is correct |
58 |
Correct |
241 ms |
43264 KB |
Output is correct |
59 |
Correct |
634 ms |
39708 KB |
Output is correct |
60 |
Correct |
668 ms |
39812 KB |
Output is correct |
61 |
Correct |
701 ms |
40056 KB |
Output is correct |
62 |
Correct |
494 ms |
36848 KB |
Output is correct |
63 |
Correct |
170 ms |
37712 KB |
Output is correct |
64 |
Correct |
6 ms |
4420 KB |
Output is correct |
65 |
Correct |
6 ms |
4436 KB |
Output is correct |
66 |
Correct |
495 ms |
36940 KB |
Output is correct |
67 |
Correct |
26 ms |
7576 KB |
Output is correct |
68 |
Correct |
41 ms |
10136 KB |
Output is correct |
69 |
Correct |
709 ms |
39684 KB |
Output is correct |
70 |
Correct |
82 ms |
16464 KB |
Output is correct |
71 |
Correct |
305 ms |
42232 KB |
Output is correct |
72 |
Correct |
650 ms |
39592 KB |
Output is correct |
73 |
Correct |
494 ms |
36888 KB |
Output is correct |