| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 834758 | IS_Rushdi | 열쇠 (IOI21_keys) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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>()));
int mn = 1e9;
vector<int>tmp(n,0);
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]);
}
vector<vector<vector<int>>>zoro_is_gay=a;
for(int i = 0; i < n; i++){
vector<int>vis(n,-1);
queue<int>q;
set<int>keys;
q.push(i);
while(!q.empty()){
int node = q.front();
q.pop();
if(vis[node] == keys.size()) continue;
keys.insert(r[node]);
vis[node] = keys.size();
for(int key : keys){
while(a[node][key].size() > 0){
q.push(a[node][key].back());
a[node][key].pop_back();
}
}
}
for(int j = 0; j < n; j++){
// cout << vis[j] << ' ';
if(vis[j] != -1) tmp[i]++;
}
mn = min(mn,tmp[i]);
// cout << tmp[i] << endl;
a=zoro_is_gay;
}
for(int i = 0; i < n; i++){
if(tmp[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] << ' ';
}