# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
817049 | vjudge1 | 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 <bits/stdc++.h>
#include "grader.cpp"
using namespace std;
#define pb push_back
#define mp make_pair
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
const int N = 5000;
vector<pii> G[N];
vector<pii> NG[N];
vector<int> find_reachable(vector <int> r, vector <int> u, vector <int> v, vector <int> c) {
int n = (int)r.size();
vi ans(n, 1), C(n, 0);
for (int i = 0; i < (int)u.size(); i++) {
G[u[i]].pb({v[i], c[i]});
G[v[i]].pb({u[i], c[i]});
}
for (int i = 0; i < n; i++) {
set <pii> wait;
vector<bool> vis(n, 0);
vector<bool> have(n, 0);
queue <int> q;
q.push(i);
while (!q.empty()) {
C[i]++;
int at = q.front();
q.pop();
have[r[at]] = 1;
for (auto next : G[at]) if (!vis[next.first]) {
if (have[next.second]) {
vis[next.first] = 1;
q.push(next.first);
} else {
wait.insert({next.second, next.first});
}
}
while (1) {
auto it = wait.lower_bound(make_pair(r[at], -1));
if (it != wait.end() && (*it).first == r[at]) {
if (!vis[(*it).second]) {
vis[(*it).second] = 1;
q.push((*it).second);
}
wait.erase(it);
} else {
break;
}
}
}
}
int mn = *min_element(C.begin(), C.end());
for (int i = 0; i < n; i++) {
if(C[i] == mn) ans[i] = 1;
else ans[i] = 0;
}
return ans;
}