Submission #1198564

#	Time	Username	Problem	Language	Result	Execution time	Memory
1198564		Nonoze	Keys (IOI21_keys)	C++20	37 / 100	3092 ms	21624 KiB

keys

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define sz(x) (int)x.size()
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define cmin(a,b) a=min(a,b)
#define cmax(a,b) a=max(a,b)

int n, m;

vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c) {
	n=sz(r), m=sz(u);
	vector<vector<pair<int, int>>> vec(n);
	for (int i=0; i<m; i++) vec[c[i]].pb({u[i], v[i]});

	vector<int> p;
	int mini=n;
	for (int i=0; i<n; i++) {
		vector<vector<int>> adj(n);
		vector<bool> reachable(n, 0); reachable[i]=1;
		vector<bool> already(n, 0);
		queue<int> q; q.push(i);
		while (!q.empty()) {
			int u=q.front(); q.pop();
			if (!already[r[u]]) {
				already[r[u]]=1;
				for (auto &[x, y]: vec[r[u]]) {
					if (reachable[x] && !reachable[y]) {
						reachable[y]=1;
						q.push(y);
					} else if (!reachable[x] && reachable[y]) {
						reachable[x]=1;
						q.push(x);
					} else if (!reachable[x] && !reachable[y]) {
						adj[x].pb(y);
						adj[y].pb(x);
					}
				}
			}
			for (auto &v: adj[u]) {
				if (!reachable[v]) {
					reachable[v]=1;
					q.push(v);
				}
			}
		}
		int nb=0; for (int j=0; j<n; j++) nb+=reachable[j];
		p.pb(nb);
		cmin(mini, nb);
	}

	vector<int> ans(n, 0);
	for (int i=0; i<n; i++) ans[i]=(p[i]==mini);


	return ans;
}

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