Submission #496108

#	Time	Username	Problem	Language	Result	Execution time	Memory
496108		Half	Keys (IOI21_keys)	C++17	20 / 100	3094 ms	24812 KiB

keys

#include <vector>
#include "keys.h"

#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;
typedef long double ld;
#define REP(i,a,b) for(ll i=(ll) a; i<(ll) b; i++)
#define pb push_back
#define mp make_pair
#define pl pair<ll,ll>
#define ff first
#define ss second
#define whole(x) x.begin(),x.end()
#define DEBUG(i) cout<<"DEBUG "<<i<<endl
#define INF 500000000LL
#define EPS 0.00000001
#define pi 3.14159
ll mod=1000000007LL;


std::vector<int> find_reachable(std::vector<int> r, std::vector<int> u, std::vector<int> v, std::vector<int> c) {
	int n = r.size(), m = u.size();
	vector<pair<int, int>> adj[n];
	for(int i = 0; i < m; i++){
		adj[u[i]].pb(mp(v[i], c[i]));
		adj[v[i]].pb(mp(u[i], c[i]));
	}
	int mn = n+1;
	vector<int> mnr;
	for(int i = 0; i < n; i++){
		queue<pair<pair<int, int>, int> > q;
		q.push(mp(mp(i, n), -1));
		bool visited[n];
		memset(visited, false, sizeof visited);
		bool keys[n+1];
		memset(keys, false, sizeof keys);
		keys[n] = true;
		int cnt = 0;
		while(!q.empty()){
			pair<pair<int, int>, int> nxt = q.front();
			q.pop();
			int j = nxt.ff.ff, ky = nxt.ff.ss, rnd = nxt.ss;
			if(visited[j])
				continue;
			if(rnd == cnt)
				break;
			if(!keys[ky]){
				q.push(mp(mp(j, ky), cnt));
				continue;
			}
			keys[r[j]] = true;
			visited[j] = true;
			for(auto adpr : adj[j])
				q.push(mp(adpr, cnt));
			cnt++;
		}
		if(cnt < mn){
			mn = cnt;
			mnr.clear();
			mnr.pb(i);
		}else if (cnt == mn){
			mnr.pb(i);
		}
	}

	std::vector<int> ans(r.size(), 0);
	for(auto i : mnr)
		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