Submission #1064971

#	Time	Username	Problem	Language	Result	Execution time	Memory
1064971		epicci23	Keys (IOI21_keys)	C++17	0 / 100	16 ms	35676 KiB

keys

#include "bits/stdc++.h"
//#define int long long
#define all(v) v.begin() , v.end()
#define sz(a) (int)a.size()
using namespace std;

const int N = 3e5 + 5;
map<int,set<int>> v[N];
set<int> s[N];
vector<int> topo,vis(N,0),col(N),par(N),mark(N);
vector<array<int,3>> geri_ekle;
struct DSU{
  vector<int> par,siz;
  DSU(int n){
    par.resize(n);
    siz.assign(n,1);
    iota(all(par),0);
  }
  int find(int a){
    if(par[a]==a) return a;
    return par[a]=find(par[a]);
  }
  void unite(int a,int b){
    a=find(a),b=find(b);
    if(a==b) return;
    if(siz[a]<siz[b]) swap(a,b);
    par[b]=a;
    siz[a]+=siz[b];
  }
}; 

DSU dsu(N);

void merge_info(int a,int b){
  a=dsu.find(a),b=dsu.find(b);
  if(a==b) return;
  dsu.unite(a,b);
  if(sz(s[a])<sz(s[b])) swap(s[a],s[b]);
  for(int u:s[b]) s[a].insert(u);
  int sA=0,sB=0;
  for(auto x:v[a]) sA+=sz(x.second);
  for(auto x:v[b]) sB+=sz(x.second);
  if(sA<sB) swap(v[a],v[b]);
  for(auto x:v[b]) for(int u:x.second) v[a][x.first].insert(u);
  int u=dsu.find(a);
  if(u!=a){
    swap(s[a],s[u]);
    swap(v[a],v[u]);
  }
}

void topo_sort(int c){
  if(vis[c]) return;
  vis[c]=1;
  for(int x:v[c][col[c]]) topo_sort(x);
  topo.push_back(c);
}

void dfs(int c){
  c=dsu.find(c);
  if(vis[c]==2) return;
  //cout << "vardim: " << c << '\n';
  vis[c]=1;
  vector<int> go;
  vector<array<int,2>> sil;
  for(int u:s[c]){
   for(int x:v[c][u]){
    x=dsu.find(x);
    if(vis[x]==2 || x==c) continue;
    if(vis[x]==1){
      int d=dsu.find(c);
      while(d!=x){
        //cout << "Mergele\n";
        //cout << par[d] << ' ' << d << '\n';
        dsu.unite(par[d],d);
        merge_info(par[d],d);
        d=par[d];
      }
    }
    else{
     par[x]=c;
     sil.push_back({u,x});
     geri_ekle.push_back({c,x,u});
     go.push_back(x);
    } 
   }
 }
 for(auto x:sil) v[c][x[0]].erase(x[1]);
 for(int x:go) dfs(x);
 vis[c]=2;
}

void check(int c){
  c=dsu.find(c);
  if(vis[c]) return;
  vis[c]=1;
  //cout << "bakcaz: " << c << '\n';
  for(int u:s[c]){
   for(int x:v[c][u]){
    x=dsu.find(x);
    //cout << c << " " << x << '\n';
    if(x!=c) mark[c]=1;
   }
 }
}

vector<int> find_reachable(vector<int> R, vector<int> U, vector<int> V, vector<int> C){
  int n=sz(R),m=sz(U);
  for(int i=0;i<n;i++) col[i]=R[i];
  for(int i=0;i<n;i++) s[i].insert(col[i]); 
  for(int i=0;i<m;i++){
    int a=U[i],b=V[i],c=C[i];
    v[a][c].insert(b);
    v[b][c].insert(a);
  }
  for(int i=0;i<n;i++) topo_sort(i);
  reverse(all(topo));
  vis.assign(N,0);
  for(int x:topo) dfs(x);
  vis.assign(N,0);
  for(auto x:geri_ekle){
    int a=x[0],b=x[1],c=x[2];
    v[a][c].insert(b);
    v[b][c].insert(a);
  }
  for(int x:topo) check(x);
  int mini=100000007;
  for(int i=0;i<n;i++){
    if(mark[dsu.find(i)]) continue;
    mini=min(mini,dsu.siz[dsu.find(i)]);
  }
  vector<int> ans(n,0);
  for(int i=0;i<n;i++) if(!mark[dsu.find(i)] && dsu.siz[dsu.find(i)]==mini) ans[i]=1;
  return ans;
}


/*void _(){
  int n,m;
  cin >> n >> m;
  for(int i=0;i<n;i++) cin >> col[i];
  for(int i=0;i<n;i++) s[i].insert(col[i]);	
  for(int i=0;i<m;i++){
  	int a,b,c;
  	cin >> a >> b >> c;
  	v[a][c].insert(b);
  	v[b][c].insert(a);
  }
   
  for(int i=0;i<n;i++) topo_sort(i);
  reverse(all(topo));
  vis.assign(N,0);
  for(int x:topo) dfs(x);
  vis.assign(N,0);
  for(auto x:geri_ekle){
    int a=x[0],b=x[1],c=x[2];
    v[a][c].insert(b);
    v[b][c].insert(a);
  }
  for(int x:topo) check(x);
  int mini=100000007;
  for(int i=0;i<n;i++){
    if(mark[dsu.find(i)]) continue;
    mini=min(mini,dsu.siz[dsu.find(i)]);
  }
  vector<int> ans(n,0);
  for(int i=0;i<n;i++) if(!mark[dsu.find(i)] && dsu.siz[dsu.find(i)]==mini) ans[i]=1;
  for(int i=0;i<n;i++) cout << ans[i] << " \n"[i==n-1];
}      

int32_t main(){
  cin.tie(0); ios::sync_with_stdio(0);
  int tc=1;//cin >> tc;
  while(tc--) _();
  return 0;
}*/

• Subtask 1: 0 / 9
• Subtask 2: 0 / 11
• Subtask 3: 0 / 17
• Subtask 4: 0 / 30
• Subtask 5: 0 / 33