| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 435410 | Muhammetali | 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>
#define mp make_pair
#define ff first
#define ss second
#define sz(x) (ll)(x).size()
#define all(x) x.begin(),x.end()
#define all_r(x) x.rbegin(),x.rend()
#define clr(a) memset((a),0,sizeof(a))
#define rsz resize
#define ins insert
#define ft front()
#define bk back()
#define pf push_front
#define pb push_back
#define eb emplace_back
#define lb lower_bound
#define ub upper_bound
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pi;
typedef pair<ll,ll> pl;
typedef vector<ll> vi;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef priority_queue<ll,vl,greater<ll>> pqg;
int R[300000];
vpi adj[300000];
set<int>st,key;
void find(int k){
st.ins(k);
key.ins(R[k]);
for(int i:st){
for(auto it:adj[i]){
if(st.count(it.ff)==1 || key.count(it.ss)==0)continue;
find(it.ff);
return;
}
}
}
vi find_reachable(vi r,vi u,vi v,vi c){
int n=sz(r);
int m=sz(v);
vi ans(n,1);
for(int i=0;i<n;i++)R[i]=r[i];
for(int i=0;i<m;i++){
adj[u[i]].pb({v[i],c[i]});
adj[v[i]].pb({u[i],c[i]});
}
int res=INT_MAX;
for(int i=0;i<n;i++){
st.clear();
key.clear();
bool vis=0;
for(auto it:adj[i]){
if(r[i]==it.ss && ans[it.ff]!=1){
vis=1;
ans[i]=ans[it.ff];
break;
}
}
if(!vis){
find(i);
ans[i]=sz(st);
}
if(res>ans[i])res=ans[i];
}
for(int i=0;i<n;i++){
if(ans[i]==res)ans[i]=1;
else ans[i]=0;
}
return ans;
}