Submission #599789

#	Time	Username	Problem	Language	Result	Execution time	Memory
599789		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 uNumber{
	int c; 
	uNumber(){c = 0;}
	int operator ()() {return c++;}
} UniqueN;

struct UF{
private:
public:
	vi ranki,p,sz;
	
	UF(int n){
		ranki.assign(n, 0);
		p.assign(n, 0);
		sz.assign(n,0);
		generate(p.begin(),p.end(),UniqueN);
	}
	
	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[y]+1;
				sz[y] = sz[x];
			}else{
				if(ranki[x] == ranki[y]) ranki[y]++;
				p[x] = y;
				sz[y] += sz[x]+1;
				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){
		ans.assign(n,1);
	}
	
	vector<vector<int>> g(n,vector<int>());
	UF unionfind(n);
	
	for(int i = 0; i < m; i++){
		g[u[i]].push_back(v[i]);
		g[v[i]].push_back(u[i]);
		
		unionfind.unionset(u[i],v[i]);
	}
	
	int mini = *min_element(unionfind.sz.begin(),unionfind.sz.end());
	
	for(int i = 0; i < n; i++){
		if(unionfind.sz[i] == 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