# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
835467 |
2023-08-23T14:50:55 Z |
IS_Rushdi |
Keys (IOI21_keys) |
C++17 |
|
3000 ms |
2097152 KB |
#include <bits/stdc++.h>
using namespace std;
vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c) {
vector<int> ans(r.size(), 1);
int n = r.size();
int m = u.size();
vector<vector<vector<int>>>a(n,vector<vector<int>>(n,vector<int>()));
for(int i = 0; i < m; i++){
a[v[i]][c[i]].push_back(u[i]);
a[u[i]][c[i]].push_back(v[i]);
}
int mn = 2e9;
vector<int>cnt(n);
for(int i = 0; i < n; i++){
vector<bool>vis(n);
vector<bool>vis2(n);
vector<vector<int>>arr(n,vector<int>());
vector<int>keys;
queue<int>q;
q.push(i);
while(!q.empty()){
int node = q.front();
q.pop();
if(vis[node]) continue;
vis[node]=1;
if(!vis2[r[node]]){
keys.push_back(r[node]);
vis2[r[node]]=1;
for(int to : arr[r[node]]){
if(vis[to]) continue;
q.push(to);
}
}
for(int j = 0; j < n; j++){
if(!vis2[j]){
for(int to : a[node][j]){
if(vis[to]) continue;
arr[j].push_back(to);
}
}
else{
for(int to : a[node][j]){
if(vis[to]) continue;
q.push(to);
}
}
}
}
for(int j = 0; j < n; j++){
if(vis[j]) cnt[i]++;
}
mn = min(mn,cnt[i]);
}
for(int i = 0; i < n; i++){
if(cnt[i] == mn) ans[i] = 1;
else ans[i] = 0;
}
return ans;
}
// int main(){
// int n; cin >> n;
// vector<int>a(n);
// for(int i = 0; i < n; i++) cin >> a[i];
// int m; cin >> m;
// vector<int>b(m),c(m),d(m);
// for(int i = 0; i < m; i++) cin >> b[i];
// for(int i = 0; i < m; i++) cin >> c[i];
// for(int i = 0; i < m; i++) cin >> d[i];
// vector<int>ans = find_reachable(a,b,c,d);
// for(int i = 0; i < n; i++) cout << ans[i] << ' ';
// }
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
336 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
7 ms |
980 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
0 ms |
212 KB |
Output is correct |
8 |
Correct |
5 ms |
724 KB |
Output is correct |
9 |
Correct |
8 ms |
980 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
336 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
7 ms |
980 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
0 ms |
212 KB |
Output is correct |
8 |
Correct |
5 ms |
724 KB |
Output is correct |
9 |
Correct |
8 ms |
980 KB |
Output is correct |
10 |
Correct |
8 ms |
1236 KB |
Output is correct |
11 |
Correct |
7 ms |
1236 KB |
Output is correct |
12 |
Correct |
9 ms |
1236 KB |
Output is correct |
13 |
Correct |
0 ms |
212 KB |
Output is correct |
14 |
Correct |
0 ms |
212 KB |
Output is correct |
15 |
Correct |
7 ms |
724 KB |
Output is correct |
16 |
Correct |
0 ms |
212 KB |
Output is correct |
17 |
Correct |
0 ms |
212 KB |
Output is correct |
18 |
Correct |
1 ms |
468 KB |
Output is correct |
19 |
Correct |
0 ms |
212 KB |
Output is correct |
20 |
Correct |
1 ms |
340 KB |
Output is correct |
21 |
Correct |
17 ms |
1236 KB |
Output is correct |
22 |
Correct |
2 ms |
340 KB |
Output is correct |
23 |
Correct |
12 ms |
852 KB |
Output is correct |
24 |
Correct |
12 ms |
852 KB |
Output is correct |
25 |
Correct |
22 ms |
1172 KB |
Output is correct |
26 |
Correct |
23 ms |
1108 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
336 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
7 ms |
980 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
0 ms |
212 KB |
Output is correct |
8 |
Correct |
5 ms |
724 KB |
Output is correct |
9 |
Correct |
8 ms |
980 KB |
Output is correct |
10 |
Correct |
8 ms |
1236 KB |
Output is correct |
11 |
Correct |
7 ms |
1236 KB |
Output is correct |
12 |
Correct |
9 ms |
1236 KB |
Output is correct |
13 |
Correct |
0 ms |
212 KB |
Output is correct |
14 |
Correct |
0 ms |
212 KB |
Output is correct |
15 |
Correct |
7 ms |
724 KB |
Output is correct |
16 |
Correct |
0 ms |
212 KB |
Output is correct |
17 |
Correct |
0 ms |
212 KB |
Output is correct |
18 |
Correct |
1 ms |
468 KB |
Output is correct |
19 |
Correct |
0 ms |
212 KB |
Output is correct |
20 |
Correct |
1 ms |
340 KB |
Output is correct |
21 |
Correct |
17 ms |
1236 KB |
Output is correct |
22 |
Correct |
2 ms |
340 KB |
Output is correct |
23 |
Correct |
12 ms |
852 KB |
Output is correct |
24 |
Correct |
12 ms |
852 KB |
Output is correct |
25 |
Correct |
22 ms |
1172 KB |
Output is correct |
26 |
Correct |
23 ms |
1108 KB |
Output is correct |
27 |
Execution timed out |
3095 ms |
94464 KB |
Time limit exceeded |
28 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
336 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
7 ms |
980 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
0 ms |
212 KB |
Output is correct |
8 |
Correct |
5 ms |
724 KB |
Output is correct |
9 |
Correct |
8 ms |
980 KB |
Output is correct |
10 |
Runtime error |
1010 ms |
2097152 KB |
Execution killed with signal 9 |
11 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
336 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
7 ms |
980 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
0 ms |
212 KB |
Output is correct |
8 |
Correct |
5 ms |
724 KB |
Output is correct |
9 |
Correct |
8 ms |
980 KB |
Output is correct |
10 |
Correct |
8 ms |
1236 KB |
Output is correct |
11 |
Correct |
7 ms |
1236 KB |
Output is correct |
12 |
Correct |
9 ms |
1236 KB |
Output is correct |
13 |
Correct |
0 ms |
212 KB |
Output is correct |
14 |
Correct |
0 ms |
212 KB |
Output is correct |
15 |
Correct |
7 ms |
724 KB |
Output is correct |
16 |
Correct |
0 ms |
212 KB |
Output is correct |
17 |
Correct |
0 ms |
212 KB |
Output is correct |
18 |
Correct |
1 ms |
468 KB |
Output is correct |
19 |
Correct |
0 ms |
212 KB |
Output is correct |
20 |
Correct |
1 ms |
340 KB |
Output is correct |
21 |
Correct |
17 ms |
1236 KB |
Output is correct |
22 |
Correct |
2 ms |
340 KB |
Output is correct |
23 |
Correct |
12 ms |
852 KB |
Output is correct |
24 |
Correct |
12 ms |
852 KB |
Output is correct |
25 |
Correct |
22 ms |
1172 KB |
Output is correct |
26 |
Correct |
23 ms |
1108 KB |
Output is correct |
27 |
Execution timed out |
3095 ms |
94464 KB |
Time limit exceeded |
28 |
Halted |
0 ms |
0 KB |
- |