# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1049645 | nisanduu | Keys (IOI21_keys) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <vector>
#include <bits/stdc++.h>
using namespace std;
ll dfs(ll node,vector<ll> vis,vector<vector<ll>> adj){
vis[node]=1;
int am = 1;
for(auto el:adj[node]){
if(!vis[node]){
am += dfs(el,vis,adj);
}
}
return am;
}
vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c) {
vector<int> ans(r.size(), 0);
int n = r.size();
int m = v.size();
vector<vector<ll>> adj(n+2);
for(ll i=0;i<m;i++){
adj[v[i]].push_back(u[i]);
adj[u[i]].push_back(v[i]);
}
int mini = 1e9;
int type = c[0];
for(int i=0;i<n;i++){
if(r[i]==type) {
vector<ll> vis(n+2);
ans[i] = dfs(i,vis,adj);
}else{
ans[i] = 1;
}
mini = min(mini,ans[i]);
}
for(int i=0;i<n;i++) ans[i] = ans[i]==mini ? 1 : 0;
return ans;
}