Submission #1243251

#	Time	Username	Problem	Language	Result	Execution time	Memory
1243251		guanex	Keys (IOI21_keys)	C++20	9 / 100	78 ms	19780 KiB

keys

#include <vector>
#include<bits/stdc++.h>

using namespace std;

int check(int no, vector<int> &key, vector<vector<pair<int, int>>> &ed){
	bool vis[2005];
	bool gotten[2005];
	memset(vis, 0,sizeof vis);
	memset(gotten, 0, sizeof gotten);
	gotten[key[no]] = 1;
	vis[no] = 1;
	map<int, vector<int>> m;
	int ans = 0;
	queue<int> q;
	q.push(no);
	while(!q.empty()){
		int no = q.front();
		q.pop();
		//cout << no << endl;
		ans++;
		for(auto e:ed[no]){
			if(gotten[e.second]){
				if(vis[e.first] == 0){
					vis[e.first] = 1;
					q.push(e.first);
				}
			}else
				m[e.second].push_back(e.first);
		}
		for(auto e:m[key[no]]){
			if(vis[e] == 0){
				vis[e] = 1;
				q.push(e);
			}
		}
		m[key[no]].clear();
	}
	return ans;
}

std::vector<int> find_reachable(std::vector<int> r, std::vector<int> u, std::vector<int> v, std::vector<int> c) {
	std::vector<int> cnt(r.size());
	int mn = 1000000;
	vector<vector<pair<int, int>>> ed(r.size());
	for(int i = 0; i < u.size(); ++i){
		ed[u[i]].push_back({v[i], c[i]});
		ed[v[i]].push_back({u[i], c[i]});
	}
	for(int i = 0; i < r.size(); ++i){
		cnt[i] = check(i, r, ed);
		mn = min(mn, cnt[i]);
	}
	vector<int> ans;
	for(auto e:cnt){
		if(e == mn)ans.push_back(1);
		else ans.push_back(0);
	}
	return ans;
}

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