Submission #1245099

#	Time	Username	Problem	Language	Result	Execution time	Memory
1245099		nicolo_010	Keys (IOI21_keys)	C++20	37 / 100	3092 ms	24204 KiB

keys

#include <bits/stdc++.h>
#include "keys.h"
using namespace std;
using ll = long long;
#define rep(i, k, n) for (int i=k;i<n;i++)

struct DSU {
	vector<int> rank, parent;
	vector<int> contain;
	DSU(int n, int i) {
		rank.assign(n, 1);
		parent.resize(n);
		contain.assign(n, 0);
		contain[i] = 1;
		rep(i, 0, n) parent[i] = i;
	}

	int find(int n) {
		return (parent[n] == n ? n : parent[n] = find(parent[n]));
	}

	bool unite(int n1, int n2) {
		int p1 = find(n1), p2 = find(n2);
		if (p1 == p2) return false;
		if (rank[p1] > rank[p2]) {
			rank[p1] += rank[p2];
			parent[p2] = p1;
			contain[p1] |= contain[p2];
		}
		else {
			rank[p2] += rank[p1];
			parent[p1] = p2;
			contain[p2] |= contain[p1];
		}
		return true;
	}
};

vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c) {
	int n = r.size();
	int m = v.size();
	vector<int> ans(n);
	vector<int> sz(n, 1);
	vector<vector<pair<int, int>>> adj(n);
	rep(i, 0, m) {
		int a = u[i], b = v[i];
		adj[a].push_back({b, c[i]});
		adj[b].push_back({a, c[i]});
	}
	rep(i, 0, n) {
		vector<int> visc(n, 0);
		vector<bool> vis(n, false);
		queue<int> q;
		q.push(i);
		visc[r[i]] = true;
		vis[i] = true;
		vector<vector<int>> edges(n);
		int cnt = 0;
		while (!q.empty()) {
			int node = q.front();
			cnt++;
			q.pop();
			int un = r[node];
			//	cout << node << " " << un << endl;
			for (auto x : adj[node]) {
				int col = x.second;
				int vec = x.first;
				if (!vis[vec] && visc[col]) {
					vis[vec] = true;
					q.push(vec);
				}
				else if (!vis[vec]) {
					edges[col].push_back(vec);
				}
			}
			visc[un] = true;
			for (auto x : edges[un]) {
				if (!vis[x]) {
					vis[x] = true;
					q.push(x);
				}
			}
		}
		sz[i] = cnt;
	}
	int mn = 1e9;
	rep(i, 0, n) mn = min(mn, sz[i]);
	//rep(i, 0, n) cout << i << " "<< sz[i] << endl;
	rep(i, 0,  n) {
		if (sz[i] <= mn) ans[i] = 1;
		else ans[i] = 0;
	}
	return ans;
}

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