Submission #1320286

#	Time	Username	Problem	Language	Result	Execution time	Memory
1320286		nikaa123	Keys (IOI21_keys)	C++20	67 / 100	3095 ms	55532 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]);
	};

	vector <int> aa;
	vector <bool> dead(n,0);	
	vector <int> used(n,-1);
	vector <vector<int>> b(n);
	vector <int> t(n,-1);
	vector <int> a;
	vector <int> usedk;
	vector<int> skip(n,0);
	int mn = n+1;
	bool ok = 1;
	while (ok) {
		ok = 0;
		skip.assign(n,0);
		for (int i = 0; i < n; i++) {
		if (getpar(i) != i || dead[i] == 1 || skip[i] == 1) continue;
		ok = 1;

		a.clear();
		usedk.clear();
		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;
				par[i] = getpar(f);
				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()) {
				mn = a.size();
				aa = a;
			} else if (mn == a.size()) {
				for (auto x:a) {
					aa.emplace_back(x);
				}
			}
		}

	}
	}


	vector<int> ans(n, 0);
	for (auto x:aa) {
		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