Submission #1014157

#	Time	Username	Problem	Language	Result	Execution time	Memory
1014157		shenfe1	Keys (IOI21_keys)	C++17	37 / 100	3022 ms	55868 KiB

keys

#include <bits/stdc++.h>

#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];
set<int> st[MAX];
vector<int> ver[MAX];
int ban[MAX];
bool MR[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 a,int b){
  if(sz(st[a])<sz(st[b]))swap(st[a],st[b]);
  for(int x:st[b])st[a].in(x);
  st[b].clear();
  if(sz(ver[a])<sz(ver[b])){
    swap(ver[a],ver[b]);
  }
  for(int x:ver[b])ver[a].pb(x);
  ver[b].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]});
  }
  D.init(n);
  D1.init(n);
  for(int i=1;i<=n;i++){
    ver[i].pb(i);
    st[i].in(r[i-1]);
  }
  while(1){
    mem(MR,0);
    int cnt=0;
    // cerr<<1<<"\n";
    for(int i=1;i<=n;i++){
      if(ban[D.get(i)])continue;
      if(!tov[D.get(i)]){
        for(auto to:g[i]){
          if(D.get(i)!=D.get(to.F)&&st[D.get(i)].count(to.S)){
            if(ban[D.get(to.F)]){
              ban[D.get(i)]=2;
              break;
            }
            tov[D.get(i)]=D.get(to.F);
            cnt++;
            if(D1.get(i)==D1.get(to.F)){
              tov[D.get(i)]=0;
              MR[D.get(i)]=1;
              {
                int V=D.get(to.F);
                while(D.get(V)!=D.get(i)){
                  mrg(D.get(i),V);
                  D.unite(i,V);
                  int TO=D.get(tov[V]);
                  tov[V]=0;
                  V=TO;
                }
              }
            }
            else{
              D1.unite(i,to.F);
              break;
            }
          }
        }
      }
    }
    for(int i=1;i<=n;i++){
      if(ban[D.get(i)])continue;
      if(tov[D.get(i)]==0&&!MR[D.get(i)]){
        // cout<<D.get(i)<<"\n";
        ban[D.get(i)]=1;
      }
    }
    if(!cnt)break;
  }
  // return vector<int>(n,0);
  int ans=inf;
  for(int i=1;i<=n;i++){
    if(D.get(i)==i){
      // cout<<ban[i]<<" ";
      if(ban[i]==1){
        ans=min(ans,D.s[i]);
      }
    }
  }
  // cout<<"\n";
  // cout<<ans<<"\n";
  vector<int> res(n,0);
  for(int i=1;i<=n;i++){
    if(ban[i]==1&&D.get(i)==i&&D.s[i]==ans){
      for(auto v:ver[i]){
        res[v-1]=1;
      }
      // cout<<"!! "<<i<<" "<<D.s[i]<<"\n";
    }
  }
  return res;
}

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