| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1049654 | nisanduu | 열쇠 (IOI21_keys) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <vector>
#include <bits/stdc++.h>
using namespace std;
typedef int ll;
ll dfs(ll node,vector<ll> vis,vector<vector<ll>> adj){
if(vis[node]) return 0;
vis[node]=1;
int am = 1;
for(auto el:adj[node]){
if(!vis[el]){
//vis[el]=1;
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;
}
int main(){
vector<int> arr = find_reachable({0, 0, 0}, {0}, {1}, {0});
for(auto z:arr) cout<<z<<" ";
return 1;
}