Submission #1038083

#	Time	Username	Problem	Language	Result	Execution time	Memory
1038083		vjudge1	Keys (IOI21_keys)	C++17	37 / 100	68 ms	20820 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