Submission #1320279

#	Time	Username	Problem	Language	Result	Execution time	Memory
1320279		nikaa123	Keys (IOI21_keys)	C++20	67 / 100	3096 ms	55492 KiB

keys

#include <bits/stdc++.h>
using namespace std;

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

	vector <int> par(n);
	iota(par.begin(),par.end(),0);
	function<int(int)> getpar = [&](int x) {
		if (par[x] == x) return x;
		return par[x] = getpar(par[x]);
	};
	auto unionset = [&](int a, int b) {
		a = getpar(a);
		b = getpar(b);
		if (a == b) return;
		par[b] = a;
	};

	vector <vector<int>> aa;
	vector <int> dead(n,0);	
	vector <int> used(n,-1);
	vector <vector<int>> b(n);
	vector <int> t(n,-1);
	int mn = n+1;
	for (int i = 0; i < n; i++) {
		if (getpar(i) != i || dead[i] == 1) continue;

		vector <int> a;
		vector <int> usedk;
		queue <int> q;
		q.push(i);
		used[i] = i;
		usedk.emplace_back(r[i]);
		t[r[i]] = i;
		bool merged = 0;
		while (!q.empty()) {
			int f = q.front();
			q.pop();
			a.emplace_back(f);

			if (getpar(f) != i) {
				merged = 1;
				unionset(f,i);
				break;
			}

			if (t[r[f]] != i) {
				t[r[f]] = i;
				usedk.emplace_back(r[f]);
				for (auto res:b[r[f]]) {
					if (used[res]==i) continue;
					used[res] = i; 
					q.push(res);
				}
				b[r[f]].clear();
			}

			for (auto [to,k]:g[f]) {
				if (used[to] == i) continue;
				if (t[k] == i) {
					used[to] = i;
					q.push(to);
					continue;
				}
				if (b[k].empty()) usedk.emplace_back(k);
				b[k].emplace_back(to);
			}
		}

		for (auto k:usedk) b[k].clear();

		if (!merged) {
			dead[i] = 1;
			if (mn > a.size()) {
				aa = {a};
				mn = a.size();
			} else if (mn == a.size()) {
				aa.emplace_back(a);
			}
		}

	}


	vector<int> ans(n, 0);
	for (auto a:aa) {
		for (auto x:a) {
			ans[x] = 1;
		}
	}
	return ans;
}

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