Submission #1032781

#	Time	Username	Problem	Language	Result	Execution time	Memory
1032781		hotboy2703	Keys (IOI21_keys)	C++17	20 / 100	3057 ms	13340 KiB

keys

#include<bits/stdc++.h>
using ll = long long;
using namespace std;
#define pll pair <ll,ll>
#define fi first
#define se second
#define MP make_pair
#define sz(a) (ll((a).size()))
#define MASK(i) (1LL<<(i))
#define BIT(mask,i) (((mask) >> (i))&1)
// namespace brute{
	const ll MAXN = 3e5+100;
	bool in[MAXN];
	bool keys[MAXN];
	ll n;
	std::vector<int> find_reachable(std::vector<int> r, std::vector<int> u, std::vector<int> v, std::vector<int> c) {
		n = sz(r);
		ll m = sz(u);
		std::vector<int> ans(n);
		vector <ll> cnt(n);
		ll res = n;
		for (ll i = 0;i < n;i ++){
			for (ll j = 0;j < n;j ++)in[j] = 0,keys[j] = 0;
			in[i] = 1;
			keys[r[i]] = 1;
			cnt[i] = 1;
			while (true){
				ll pre = cnt[i];
				for (ll j = 0;j < m;j ++){
					if (in[u[j]] && keys[c[j]] && !in[v[j]])cnt[i]++,in[v[j]] = 1,keys[r[v[j]]] = 1;
					if (in[v[j]] && keys[c[j]] && !in[u[j]])cnt[i]++,in[u[j]] = 1,keys[r[u[j]]] = 1;
				}
				if (cnt[i]==pre)break;
			}
			res = min(res,cnt[i]);
		}
		for (ll i = 0;i < n;i ++)if (cnt[i] == res)ans[i] = 1;
		return ans;
	}
// }

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