Submission #599819

#	Time	Username	Problem	Language	Result	Execution time	Memory
599819		tpiang	Keys (IOI21_keys)	C++17	9 / 100	136 ms	20860 KiB

keys

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

using namespace std;

vector<vi> graph;
vi root;
vi sz;
int ro;

void dfs(int u){
	root[u] = ro;
	
	for(int v : graph[u]){
		if(root[v] == -1){
			dfs(v);
			sz[u] += sz[v];
		}
	}
}

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);
	root.assign(n,-1);
	graph.assign(n,vi());
	sz.assign(n,1);
	
	for(int i = 0; i < n; i++){
		if(r[i] != 0){
			ans[i] = 1;
		}
	}	
	
	for(int i = 0; i < m; i++){
		graph[u[i]].push_back(v[i]);
		graph[v[i]].push_back(u[i]);
	}
	
	for(int i = 0; i < n; i++){
		if(ans[i] == 1) root[i] = i;
		if(root[i] == -1 && ans[i] == 0){
			ro = i;
			
			dfs(i);
		}
	}
	
	int mini = 1000;
	
	for(int i = 0; i < n; i++){
		mini = min(mini, sz[root[i]]);
	}
	
	for(int i = 0; i < n; i++){
		if(sz[root[i]] == mini){
			ans[i] = 1;
		}
	}
	
	return ans;
}

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