Submission #829621

#	Time	Username	Problem	Language	Result	Execution time	Memory
829621		Abrar_Al_Samit	Keys (IOI21_keys)	C++17	37 / 100	192 ms	20940 KiB

keys

#include <bits/stdc++.h>
#include "keys.h"

using namespace std;

const int nax = 2000;

vector<pair<int,int>>g[nax];
vector<int>waiting[nax];
vector<int> find_reachable(vector<int> r, vector<int> u, 
	vector<int> v, vector<int> c) {

	int n = r.size(), m = u.size();
	for(int i=0; i<m; ++i) {
		g[u[i]].emplace_back(v[i], c[i]);
		g[v[i]].emplace_back(u[i], c[i]);
	}

	int cnt[n] = {0};
	for(int sc=0; sc<n; ++sc) {
		bool rc[n] = {0};
		rc[sc] = 1;

		bool key[n] = {0};
		key[r[sc]] = 1;

		for(int i=0; i<n; ++i) waiting[i].clear();

		vector<int>yet = {sc};

		while(!yet.empty()) {
			vector<int>new_yet, new_keys;
			for(int x : yet) {
				for(auto [to, type] : g[x]) if(!rc[to]) {
					if(key[type]) {
						rc[to] = 1;
						new_yet.push_back(to);
						if(!key[r[to]]) {
							key[r[to]] = 1;
							new_keys.push_back(r[to]);
						}
					} else {
						waiting[type].push_back(to);
					}
				}
			}
			yet = new_yet;

			for(int k : new_keys) {
				for(int v : waiting[k]) if(!rc[v]) {
					yet.push_back(v);
					key[r[v]] = 1;
					rc[v] = 1;
				}
				waiting[k].clear();
			}
		}
		for(int i=0; i<n; ++i) {
			cnt[sc] += rc[i];
		}
	}

	int mn = 1e9;
	for(int i=0; i<n; ++i) {
		mn = min(mn, cnt[i]);
	}

	vector<int>ret(n);
	for(int i=0; i<n; ++i) if(cnt[i]==mn) {
		ret[i] = 1;
	}
	return ret;
}

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