Submission #1014291

#	Time	Username	Problem	Language	Result	Execution time	Memory
1014291		shenfe1	Keys (IOI21_keys)	C++17	100 / 100	499 ms	76288 KiB

keys

#include <bits/stdc++.h>

#pragma GCC optimize("Ofast")

#define ll long long
#define lb lower_bound
#define ub upper_bound
#define pii pair<int,int>
#define F first
#define S second
#define ld long double
#define pb push_back
#define all(v) v.begin(),v.end()
#define in insert
#define sz(s) (int)s.size()
// #define int ll
#define ppb pop_back
#define mem(a,i) memset(a,i,sizeof(a))

using namespace std;

const int MAX=3e5+15;
const int inf=1e9;
const int mod=1e9+7;

const int dx[4]={1,0,-1,0};
const int dy[4]={0,1,0,-1};

vector<pii> g[MAX];
int n,m;
int tov[MAX];
bool col[MAX];
vector<int> op[MAX];
vector<int> ver[MAX];
int ban[MAX];
bool bad[MAX];

struct DSU{
  int f[MAX];
  int s[MAX];

  void init(int n){
    for(int i=1;i<=n;i++)f[i]=i,s[i]=1;
  }

  int get(int v){
    return (f[v]==v?v:f[v]=get(f[v]));
  }

  void unite(int u,int v){
    u=get(u);
    v=get(v);
    f[v]=u;
    s[u]+=s[v];
  }
}D,D1;

void mrg(int u,int v){
  u=D.get(u);
  v=D.get(v);
  if(sz(ver[u])<sz(ver[v]))swap(ver[u],ver[v]);
  for(int x:ver[v])ver[u].pb(x);
  ver[v].clear();
}

vector<int> find_reachable(vector<int> r,vector<int> u,vector<int> v,vector<int> c){
  n=sz(r);
  m=sz(u);
  for(int i=0;i<m;i++){
    u[i]++;
    v[i]++;
    g[u[i]].pb({v[i],c[i]});
    g[v[i]].pb({u[i],c[i]});
  }
  for(int i=1;i<=n;i++)ver[i].pb(i);
  D.init(n);
  D1.init(n);
  vector<int> comp;
  for(int i=1;i<=n;i++)comp.pb(i);
  for(int X=0;X<=20;X++){
    for(int x:comp)bad[x]=0;
    for(int x:comp){
      queue<int> q;
      for(int to:ver[x]){
        q.push(to);
      }
      vector<int> colors;
      while(!q.empty()&&!tov[x]){
        int v=q.front();
        q.pop();
        colors.pb(r[v-1]);
        col[r[v-1]]=1;
        for(auto to:g[v]){
          if(D.get(to.F)==D.get(v)){
            continue;
          }
          else{
            if(col[to.S]){
              bad[x]=1;
              if(D1.get(D.get(v))!=D1.get(D.get(to.F))){
                tov[x]=D.get(to.F);
                D1.unite(D.get(v),D.get(to.F));
                break;
              }
              else{
                int V=D.get(to.F);
                while(V!=x){
                  q.push(V);
                  mrg(x,V);
                  D.unite(x,V);
                  V=D.get(tov[V]);
                }
              }
            }
            else{
              colors.pb(to.S);
              op[to.S].pb(to.F);
            }
          }
        }
        if(tov[x])break;
        for(auto to:op[r[v-1]]){
          if(D.get(to)==D.get(v)){
            continue;
          }
          bad[x]=1;
          if(D1.get(D.get(v))!=D1.get(D.get(to))){
            tov[x]=D.get(to);
            D1.unite(D.get(v),D.get(to));
            break;
          }
          else{
            int V=D.get(to);
            // cerr<<v<<" "<<to<<" "<<r[v-1]<<"\n";
            while(V!=x){
              // cerr<<x<<" "<<V<<" "<<tov[V]<<"\n";
              q.push(V);
              mrg(x,V);
              D.unite(x,V);
              V=D.get(tov[V]);
            }
          }
        }
        op[r[v-1]].clear();
      }
      for(int f:colors){
        col[f]=0;
        op[f].clear();
      }
    }
    vector<int> ncomp;
    for(int x:comp){
      if(tov[x]==0){
        if(!bad[x])ban[x]=1;
        else ncomp.pb(x);
      }
    }
    comp=ncomp;
  }
  int ans=inf;
  for(int i=1;i<=n;i++){
    if(D.get(i)==i){
      if(ban[i]==1){
        ans=min(ans,D.s[i]);
      }
    }
  }
  vector<int> res(n,0);
  for(int i=1;i<=n;i++){
    if(ban[D.get(i)]==1&&D.s[D.get(i)]==ans){
      res[i-1]=1;
    }
  }
  return res;
}

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