제출 #1179380

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1179380		hyakup	열쇠 (IOI21_keys)	C++20	37 / 100	68 ms	8260 KiB

keys

#include <bits/stdc++.h>
using namespace std;

const int maxn = 2e3 + 10;
vector<pair<int, int>> adj[maxn];


vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c) {
	int n = r.size(), m = u.size();
	for( int i = 0; i < m; i++ ){
		adj[u[i]].push_back({ v[i], c[i] });
		adj[v[i]].push_back({ u[i], c[i] });
	}

	int mini = n;
	vector<int> resp(n);

	auto bfs = [&]( int source ){
		vector<int> key(n), marc(n);
		vector<vector<int>> aux(n);

		queue<int> fila;
		marc[source] = true;
		fila.push(source);
		int cont = 0;

		while( !fila.empty() ){
			int cur = fila.front(); fila.pop();
			if( !key[r[cur]] ) for( int x : aux[r[cur]] ) if( !marc[x] ) fila.push(x), marc[x] = true;
			key[r[cur]] = true;

			cont++;
			for( auto [viz, id] : adj[cur] ) if( !marc[viz] ){
				if( key[id] ){ marc[viz] = true; fila.push(viz); }
				else aux[id].push_back(viz);
			}
		}

		return cont;
	};

	for( int i = 0; i < n; i++ ){
		int x = bfs(i);
		if( x < mini ){
			fill( resp.begin(), resp.end(), 0 );
			mini = x;
		}
		if( x == mini ) resp[i] = 1;
	}

	return resp;
}

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