제출 #1110116

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1110116		mychecksedad	열쇠 (IOI21_keys)	C++17	0 / 100	5 ms	23976 KiB

keys

/* Author : Mychecksdead  */
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define MOD (1000000000+7)
#define MOD1 (998244353)
#define pb push_back
#define all(x) x.begin(), x.end()
#define en cout << '\n'
#define ff first
#define ss second
#define pii pair<int,int>
#define vi vector<int>
const int N = 1e6+100, M = 1e5+10, K = 52, MX = 30;


vector<pii> g[N];
int n, m;
vector<int> find_reachable(vector<int> r, vi u, vi v, vi c){
  n = r.size();
  m = u.size();
  for(int i = 0; i < m; ++i){
    g[u[i]].pb({v[i], c[i]});
    g[v[i]].pb({u[i], c[i]});
  }
  mt19937 rng(2134343213);

  vector<int> arr(n);
  for(int i = 1; i <= n; ++i){
    arr[i-1] = i-1;
    swap(arr[i-1], arr[uniform_int_distribution<int>(0,i-1)(rng)]);
  }
  vector<int> vis(n), viss(n), sz(n);
  vi op(n);
  vector<vector<int>> Q(n);
  map<pii, bool> reach;
  for(int u: arr){
  	// cout << u << ' ';
    vi used;
    vi usedd;

    queue<int> q;
    q.push(u);
    viss[u] = 1;
    while(!q.empty()){
      int v = q.front();
      q.pop();
      sz[u]++;
      // cout << u << ' ' << v << '\n';
      reach[{u, v}] = 1;
      while(Q[r[v]].size()){
        int x = Q[r[v]].back(); Q[r[v]].pop_back();
        if(!viss[x])
	        q.push(x), viss[x] = 1;
      }
      used.pb(r[v]);
      usedd.pb(v);
      op[r[v]] = 1;
      bool ok = 1;
      for(auto [to, col]: g[v]){
      	// cout << u << ' ' << v << ' ' << to << ' ' << col << '\n';
        if(vis[to] != 0 && op[col]){
          ok = 0;
          if(vis[to] == 2){
            vis[u] = 2;
          }
          if(vis[to] == 1){
            if(reach[{to, u}]){
              vis[u] = 1;
              sz[u] = sz[to];
            }else{
              vis[u] = 2;
            }
          }
          break;
        }
        used.pb(col);
        if(op[col] && !viss[to]){
          viss[to] = 1;
          q.push(to);
        }else if(!viss[to]) Q[col].pb(to);
      }
      if(!ok) break;

    }
    if(vis[u] == 0) vis[u] = 1;
    // cout << u << ' ';
    // cout << sz[u] << ' ' << vis[u] << '\n';

    for(int x: used) Q[x].clear(), op[x] = 0;
    for(int x: usedd) viss[x] = 0;
  	used.clear();
  	usedd.clear();
  }
  int mn = n;
  for(int i = 0; i < n; ++i){
    if(vis[i] == 1) mn = min(mn, sz[i]);
  }
  vector<int> ans(n);
  for(int i = 1; i <= n; ++i){
    if(vis[i-1]==1 && sz[i-1]==mn) ans[i-1]=1;
  }
  return ans;
}

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