| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 835711 | Mohmad_Zaid | 열쇠 (IOI21_keys) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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;
// }