Submission #1055407

#	Time	Username	Problem	Language	Result	Execution time	Memory
1055407		mariaclara	Keys (IOI21_keys)	C++17	37 / 100	3051 ms	27420 KiB

keys

#include <vector>
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define mk make_pair
#define pb push_back
#define fr first
#define sc second

int n;
vector<vector<pii>> type_edges;
vector<vector<int>> edges;
vector<int> key;

int bfs(int ini) {
	vector<bool> vis(n,0), ad_key(n,0);
	queue<int> fila;
	fila.push(ini);
	edges.resize(n);
	vis[ini] = 1;

	int cnt = 0;
	while(!fila.empty()) {
		int x = fila.front();
		fila.pop();
		cnt++;
		
		if(!ad_key[key[x]]) {
			ad_key[key[x]] = 1;
			for(auto [a,b] : type_edges[key[x]]) {
				edges[a].pb(b);
				edges[b].pb(a);
				if(vis[a] and !vis[b]) fila.push(b), vis[b] = 1;
				if(vis[b] and !vis[a]) fila.push(a), vis[a] = 1;
			}
		}

		for(int viz : edges[x])
			if(!vis[viz]) vis[viz] = 1, fila.push(viz);
	}
	
	edges.clear();

	return cnt;
}

vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c) {
	n = sz(r);
	key = r;
	type_edges.resize(n);
	vector<int> ans(n);

	for(int i = 0; i < sz(u); i++) 
		type_edges[c[i]].pb({u[i],v[i]});

	int val = n;
	for(int i = 0; i < n; i++) {
		ans[i] = bfs(i);
		val = min(val, ans[i]);
	}

	for(int i = 0; i < n; i++)
		ans[i] = ans[i] == val;

	return ans;
}

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