제출 #1110325

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1110325		mychecksedad	열쇠 (IOI21_keys)	C++17	100 / 100	660 ms	96252 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){
			if(s[a] > s[b]) swap(a, b);
			s[b] += s[a];
			p[a] = b;
			sz--;
		}
	}
};


vector<pii> g[N];
int n, m;
vector<int> BLOCK[N];
bool is_key[N], vis[N];
int search(int root, vector<int> &is_root, int finish, vi &r){
	vi used_key, used_vis, used_block;
	queue<int> q;
	q.push(root);
	vis[root] = 1;
	used_vis.pb(root);
	int sz = 0;
	while(q.size()){
		int v = q.front(); q.pop();
		if(is_key[r[v]] == 0) used_key.pb(r[v]);
		is_key[r[v]] = 1;
		if(finish == 2) is_root[v] = 1;
		++sz;
		while(BLOCK[r[v]].size()){
			int u = BLOCK[r[v]].back(); BLOCK[r[v]].pop_back();
			if(vis[u] == false){
				vis[u] = true;
				used_vis.pb(u);
				q.push(u);
			}
		}
		for(auto [u, col]: g[v]){
			if(!vis[u]){
				if(is_key[col]){
					vis[u] = 1;
					used_vis.pb(u);
					q.push(u);
					if(finish && is_root[u]){
						for(int &x: used_block) BLOCK[x].clear();
						for(int &x: used_key) is_key[x] = 0;
						for(int &x: used_vis) vis[x] = 0;
						return u;
					}
				}else{
					BLOCK[col].pb(u);
					used_block.pb(col);
				}
			}
		}
	}
	for(int &x: used_block) BLOCK[x].clear();
	for(int &x: used_key) is_key[x] = 0;
	for(int &x: used_vis) vis[x] = 0;
	if(finish == 0) return sz;
	return -1;
}

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]});
  }


  
  for(int i = 0; i < n; ++i) is_key[i] = vis[i] = 0;
  Dsu d(n);
  vector<int> is_root(n, 1);
  bool OK = true;
  while(OK){
  	OK = false;
  	vector<pii> P;
  	for(int i = 0; i < n; ++i){
  		if(is_root[i]){
  			auto p = search(i, is_root, 1, r);
  			if(p != -1) P.pb({i, p});
  		}
  	}
  	for(auto [u, v]: P){
  		if(d.find(u) != d.find(v)){
	  		d.merge(u, v);
	  		is_root[u] = false;
	  		OK = true;
	  	}
  	}
  }
  int sz = n;
  vector<int> good(n), ans(n), SZ(n);
  for(int i = 0; i < n; ++i){
  	if(is_root[i]){
  		SZ[i] = search(i, is_root, 0, r);
  		sz = min(sz, SZ[i]);
  		good[d.find(i)] = 1;
  	}
  }

  for(int i = 0; i < n; ++i){
  	if(is_root[i]){
  		if(SZ[i] == sz){
  			search(i, ans, 2, r);
  		}
  	}
  }
  return ans;

}

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