Submission #1066178

#	Time	Username	Problem	Language	Result	Execution time	Memory
1066178		epicci23	Keys (IOI21_keys)	C++17	37 / 100	3027 ms	71368 KiB

keys

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

const int N = 3e5 + 5;
vector<int> v[N],comp[N];
vector<array<int,2>> adj[N];
set<int> s[N];
bool vis[N],vis2[N],mark[N];
vector<int> cur,par(N,0);

void merge_info(int a,int b){
  a=par[a],b=par[b];
  if(a==b) return;
  if(sz(comp[a])<sz(comp[b])) swap(a,b);
  mark[a]&=mark[b];
  for(int x:v[b]) v[a].push_back(x);
  for(int x:comp[b]){
    comp[a].push_back(x);
    par[x]=a;
  }
  vector<array<int,2>> new_adj;
  for(int u:s[b]) s[a].insert(u);
  for(int i=0;i<sz(adj[a]);i++){
    int u=adj[a][i][0],c=adj[a][i][1];
    if(s[a].count(c)) v[a].push_back(u);
    else new_adj.push_back({u,c});
  }
  for(int i=0;i<sz(adj[b]);i++){
    int u=adj[b][i][0],c=adj[b][i][1];
    if(s[a].count(c)) v[a].push_back(u);
    else new_adj.push_back({u,c});
  }
  adj[b].clear();adj[a].clear();
  adj[a]=new_adj;
  v[b].clear();
  comp[b].clear();
  s[b].clear();
}

void dfs(int c){
  vis2[c]=vis[c]=1;
  cur.push_back(c);
  while(!v[par[c]].empty()){
    int x=v[par[c]].back();
    v[par[c]].pop_back();
    if(vis[x] && !vis2[x]){
      mark[par[c]]=0;
      continue;
    }
    if(vis[x]==1){
      while(!cur.empty() && par[cur.back()]!=par[x]){
        merge_info(cur.back(),x);
        cur.pop_back();
      }
    }
    else{
      dfs(x);
      if(par[c]!=par[x]) mark[par[c]]=0;
    }
  }
 if(!cur.empty() && cur.back()==c) cur.pop_back();
 vis2[c]=0;
}

vector<int> find_reachable(vector<int> R, vector<int> U, vector<int> V, vector<int> C){
  int n=sz(R),m=sz(U);
  iota(all(par),0);
  for(int i=0;i<n;i++) mark[i]=1;
  for(int i=0;i<n;i++) comp[i].push_back(i);
  for(int i=0;i<n;i++) s[i].insert(R[i]); 
  for(int i=0;i<m;i++){
    int a=U[i],b=V[i],c=C[i];
    if(s[a].count(c)) v[a].push_back(b);
    else adj[a].push_back({b,c});
    if(s[b].count(c)) v[b].push_back(a);
    else adj[b].push_back({a,c});
  }
  for(int i=0;i<n;i++) if(!vis[i]) dfs(i);
  int mini=100000007;
  for(int i=0;i<n;i++) if(mark[par[i]]) mini=min(mini,sz(comp[par[i]]));
  vector<int> ans(n,0);
  for(int i=0;i<n;i++) if(mark[par[i]] && sz(comp[par[i]])==mini) ans[i]=1;
  return ans;
}

/*void _(){
  int n,m;
  cin >> n >> m;
  iota(all(par),0);
  for(int i=0;i<n;i++) comp[i].push_back(i);
  vector<int> col(n);
  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].push_back(b);
    v[b][c].push_back(a);
  }
  for(int i=0;i<n;i++) if(vis[i]==0) dfs(i);
  int mini=100000007;
  for(int i=0;i<n;i++){
    if(mark[par[i]]) continue;
    mini=min(mini,sz(comp[par[i]]));
  }
  vector<int> ans(n,0);
  for(int i=0;i<n;i++) if(!mark[par[i]] && sz(comp[par[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: 9 / 9
• Subtask 2: 11 / 11
• Subtask 3: 17 / 17
• Subtask 4: 0 / 30
• Subtask 5: 0 / 33