제출 #1110119

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1110119		mychecksedad	열쇠 (IOI21_keys)	C++17	0 / 100	7 ms	23888 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;


struct Dsu {
	vector<int> s, p;
	int sz;
	Dsu(int n){
		sz = n;
		s.resize(n+1, 1);
		p.resize(n+1);
		for(int i = 0; i <= n; ++i) p[i] = i;
	}
	int find(int v){
		if(p[v] == v) return v;
		return (p[v] = find(p[v]));
	}
	void merge(int a, int b){
		a = find(a);
		b = find(b);
		if(a != b){
			s[b] += s[a];
			p[a] = b;
			sz--;
		}
	}
};


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;
  Dsu d(n);
  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[{d.find(u), d.find(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[{d.find(to), d.find(u)}]){
              vis[u] = 1;
              d.merge(u, to);
              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