제출 #1002559

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1002559		ZeroCool	열쇠 (IOI21_keys)	C++17	37 / 100	83 ms	21076 KiB

keys

#include <vector>
#include <bits/stdc++.h>
using namespace std;

const int N = 2005;
#define ar array
vector<ar<int, 2>> g[N];

int n;

int A[N];

int bfs(int x){
	vector<int> v[n];
	bitset<N> vis, has;
	queue<int>q;
	q.push(x);
	vis[x] = 1;
	int cnt = 0;
	
	while(q.size()){
		int x = q.front();
		q.pop();
		cnt++;
		if(!has[A[x]]){
			has[A[x]] = 1;
			for(auto u: v[A[x]]){
				if(!vis[u]){
					q.push(u);
					vis[u] = 1;
				}
			}
		}
		for(auto [u, c]: g[x]){
			if(vis[u])continue;
			if(!has[c])v[c].push_back(u);
			else {
				q.push(u);
				vis[u] = 1;
			}
		}
	}

	return cnt;
}

vector<int> find_reachable(vector<int> r, vector<int> u,vector<int> v, vector<int> c) {
	n = r.size();
	int m = u.size();
	for(int i = 0;i < n;i++)A[i] = r[i];
	for(int i = 0;i < m;i++){
		g[u[i]].push_back({v[i], c[i]});
		g[v[i]].push_back({u[i], c[i]});
	}
	
	vector<int>res(n);
	for(int i =0 ;i < n;i++)res[i] = bfs(i);
	int mn = *min_element(res.begin(), res.end());
	for(int i = 0;i < n;i++)res[i] = res[i] == mn;
	
	return res;
}

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