| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1042509 | ProtonDecay314 | 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>
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pi;
typedef pair<ll, ll> pll;
typedef vector<pi> vpi;
typedef vector<pll> vpll;
typedef vector<vpi> vvpi;
typedef vector<vpll> vvpll;
typedef vector<bool> vb;
#define IOS ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
#define L(varll, mn, mx) for(ll varll = (mn); varll < (mx); varll++)
#define LR(varll, mx, mn) for(ll varll = (mx); varll > (mn); varll--)
#define LI(vari, mn, mx) for(int vari = (mn); vari < (mx); vari++)
#define LIR(vari, mx, mn) for(int vari = (mx); vari > (mn); vari--)
#define INPV(varvec) for(auto& varveci : (varvec)) cin >> varveci
#define fi first
#define se second
#define pb push_back
#define INF(type) numeric_limits<type>::max()
#define NINF(type) numeric_limits<type>::min()
#define TCASES int t; cin >> t; while(t--)
// class UF {
// public:
// int n;
// int ncomps;
// vi par;
// vi csize;
// UF(int a_n): n(a_n), ncomps(a_n), par(a_n, 0), csize(a_n, 1) {
// for(int i = 0; i < n; i++) par[i] = i;
// }
// int find(int i) {
// return (i == par[i] ? i : par[i] = find(par[i]));
// }
// int conn(int i, int j) {
// return find(i) == find(j);
// }
// void unify(int i, int j) {
// int pari = find(i), parj = find(j);
// if(pari == parj) return;
// if(csize[pari] < csize[parj]) {
// par[pari] = parj;
// csize[parj] += csize[pari];
// } else {
// par[parj] = pari;
// csize[pari] += csize[parj];
// }
// ncomps--;
// }
// }
vvpi cant_visit;
int bfs(int n, int m, int s, const vi& r, const vvpi& adj) {
int num = 0;
set<int> found_k;
set<int> vis(n, false);
queue<pi> q;
q.push({s, r[s]});
while(!q.empty()) {
auto [i, cr] = q.front();
q.pop();
if(vis[i]) continue;
vis[i] = true;
num++;
if(found_k.count(r[i]) == 0) {
while(cant_visit[r[i]].size() > 0) {
q.push(cant_visit[r[i]].back());
cant_visit[r[i]].pop_back();
}
found_k.insert(r[i]);
}
for(auto [j, c] : adj[i]) {
if(vis[j]) continue;
if(found_k.count(c) > 0) q.push({j, c});
else cant_visit[c].pb({j, c});
}
}
for(int k : found_k) {
cant_visit[k].clear();
}
return num;
}
vi find_reachable(vi r, vi u, vi v, vi c) {
int n = r.size(), m = u.size();
vi ans(n, 1);
vvpi adj;
for(int i = 0; i < n; i++) {
vpi adjr;
adj.pb(adjr);
}
for(int i = 0; i < n; i++) {
vpi cant_visitr;
cant_visit.pb(cant_visitr);
}
for(int i = 0; i < m; i++) {
adj[u[i]].pb({v[i], c[i]});
adj[v[i]].pb({u[i], c[i]});
}
int mn = INF(int);
for(int i = 0; i < n; i++) {
ans[i] = bfs(n, m, i, r, adj);
mn = min(mn, ans[i]);
}
for(int i = 0; i < n; i++) {
ans[i] = (ans[i] == mn ? 1 : 0);
}
return ans;
}