| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 831754 | DJeniUp | 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>
#pragma GCC optimize("O3")
using namespace std;
typedef int ll;
typedef pair<ll,ll>pairll;
#define N 150007
#define pb push_back
#define fr first
#define sc second
vector<int> ans;
ll p[2*N],f[2*N],n,m,d[2*N],sz[2*N],fr[2*N];
map<ll,vector<ll> >v[2*N];
vector<ll>v2[2*N];
vector<pairll>v1[2*N];
set<ll>s[2*N],del[2*N],a[2*N];
ll P(ll x){
if(p[x]!=x)p[x]=P(p[x]);
return p[x];
}
void A(ll x,ll y){
if(P(x)==P(y))return ;
x=P(x);
y=P(y);
if(rand()%2)swap(x,y);
p[y]=x;
if(v2[x].size()<v2[y].size())swap(v2[x],v2[y]);
while(v2[y].size()>0){
v2[x].pb(v2[y].back());
v2[y].pop_back();
}
if(v1[x].size()<v1[y].size()){
swap(v1[x],v1[y]);
}
while(v1[y].size()>0){
v1[x].pb(v1[y].back());
v1[y].pop_back();
}
if(a[x].size()<a[y].size()){
swap(s[x],s[y]);
swap(v[x],v[y]);
swap(a[x],a[y]);
}
for(auto it:a[y]){
if(s[x].count(it)!=0){
while(v[y][it].size()>0){
v2[x].pb(v[y][it].back());
v[y][it].pop_back();
}
v[x][it].erase();
}else{
if(s[y].count(it)!=0){
while(v[x][it].size()>0){
v2[x].pb(v[x][it].back());
v[x][it].pop_back();
}
s[x].insert(it);
v[y][it].erase();
}else{
if(v[y][it].size()>v[x][it].size())swap(v[x][it],v[y][it]);
while(v[y][it].size()>0){
v[x][it].pb(v[y][it].back());
v[y][it].pop_back();
}
}
}
a[x].insert(it);
}
sz[x]+=sz[y];
return ;
}
ll S(ll x,ll y){
x=P(x);
//cout<<x<<" "<<y<<" "<<f[x]<<" "<<s[x].size()<<endl;
if(f[x]==2)return x;
if(f[x]==1)return 0;
//cout<<1<<endl;
f[x]=2;
while(v2[x].size()>0){
while(v2[x].size()>0){
ll m1=v2[x].back();
v2[x].pop_back();
if(P(m1)!=P(x)){
ll g=S(m1,x);
if(g!=0){
if(x==g){
break;
}else{
A(x,y);
return g;
}
}
}
}
x=P(x);
}
f[x]=1;
return 0;
}
vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> w, vector<int> c) {
n=r.size();
for(int i=1;i<=n;i++){
d[i]=r[i-1];
p[i]=i;
s[i].insert(d[i]);
sz[i]=1;
}
m=u.size();
for(int i=0;i<m;i++){
u[i]++;
w[i]++;
v[u[i]][c[i]].pb(w[i]);
v[w[i]][c[i]].pb(u[i]);
v1[u[i]].pb({c[i],w[i]});
v1[w[i]].pb({c[i],u[i]});
if(c[i]==d[u[i]]){
v2[u[i]].pb(w[i]);
}
if(c[i]==d[w[i]]){
v2[w[i]].pb(u[i]);
}
a[u[i]].insert(c[i]);
a[w[i]].insert(c[i]);
}
for(int i=1;i<=n;i++){
if(f[i]==0)S(i,i);
}
for(int i=1;i<=n;i++){
s[i].clear();
}
for(int i=1;i<=n;i++){
s[P(i)].insert(d[i]);
}
ll mn=n;
for(int i=1;i<=n;i++){
if(p[i]==i){
for(auto it:v1[i]){
if(s[i].count(it.fr)!=0 && P(it.sc)!=i)fr[i]=1;
}
if(fr[i]==0)mn=min(mn,sz[i]);
}
//cout<<i<<" "<<P(i)<<endl;
}
ans.resize(n);
for(int i=1;i<=n;i++){
if(fr[P(i)]==0 && sz[P(i)]==mn)ans[i-1]=1;
}
return ans;
}