| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 582367 |
2022-06-23T16:53:14 Z |
georgievskiy |
Keys (IOI21_keys) |
C++17 |
|
1301 ms |
61300 KB |
#include <bits/stdc++.h>
#include <vector>
using namespace std;
using vi = vector<int>;
typedef vector<vector<pair<int, int>>> graph;
const int N = 3.1e5;
//const int N = 100;
vector<int> blocked[N];
int used[N], keys[N], travelled[N], a[N];
int n, m;
int timer = 0;
void travel(int start, vi& r, graph& g) {
int cnt = 0;
int cur = ++timer;
queue<int> q;
q.push(start);
vector<int> to_clear, used_list;
while (q.size()) {
int v = q.front(); q.pop();
if (travelled[v]) {
for (int x : to_clear)
blocked[x].clear();
return;
}
if (used[v] == cur)
continue;
cnt++;
used[v] = cur;
used_list.push_back(v);
int t = r[v];
if (keys[t] < cur) {
for (int x : blocked[t])
q.push(x);
keys[t] = cur;
}
for (auto u : g[v]) {
if (used[u.first] == cur)
continue;
if (keys[u.second] == cur) {
q.push(u.first);
} else {
to_clear.push_back(u.second);
blocked[u.second].push_back(u.first);
}
}
}
for (int x : to_clear)
blocked[x].clear();
for (int x : used_list)
a[x] = min(a[x], cnt);
}
std::vector<int> find_reachable(std::vector<int> r, std::vector<int> u, std::vector<int> v, std::vector<int> c) {
random_device rd;
mt19937 rng(rd());
n = r.size(), m = u.size();
graph g(n);
for (int i = 0; i < m; i++) {
g[u[i]].push_back({v[i], c[i]});
g[v[i]].push_back({u[i], c[i]});
}
vector<int> t;
for (int i = 0; i < m; i++)
t.push_back(u[i]), t.push_back(v[i]);
for (int i = 0; i < n; i++)
if (g[i].empty())
t.push_back(i);
shuffle(t.begin(), t.end(), rng);
fill(a, a + n, 1e9);
for (int v : t) {
if (travelled[v])
continue;
travel(v, r, g);
travelled[v] = 1;
}
int mn = *min_element(a, a + n);
vector<int> ans(n);
for (int i = 0; i < n; i++)
ans[i] = a[i] == mn;
return ans;
}
Compilation message
keys.cpp: In function 'std::vector<int> find_reachable(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
keys.cpp:87:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
87 | for (int i = 0; i < n; i++)
| ^~~
keys.cpp:89:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
89 | return ans;
| ^~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
7508 KB |
Output is correct |
| 2 |
Correct |
5 ms |
7508 KB |
Output is correct |
| 3 |
Correct |
5 ms |
7508 KB |
Output is correct |
| 4 |
Correct |
4 ms |
7508 KB |
Output is correct |
| 5 |
Correct |
4 ms |
7588 KB |
Output is correct |
| 6 |
Correct |
5 ms |
7508 KB |
Output is correct |
| 7 |
Correct |
5 ms |
7508 KB |
Output is correct |
| 8 |
Correct |
4 ms |
7636 KB |
Output is correct |
| 9 |
Correct |
5 ms |
7576 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
7508 KB |
Output is correct |
| 2 |
Correct |
5 ms |
7508 KB |
Output is correct |
| 3 |
Correct |
5 ms |
7508 KB |
Output is correct |
| 4 |
Correct |
4 ms |
7508 KB |
Output is correct |
| 5 |
Correct |
4 ms |
7588 KB |
Output is correct |
| 6 |
Correct |
5 ms |
7508 KB |
Output is correct |
| 7 |
Correct |
5 ms |
7508 KB |
Output is correct |
| 8 |
Correct |
4 ms |
7636 KB |
Output is correct |
| 9 |
Correct |
5 ms |
7576 KB |
Output is correct |
| 10 |
Correct |
5 ms |
7636 KB |
Output is correct |
| 11 |
Correct |
4 ms |
7636 KB |
Output is correct |
| 12 |
Correct |
5 ms |
7588 KB |
Output is correct |
| 13 |
Correct |
4 ms |
7584 KB |
Output is correct |
| 14 |
Correct |
5 ms |
7588 KB |
Output is correct |
| 15 |
Correct |
4 ms |
7636 KB |
Output is correct |
| 16 |
Correct |
5 ms |
7508 KB |
Output is correct |
| 17 |
Correct |
5 ms |
7508 KB |
Output is correct |
| 18 |
Correct |
4 ms |
7508 KB |
Output is correct |
| 19 |
Correct |
5 ms |
7508 KB |
Output is correct |
| 20 |
Correct |
5 ms |
7508 KB |
Output is correct |
| 21 |
Correct |
4 ms |
7636 KB |
Output is correct |
| 22 |
Correct |
4 ms |
7508 KB |
Output is correct |
| 23 |
Correct |
5 ms |
7636 KB |
Output is correct |
| 24 |
Correct |
5 ms |
7588 KB |
Output is correct |
| 25 |
Correct |
5 ms |
7520 KB |
Output is correct |
| 26 |
Correct |
4 ms |
7556 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
7508 KB |
Output is correct |
| 2 |
Correct |
5 ms |
7508 KB |
Output is correct |
| 3 |
Correct |
5 ms |
7508 KB |
Output is correct |
| 4 |
Correct |
4 ms |
7508 KB |
Output is correct |
| 5 |
Correct |
4 ms |
7588 KB |
Output is correct |
| 6 |
Correct |
5 ms |
7508 KB |
Output is correct |
| 7 |
Correct |
5 ms |
7508 KB |
Output is correct |
| 8 |
Correct |
4 ms |
7636 KB |
Output is correct |
| 9 |
Correct |
5 ms |
7576 KB |
Output is correct |
| 10 |
Correct |
5 ms |
7636 KB |
Output is correct |
| 11 |
Correct |
4 ms |
7636 KB |
Output is correct |
| 12 |
Correct |
5 ms |
7588 KB |
Output is correct |
| 13 |
Correct |
4 ms |
7584 KB |
Output is correct |
| 14 |
Correct |
5 ms |
7588 KB |
Output is correct |
| 15 |
Correct |
4 ms |
7636 KB |
Output is correct |
| 16 |
Correct |
5 ms |
7508 KB |
Output is correct |
| 17 |
Correct |
5 ms |
7508 KB |
Output is correct |
| 18 |
Correct |
4 ms |
7508 KB |
Output is correct |
| 19 |
Correct |
5 ms |
7508 KB |
Output is correct |
| 20 |
Correct |
5 ms |
7508 KB |
Output is correct |
| 21 |
Correct |
4 ms |
7636 KB |
Output is correct |
| 22 |
Correct |
4 ms |
7508 KB |
Output is correct |
| 23 |
Correct |
5 ms |
7636 KB |
Output is correct |
| 24 |
Correct |
5 ms |
7588 KB |
Output is correct |
| 25 |
Correct |
5 ms |
7520 KB |
Output is correct |
| 26 |
Correct |
4 ms |
7556 KB |
Output is correct |
| 27 |
Correct |
7 ms |
7892 KB |
Output is correct |
| 28 |
Correct |
7 ms |
7892 KB |
Output is correct |
| 29 |
Correct |
7 ms |
7892 KB |
Output is correct |
| 30 |
Correct |
5 ms |
7728 KB |
Output is correct |
| 31 |
Correct |
5 ms |
7636 KB |
Output is correct |
| 32 |
Correct |
5 ms |
7636 KB |
Output is correct |
| 33 |
Correct |
5 ms |
7724 KB |
Output is correct |
| 34 |
Correct |
5 ms |
7728 KB |
Output is correct |
| 35 |
Correct |
6 ms |
7636 KB |
Output is correct |
| 36 |
Correct |
8 ms |
7856 KB |
Output is correct |
| 37 |
Correct |
7 ms |
7764 KB |
Output is correct |
| 38 |
Correct |
7 ms |
7860 KB |
Output is correct |
| 39 |
Correct |
7 ms |
7876 KB |
Output is correct |
| 40 |
Correct |
5 ms |
7764 KB |
Output is correct |
| 41 |
Correct |
6 ms |
7764 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
7508 KB |
Output is correct |
| 2 |
Correct |
5 ms |
7508 KB |
Output is correct |
| 3 |
Correct |
5 ms |
7508 KB |
Output is correct |
| 4 |
Correct |
4 ms |
7508 KB |
Output is correct |
| 5 |
Correct |
4 ms |
7588 KB |
Output is correct |
| 6 |
Correct |
5 ms |
7508 KB |
Output is correct |
| 7 |
Correct |
5 ms |
7508 KB |
Output is correct |
| 8 |
Correct |
4 ms |
7636 KB |
Output is correct |
| 9 |
Correct |
5 ms |
7576 KB |
Output is correct |
| 10 |
Correct |
383 ms |
36924 KB |
Output is correct |
| 11 |
Correct |
410 ms |
52656 KB |
Output is correct |
| 12 |
Correct |
56 ms |
14880 KB |
Output is correct |
| 13 |
Correct |
389 ms |
43396 KB |
Output is correct |
| 14 |
Correct |
351 ms |
46904 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
7508 KB |
Output is correct |
| 2 |
Correct |
5 ms |
7508 KB |
Output is correct |
| 3 |
Correct |
5 ms |
7508 KB |
Output is correct |
| 4 |
Correct |
4 ms |
7508 KB |
Output is correct |
| 5 |
Correct |
4 ms |
7588 KB |
Output is correct |
| 6 |
Correct |
5 ms |
7508 KB |
Output is correct |
| 7 |
Correct |
5 ms |
7508 KB |
Output is correct |
| 8 |
Correct |
4 ms |
7636 KB |
Output is correct |
| 9 |
Correct |
5 ms |
7576 KB |
Output is correct |
| 10 |
Correct |
5 ms |
7636 KB |
Output is correct |
| 11 |
Correct |
4 ms |
7636 KB |
Output is correct |
| 12 |
Correct |
5 ms |
7588 KB |
Output is correct |
| 13 |
Correct |
4 ms |
7584 KB |
Output is correct |
| 14 |
Correct |
5 ms |
7588 KB |
Output is correct |
| 15 |
Correct |
4 ms |
7636 KB |
Output is correct |
| 16 |
Correct |
5 ms |
7508 KB |
Output is correct |
| 17 |
Correct |
5 ms |
7508 KB |
Output is correct |
| 18 |
Correct |
4 ms |
7508 KB |
Output is correct |
| 19 |
Correct |
5 ms |
7508 KB |
Output is correct |
| 20 |
Correct |
5 ms |
7508 KB |
Output is correct |
| 21 |
Correct |
4 ms |
7636 KB |
Output is correct |
| 22 |
Correct |
4 ms |
7508 KB |
Output is correct |
| 23 |
Correct |
5 ms |
7636 KB |
Output is correct |
| 24 |
Correct |
5 ms |
7588 KB |
Output is correct |
| 25 |
Correct |
5 ms |
7520 KB |
Output is correct |
| 26 |
Correct |
4 ms |
7556 KB |
Output is correct |
| 27 |
Correct |
7 ms |
7892 KB |
Output is correct |
| 28 |
Correct |
7 ms |
7892 KB |
Output is correct |
| 29 |
Correct |
7 ms |
7892 KB |
Output is correct |
| 30 |
Correct |
5 ms |
7728 KB |
Output is correct |
| 31 |
Correct |
5 ms |
7636 KB |
Output is correct |
| 32 |
Correct |
5 ms |
7636 KB |
Output is correct |
| 33 |
Correct |
5 ms |
7724 KB |
Output is correct |
| 34 |
Correct |
5 ms |
7728 KB |
Output is correct |
| 35 |
Correct |
6 ms |
7636 KB |
Output is correct |
| 36 |
Correct |
8 ms |
7856 KB |
Output is correct |
| 37 |
Correct |
7 ms |
7764 KB |
Output is correct |
| 38 |
Correct |
7 ms |
7860 KB |
Output is correct |
| 39 |
Correct |
7 ms |
7876 KB |
Output is correct |
| 40 |
Correct |
5 ms |
7764 KB |
Output is correct |
| 41 |
Correct |
6 ms |
7764 KB |
Output is correct |
| 42 |
Correct |
383 ms |
36924 KB |
Output is correct |
| 43 |
Correct |
410 ms |
52656 KB |
Output is correct |
| 44 |
Correct |
56 ms |
14880 KB |
Output is correct |
| 45 |
Correct |
389 ms |
43396 KB |
Output is correct |
| 46 |
Correct |
351 ms |
46904 KB |
Output is correct |
| 47 |
Correct |
4 ms |
7508 KB |
Output is correct |
| 48 |
Correct |
4 ms |
7592 KB |
Output is correct |
| 49 |
Correct |
6 ms |
7508 KB |
Output is correct |
| 50 |
Correct |
355 ms |
47420 KB |
Output is correct |
| 51 |
Correct |
384 ms |
49888 KB |
Output is correct |
| 52 |
Correct |
680 ms |
43276 KB |
Output is correct |
| 53 |
Correct |
715 ms |
43264 KB |
Output is correct |
| 54 |
Correct |
746 ms |
43300 KB |
Output is correct |
| 55 |
Correct |
511 ms |
38712 KB |
Output is correct |
| 56 |
Correct |
742 ms |
55240 KB |
Output is correct |
| 57 |
Correct |
450 ms |
53920 KB |
Output is correct |
| 58 |
Correct |
406 ms |
61300 KB |
Output is correct |
| 59 |
Correct |
1301 ms |
50388 KB |
Output is correct |
| 60 |
Correct |
1053 ms |
49604 KB |
Output is correct |
| 61 |
Correct |
1062 ms |
49832 KB |
Output is correct |
| 62 |
Correct |
854 ms |
43328 KB |
Output is correct |
| 63 |
Correct |
296 ms |
44812 KB |
Output is correct |
| 64 |
Correct |
10 ms |
8240 KB |
Output is correct |
| 65 |
Correct |
8 ms |
8256 KB |
Output is correct |
| 66 |
Correct |
866 ms |
43328 KB |
Output is correct |
| 67 |
Correct |
28 ms |
11408 KB |
Output is correct |
| 68 |
Correct |
46 ms |
14044 KB |
Output is correct |
| 69 |
Correct |
1212 ms |
50248 KB |
Output is correct |
| 70 |
Correct |
109 ms |
20520 KB |
Output is correct |
| 71 |
Correct |
332 ms |
47440 KB |
Output is correct |
| 72 |
Correct |
1147 ms |
50264 KB |
Output is correct |
| 73 |
Correct |
851 ms |
42912 KB |
Output is correct |
