#include <bits/stdc++.h>
using namespace std;
vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c){
int n = r.size();
int m = u.size();
vector<vector<int>> adj(n);
vector<vector<vector<int>>> lock(n, vector<vector<int>>(n));
for (int i = 0; i < m; ++i){
adj[u[i]].push_back(v[i]);
adj[v[i]].push_back(u[i]);
lock[u[i]][v[i]].push_back(c[i]);
lock[v[i]][u[i]].push_back(c[i]);
}
vector<int> out(n);
for (int i = 0; i < n; ++i){
vector<bool> visited(n, false);
int count = 0;
set<int> obtained = {-1};
deque<pair<int, int>> dq;
dq.push_back({i, -1});
while (!dq.empty()){
auto h = dq.front();
dq.pop_front();
if (visited[h.first]){
continue;
}
if (obtained.find(h.second) == obtained.end()){
continue;
}
visited[h.first] = true;
obtained.insert(r[h.first]);
count += 1;
for (auto k : adj[h.first]){
for (auto e : lock[h.first][k]){
if (obtained.find(e) != obtained.end()){
dq.push_front({k, e});
}
else{
dq.push_back({k, e});
}
}
}
}
out[i] = count;
}
int worst = out[0];
for (int i = 0; i < n; ++i){
worst = min(worst, out[i]);
}
for (int i = 0; i < n; ++i){
out[i] = out[i] == worst;
}
return out;
}
signed tester(){
vector<int> out = 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 k : out){
cout << k << " ";
}
}
Compilation message
keys.cpp: In function 'int tester()':
keys.cpp:64:1: warning: no return statement in function returning non-void [-Wreturn-type]
64 | }
| ^
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
1116 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
1 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
344 KB |
Output is correct |
8 |
Correct |
1 ms |
860 KB |
Output is correct |
9 |
Correct |
1 ms |
1116 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
1116 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
1 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
344 KB |
Output is correct |
8 |
Correct |
1 ms |
860 KB |
Output is correct |
9 |
Correct |
1 ms |
1116 KB |
Output is correct |
10 |
Correct |
3 ms |
1368 KB |
Output is correct |
11 |
Correct |
3 ms |
1372 KB |
Output is correct |
12 |
Correct |
3 ms |
1372 KB |
Output is correct |
13 |
Correct |
0 ms |
348 KB |
Output is correct |
14 |
Correct |
0 ms |
348 KB |
Output is correct |
15 |
Correct |
4 ms |
860 KB |
Output is correct |
16 |
Correct |
0 ms |
344 KB |
Output is correct |
17 |
Correct |
1 ms |
348 KB |
Output is correct |
18 |
Correct |
1 ms |
604 KB |
Output is correct |
19 |
Correct |
0 ms |
348 KB |
Output is correct |
20 |
Correct |
1 ms |
348 KB |
Output is correct |
21 |
Correct |
4 ms |
1568 KB |
Output is correct |
22 |
Correct |
2 ms |
344 KB |
Output is correct |
23 |
Correct |
6 ms |
860 KB |
Output is correct |
24 |
Correct |
6 ms |
860 KB |
Output is correct |
25 |
Correct |
9 ms |
1116 KB |
Output is correct |
26 |
Correct |
9 ms |
1116 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
1116 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
1 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
344 KB |
Output is correct |
8 |
Correct |
1 ms |
860 KB |
Output is correct |
9 |
Correct |
1 ms |
1116 KB |
Output is correct |
10 |
Correct |
3 ms |
1368 KB |
Output is correct |
11 |
Correct |
3 ms |
1372 KB |
Output is correct |
12 |
Correct |
3 ms |
1372 KB |
Output is correct |
13 |
Correct |
0 ms |
348 KB |
Output is correct |
14 |
Correct |
0 ms |
348 KB |
Output is correct |
15 |
Correct |
4 ms |
860 KB |
Output is correct |
16 |
Correct |
0 ms |
344 KB |
Output is correct |
17 |
Correct |
1 ms |
348 KB |
Output is correct |
18 |
Correct |
1 ms |
604 KB |
Output is correct |
19 |
Correct |
0 ms |
348 KB |
Output is correct |
20 |
Correct |
1 ms |
348 KB |
Output is correct |
21 |
Correct |
4 ms |
1568 KB |
Output is correct |
22 |
Correct |
2 ms |
344 KB |
Output is correct |
23 |
Correct |
6 ms |
860 KB |
Output is correct |
24 |
Correct |
6 ms |
860 KB |
Output is correct |
25 |
Correct |
9 ms |
1116 KB |
Output is correct |
26 |
Correct |
9 ms |
1116 KB |
Output is correct |
27 |
Correct |
372 ms |
94796 KB |
Output is correct |
28 |
Correct |
365 ms |
94800 KB |
Output is correct |
29 |
Correct |
371 ms |
95048 KB |
Output is correct |
30 |
Correct |
155 ms |
17240 KB |
Output is correct |
31 |
Correct |
13 ms |
24156 KB |
Output is correct |
32 |
Correct |
2 ms |
2396 KB |
Output is correct |
33 |
Correct |
9 ms |
15516 KB |
Output is correct |
34 |
Correct |
121 ms |
24132 KB |
Output is correct |
35 |
Correct |
174 ms |
13836 KB |
Output is correct |
36 |
Correct |
804 ms |
53692 KB |
Output is correct |
37 |
Correct |
787 ms |
53596 KB |
Output is correct |
38 |
Correct |
1244 ms |
85844 KB |
Output is correct |
39 |
Correct |
1241 ms |
85844 KB |
Output is correct |
40 |
Correct |
36 ms |
23900 KB |
Output is correct |
41 |
Correct |
210 ms |
24216 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
1116 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
1 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
344 KB |
Output is correct |
8 |
Correct |
1 ms |
860 KB |
Output is correct |
9 |
Correct |
1 ms |
1116 KB |
Output is correct |
10 |
Runtime error |
1249 ms |
2097152 KB |
Execution killed with signal 9 |
11 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
1116 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
1 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
344 KB |
Output is correct |
8 |
Correct |
1 ms |
860 KB |
Output is correct |
9 |
Correct |
1 ms |
1116 KB |
Output is correct |
10 |
Correct |
3 ms |
1368 KB |
Output is correct |
11 |
Correct |
3 ms |
1372 KB |
Output is correct |
12 |
Correct |
3 ms |
1372 KB |
Output is correct |
13 |
Correct |
0 ms |
348 KB |
Output is correct |
14 |
Correct |
0 ms |
348 KB |
Output is correct |
15 |
Correct |
4 ms |
860 KB |
Output is correct |
16 |
Correct |
0 ms |
344 KB |
Output is correct |
17 |
Correct |
1 ms |
348 KB |
Output is correct |
18 |
Correct |
1 ms |
604 KB |
Output is correct |
19 |
Correct |
0 ms |
348 KB |
Output is correct |
20 |
Correct |
1 ms |
348 KB |
Output is correct |
21 |
Correct |
4 ms |
1568 KB |
Output is correct |
22 |
Correct |
2 ms |
344 KB |
Output is correct |
23 |
Correct |
6 ms |
860 KB |
Output is correct |
24 |
Correct |
6 ms |
860 KB |
Output is correct |
25 |
Correct |
9 ms |
1116 KB |
Output is correct |
26 |
Correct |
9 ms |
1116 KB |
Output is correct |
27 |
Correct |
372 ms |
94796 KB |
Output is correct |
28 |
Correct |
365 ms |
94800 KB |
Output is correct |
29 |
Correct |
371 ms |
95048 KB |
Output is correct |
30 |
Correct |
155 ms |
17240 KB |
Output is correct |
31 |
Correct |
13 ms |
24156 KB |
Output is correct |
32 |
Correct |
2 ms |
2396 KB |
Output is correct |
33 |
Correct |
9 ms |
15516 KB |
Output is correct |
34 |
Correct |
121 ms |
24132 KB |
Output is correct |
35 |
Correct |
174 ms |
13836 KB |
Output is correct |
36 |
Correct |
804 ms |
53692 KB |
Output is correct |
37 |
Correct |
787 ms |
53596 KB |
Output is correct |
38 |
Correct |
1244 ms |
85844 KB |
Output is correct |
39 |
Correct |
1241 ms |
85844 KB |
Output is correct |
40 |
Correct |
36 ms |
23900 KB |
Output is correct |
41 |
Correct |
210 ms |
24216 KB |
Output is correct |
42 |
Runtime error |
1249 ms |
2097152 KB |
Execution killed with signal 9 |
43 |
Halted |
0 ms |
0 KB |
- |