제출 #590946

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
590946		Lucpp	열쇠 (IOI21_keys)	C++17	67 / 100	1139 ms	2097152 KiB

keys

#include <bits/stdc++.h>
using namespace std;
const int INF = 1e8;

int n, maxC;
vector<int> par;
vector<int> sz;
vector<vector<list<int>>> g;
vector<vector<bool>> keys;
int find(int u){
	if(u == par[u]) return u;
	else return par[u] = find(par[u]);
}
void merge(int a, int b){
	a = find(a);
	b = find(b);
	if(a == b) return;
	par[b] = a;
	sz[a] += sz[b];
	for(int i = 0; i < maxC; i++) g[a][i].splice(g[a][i].begin(), g[b][i]);
	for(int i = 0; i < maxC; i++) if(keys[b][i]) keys[a][i] = true;
}

vector<int> state;
stack<int> st;

void dfs(int u){
	u = find(u);
	st.push(u);
	state[u] = 1;
	for(int i = 0; i < maxC; i++){
		if(!keys[u][i]) continue;
		while(!g[u][i].empty()){
			int v = g[u][i].back();
			g[u][i].pop_back();
			v = find(v);
			if(v == u) continue;
			if(state[v] == 0){
				dfs(v);
				if(u != find(u)) return;
				v = find(v);
			}
			if(state[v] == 1){
				int w;
				do
				{
					w = st.top();
					st.pop();
					merge(u, w);
				}while(w != v);
				dfs(u);
				return;
			}
			else{
				sz[u] = INF;
				state[u] = 2;
				return;
			}
		}
	}
	state[u] = 2;
}

vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c) {
	n = (int)r.size();
	maxC = 0;
	for(int i : r) maxC = max(maxC, i);
	for(int i : c) maxC = max(maxC, i);
	maxC++;
	par.resize(n);
	sz.assign(n, 1);
	for(int i = 0; i < n; i++) par[i] = i;
	g.assign(n, vector<list<int>>(maxC));
	for(int i = 0; i < (int)u.size(); i++){
		g[u[i]][c[i]].push_back(v[i]);
		g[v[i]][c[i]].push_back(u[i]);
	}
	keys.assign(n, vector<bool>(maxC));
	for(int i = 0; i < n; i++) keys[i][r[i]] = true;
	state.resize(n);
	for(int i = 0; i < n; i++){
		if(state[find(i)] == 0) dfs(i);
	}
	int best = INF;
	vector<int> good;
	for(int i = 0; i < n; i++){
		int j = find(i);
		if(sz[j] < best){
			best = sz[j];
			good.clear();
		}
		if(sz[j] == best) good.push_back(i);
	}
	vector<int> ans(n);
	for(int i : good) ans[i] = 1;
	return ans;
}

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