Submission #1052944

#	Time	Username	Problem	Language	Result	Execution time	Memory
1052944		TahirAliyev	Keys (IOI21_keys)	C++17	37 / 100	118 ms	22476 KiB

keys

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, int>
#define all(v) v.begin(), v.end()
#define oo 1e9

const int MAX = 2002;
vector<pii> E[MAX];
bool used[MAX];
int k[MAX];
int n, m;

struct DSU{
	int par[MAX];
	vector<int> s[MAX];
	void init(){
		memset(par, -1, sizeof(par));
		for(int i = 0; i < n; i++){
			s[i].clear();
			s[i].push_back(k[i]);
		} 
	}
	int get(int u){
		if(par[u] < 0) return u;
		return par[u] = get(par[u]);
	}
	bool unite(int u, int v){
		u = get(u), v = get(v);
		if(u == v) return 0;
		if(-par[u] < -par[v]) swap(u, v);
		par[u] += par[v];
		par[v] = u;
		if(s[u].size() < s[v].size()) swap(s[u], s[v]);
		for(int a : s[v]) s[u].push_back(a);
		return 1;
	}
};

DSU dsu;

vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c) {
	n = r.size(), m = u.size();
	for(int i = 0; i < m; i++){
		E[c[i]].push_back({u[i], v[i]});
	}
	for(int i = 0; i < n; i++) k[i] = r[i];
	int mn = oo;
	vector<int> ans;
	for(int i = 0; i < n; i++){
		for(int j = 0; j < n; j++) used[j] = 0;
		dsu.init();
		while(dsu.s[dsu.get(i)].size()){
			int j = dsu.get(i);
			vector<pii> v;
			for(int a : dsu.s[j]){
				if(!used[a]){
					for(pii e : E[a]){
						v.push_back(e);
					}
					used[a] = 1;
				}
			}
			dsu.s[j].clear();
			for(pii e : v){
				dsu.unite(e.first, e.second);
			}
		}
		int cs = -dsu.par[dsu.get(i)]; 
		if(mn > cs){
			mn = cs;
			ans.clear();
		} 
		if(mn == cs) ans.push_back(i);
	}
	vector<int> res(n, 0);
	for(int a : ans) res[a] = 1;
	return res;
}

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