# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
835713 |
2023-08-23T17:56:06 Z |
Mohmad_Zaid |
Keys (IOI21_keys) |
C++17 |
|
1 ms |
212 KB |
#include <bits/stdc++.h>
#define pb push_back
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<int> final(n, 1);
vector<vector<pair<int,int>>>g(n,vector<pair<int,int>>());
vector<int>sizes(n,0);
vector<bool>vis(n);
vector<bool>vis2(n);
vector<vector<int>>need(n,vector<int>());
set<int>keys;
for(int i=0;i<m;i++){
g[u[i]].pb({v[i],c[i]});
g[v[i]].pb({u[i],c[i]});
}
int mn=INT_MAX;
for(int i=0;i<n;i++){
vis.assign(n,0);
vis2.assign(n,0);
need.assign(n,vector<int>());
queue<int>q;
q.push(i);
while(!q.empty()){
int par=q.front();
vis[par]=1;
if(!vis2[r[par]]){
for(auto node:need[r[par]]){
q.push(node);
}
}
vis2[r[par]]=1;
q.pop();
for(auto node:g[i]){
if(vis[node.first])continue;
if(!vis2[node.second]){need[node.second].pb(node.first);continue;}
q.push(node.first);
}
}
for(int j=0;j<n;j++)sizes[i]+=vis[j];
mn=min(mn,sizes[i]);
}
for(int i=0;i<n;i++){
// cout<<"room: "<<i<<' '<<sizes[i]<<endl;
if(sizes[i]==mn)final[i]=1;
else final[i]=0;
}
return final;
}
// int main(){
// vector<int>test;
// vector<int>r={0, 1, 1, 2, 2, 1, 2},u={0, 0, 1, 1, 2, 3, 3, 4, 4, 5},
// v={1, 2, 2, 3, 3, 4, 5, 5, 6, 6},c={0, 0, 1, 0, 0, 1, 2, 0, 2, 1};
// test=find_reachable(r,u,v,c);
// for(int i=0;i<test.size();i++)cout<<test[i]<<' ';cout<<endl;
// return 0;
// }
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
6 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
6 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
6 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
6 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
6 |
Halted |
0 ms |
0 KB |
- |