Submission #1014152

#	Time	Username	Problem	Language	Result	Execution time	Memory
1014152		shenfe1	Keys (IOI21_keys)	C++17	37 / 100	169 ms	88504 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];
bool ban[MAX];
bool out[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();
}


void solve(){
  mem(MR,0);
  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)){
          out[D.get(i)]=1;
          tov[D.get(i)]=D.get(to.F);
          // if(ban[D.get(to.F)]){
          //   ban[D.get(i)]=2;
          //   break;
          // }
          // cout<<i<<" "<<to.F<<"\n";
          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),D.get(V));
                // cout<<"!! "<<i<<" "<<V<<"\n";
                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)]){
      ban[D.get(i)]=1;
    }
  }
}

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]});
  }
  // {
  //   vector<int> res(n,0);
  //   int cnt=0;
  //   for(int i=1;i<=n;i++){
  //     bool ok=0;
  //     for(auto to:g[i]){
  //       if(to.S==r[i-1])ok=1;
  //     }
  //     if(!ok){
  //       cnt++;
  //       res[i-1]=1;
  //     }
  //   }
  //   if(cnt>0)return res;
  // }
  D.init(n);
  D1.init(n);
  for(int i=1;i<=n;i++){
    ver[i].pb(i);
    st[i].in(r[i-1]);
  }
  for(int i=1;i<=30;i++){
    solve();
  }
  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[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