Submission #1053126

#	Time	Username	Problem	Language	Result	Execution time	Memory
1053126		epicci23	Keys (IOI21_keys)	C++17	9 / 100	3028 ms	58340 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;

struct DSU{
  vector<int> par,sub;
  DSU(int g){
  	par.assign(g+5,0);
    sub.assign(g+5,1);
    iota(all(par),0);
  }
  int find(int a){
  	if(par[a]==a) return a;
  	return par[a]=find(par[a]);
  }
  bool merge(int a,int b){
  	a=find(a),b=find(b);
  	if(a==b) return 0;
  	if(sub[a]>sub[b]) swap(a,b);
  	sub[b]+=sub[a];
  	par[a]=b;
  	return 1;
  }
};

DSU dsu(N);
int n,m;
bitset<30> col[N];
vector<array<int,3>> edges;
vector<int> v[N],v2[N];
vector<int> vis,topo,scc;

void build(){
  for(int i=0;i<n;i++) v[i].clear(),v2[i].clear();
  for(auto x:edges){
	if(col[x[0]][x[2]]){
	  //cout << "edge: " << x[0] << ' ' << x[1] << '\n';
      v[x[0]].push_back(x[1]);
      v2[x[1]].push_back(x[0]);
	}
	if(col[x[1]][x[2]]){
	  //cout << "edge: " << x[1] << ' ' << x[0] << '\n';
      v[x[1]].push_back(x[0]);
      v2[x[0]].push_back(x[1]);
	}
  }
}

void dfs(int c,int t){
  if(vis[c] || dsu.find(c)!=c) return;
  vis[c]=1;
  if(t){
   for(int x:v[c]) dfs(x,t);
   topo.push_back(c);
  }
  else{
   for(int x:v2[c]) dfs(x,t);
   scc.push_back(c);
  }
}

vector<vector<int>> find_scc(){
  topo.clear();
  vis.assign(n+5,0);
  for(int i=0;i<n;i++) dfs(i,1); 
  vector<vector<int>> res;
  vis.assign(n+5,0);
  reverse(all(topo));
  for(int x:topo){
    if(vis[x]) continue;
    scc.clear();
    dfs(x,0);
    res.push_back(scc);
  }
  return res;
}

vector<int> find_reachable(vector<int> r, vector<int> git, vector<int> gel, vector<int> renk) {
	vector<int> ans(sz(r),-1);
    n=sz(r),m=sz(git);
    for(int i=0;i<n;i++) col[i][r[i]]=1;
    for(int i=0;i<m;i++){
     int a=git[i],b=gel[i],c=renk[i];
     edges.push_back({a,b,c});  
    }

    while(1){
  	build();
  	auto res=find_scc();
  	bool ok=1;
  	for(vector<int> x:res) if(sz(x)>1) ok=0;
  	if(ok) break;
    for(vector<int> x:res){
      if(sz(x)==1) continue;
      int p=sz(x);
      for(int i=0;i<p-1;i++){
      	if(!dsu.merge(x[i],x.back())) continue;
        //if(sz(col[x[i]])>sz(col[x.back()])) swap(x[i],x[p-1]);
        col[x[p-1]]|=col[x[i]];	
      }
      if(dsu.find(x[p-1])!=x[p-1]) swap(col[x[p-1]],col[dsu.find(x[p-1])]);	
    }
    vector<array<int,3>> new_edges;
    for(auto x:edges){
      if(dsu.find(x[0])==dsu.find(x[1])) continue;
      new_edges.push_back({dsu.find(x[0]),dsu.find(x[1]),x[2]});
    }
    edges=new_edges;
  }

  int mini=(int)1e9+5;
  for(int i=0;i<n;i++){
  	if(!v[dsu.find(i)].empty()){
  	  ans[i]=0;
  	  continue;
  	}
  	mini=min(mini,dsu.sub[dsu.find(i)]);
  }
  for(int i=0;i<n;i++){
  	if(ans[i]!=-1) continue;
  	if(mini==dsu.sub[dsu.find(i)]) ans[i]=1;
  	else ans[i]=0;
  }

  return ans;
}


/*void _(){
  cin >> n >> m;
  for(int i=1;i<=n;i++){
  	int a;cin >> a;
  	col[i].insert(a);
  }
  for(int i=1;i<=m;i++){
    int a,b,c;
    cin >> a >> b >> c;
    edges.push_back({a,b,c});  
  }
   
  while(1){
  	build();
  	auto res=find_scc();
  	bool ok=1;
  	for(vector<int> x:res) if(sz(x)>1) ok=0;
  	if(ok) break;
    for(vector<int> x:res){
      if(sz(x)==1) continue;
      int p=sz(x);
      for(int i=0;i<p-1;i++){
      	if(!dsu.merge(x[i],x.back())) continue;
        if(sz(col[x[i]])>sz(col[x.back()])) swap(x[i],x[p-1]);
        for(int u:col[x[i]]) col[x[p-1]].insert(u);	
      }
      if(dsu.find(x[p-1])!=x[p-1]) swap(col[x[p-1]],col[dsu.find(x[p-1])]);	
    }
    vector<array<int,3>> new_edges;
    for(auto x:edges){
      if(dsu.find(x[0])==dsu.find(x[1])) continue;
      new_edges.push_back({dsu.find(x[0]),dsu.find(x[1]),x[2]});
    }
    edges=new_edges;
  }
  vector<int> ans(n+5,-1);
  int mini=(int)1e9+5;
  for(int i=1;i<=n;i++){
  	if(!v[dsu.find(i)].empty()){
  	  ans[i]=0;
  	  continue;
  	}
  	mini=min(mini,dsu.sub[dsu.find(i)]);
  }
  for(int i=1;i<=n;i++){
  	if(ans[i]!=-1) continue;
  	if(mini==dsu.sub[dsu.find(i)]) ans[i]=1;
  	else ans[i]=0;
  }

  for(int i=1;i<=n;i++) cout << ans[i] << " \n"[i==n];
}

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

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