Submission #599806

#	Time	Username	Problem	Language	Result	Execution time	Memory
599806		tpiang	Keys (IOI21_keys)	C++17	0 / 100	1 ms	212 KiB

keys

#include <bits/stdc++.h>
#define vi vector<int>

using namespace std;

struct UF{
private:
public:
	vi ranki,p,sz;
	
	UF(int n){
		ranki.assign(n, 0);
		p.assign(n, 0);
		sz.assign(n,1);
		for(int i = 0; i < n; i++) p[i] = i;
	}
	
	int findset(int i){ return (p[i] == i) ? i : findset(p[i]);}
	bool issameset(int i, int j) {return findset(i) == findset(j);}
	
	void unionset(int i, int j){
		if(!issameset(i,j)){
			int x = findset(i), y = findset(j);
			
			if(ranki[x] > ranki[y]){
				p[y] = x;
				sz[x] = sz[x] + sz [y];
			}else{
				if(ranki[x] == ranki[y]) ranki[y]++;
				p[x] = y;
				sz[y] = sz[x] + sz [y];
			}
		}
	}
};

vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c) {
	int n = (int) r.size();
	int m = (int) c.size();
	
	vector<int> ans(n, 0);
	bool flag = false;
	
	for(int i = 0; i < n; i++){
		if(r[i] != 0){
			ans[i] = 1;
			flag = true;
		}
	}
	if(flag){
		return ans;
	}
	
	UF unionfind(n);
	
	for(int i = 0; i < m; i++){		
		unionfind.unionset(u[i],v[i]);
	}
	
	int mini = 10000;
	
	
	for(int i = 0; i < n; i++){
		int x = unionfind.findset(i);
		mini = min(mini, unionfind.sz[x]);
	}
	
	for(int i = 0; i < n; i++){
		int x = unionfind.findset(i);
		if(unionfind.sz[x] == mini){
			ans[i] = 1;
		}
	}
	
	return ans;
}

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