# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
827902 | Liudas | 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 "keys.h"
#include <cassert>
#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
#include <numeric>
#include <unordered_map>
#include <iostream>
using namespace std;
//DSU//
vector<int> par;
int find_par(int x){
if(par[x] != x){
par[x] = find_par(par[x]);
}
return par[x];
}
void merge(int a, int b){
par[find_par(a)] = find_par(b);
}
//DSU//
vector<int> VIS, keys;
vector<vector<pair<int, int>>> tree;
vector<vector<int>> locked;
vector<int> iter;
int ans = 1e9, it = 1;
vector<int> smol;
vector<int> been;
vector<bool> vis, got;
void clean(){
for(int i : been){
vis[i] = false;
got[keys[i]] = false;
locked[i].clear();
}
been.clear();
}
void BFS(int head){
queue<int> que;
que.push(head);
got[keys[head]] = true;
while(que.size()){
int a = que.front();
que.pop();
if(find_par(head) != find_par(a)){
merge(head, a);
iter[find_par(a)] = it;
clean();
return;
}
if(vis[a])continue;
vis[a] = true;
been.push_back(a);
int key = keys[a];
if(!got[key]){
got[key] = true;
for(int i : locked[key]){
if(!vis[i]){
que.push(i);
}
}
}
for(auto [l, r] : tree[a]){
if(got[r]){
que.push(l);
}
else{
locked[r].push_back(l);
}
}
}
VIS[head] = true;
int c = been.size();
if(ans > c){
ans = c;
smol.clear();
}
if(ans == c){
for(int i = 0; i < vis.size(); i ++){
if(vis[i]){
smol.push_back(i);
}
}
}
clean();
}
vector<int> find_reachable(vector<int> R, vector<int> U, vector<int> V, vector<int> C){
int N = R.size(), M = C.size();
locked.resize(N);
par.assign(N, 0);
VIS.assign(N, 0);
keys.resize(N);
tree.resize(N);
iter.assign(N, 0);
vis.assign(N, 0);
got.assign(N, 0);
for(int i = 0; i < N; i ++){
keys[i] = R[i];
}
iota(par.begin(), par.end(), 0);
for(int i = 0; i < M; i ++){
tree[U[i]].push_back({V[i], C[i]});
tree[V[i]].push_back({U[i], C[i]});
}
int check = 1;
while(check){
check = 0;
for(int i = 0; i < N; i ++){
if(find_par(i) == i && !VIS[i] && iter[i] != it){
BFS(i);
check = 1;
}
}
it ++;
}
vector<int> ret(N);
for(int i : smol){
ret[i] = 1;
}