Submission #1059405

#	Time	Username	Problem	Language	Result	Execution time	Memory
1059405		Trent	Keys (IOI21_keys)	C++17	37 / 100	3043 ms	26264 KiB

keys

#include "bits/stdc++.h"
using namespace std;
#define forR(i, x) for(int i = 0; i < (x); ++i)
#define REP(i, a, b) for(int i = (a); i < (b); ++i)
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<bool> vb;
typedef set<int> si;
struct pii{int a, b;};

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();
	int k = 1;
	forR(i, m) k = max(k, c[i] + 1);
	forR(i, n) k = max(k, r[i] + 1);
	vector<vector<pii>> adj(n);
	forR(i, m) {
		adj[u[i]].push_back({v[i], c[i]});
		adj[v[i]].push_back({u[i], c[i]});
	}
	vi cnt(n);
	forR(i, n) {
		vvi canGo(k);
		vb kFound(k), vis(n);
		vi dfs = {i};
		while(!dfs.empty()) {
			int cur = dfs.back(); dfs.pop_back();
			if(!kFound[r[cur]]) {
				for(int j : canGo[r[cur]]) if(!vis[j]) dfs.push_back(j);
				canGo[r[cur]].clear();
				kFound[r[cur]] = true;
			} else assert(canGo[r[cur]].empty());
			if(!vis[cur]){
				vis[cur] = true;
				for(auto [to, col] : adj[cur]) {
					if(!vis[to]) {
						if(kFound[col]) dfs.push_back(to);
						else canGo[col].push_back(to);
					}
				}
			}
		}
		forR(j, n) if(vis[j]) ++cnt[i];
	}

	int mi = cnt[0];
	forR(i, n) mi = min(mi, cnt[i]);
	vi ans(n);
	forR(i, n) ans[i] = cnt[i] == mi ? 1 : 0;
	return ans;
}

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