Submission #813579

#	Time	Username	Problem	Language	Result	Execution time	Memory
813579		Username4132	Keys (IOI21_keys)	C++17	37 / 100	75 ms	20936 KiB

keys

#include <iostream>
#include <vector>
#include<algorithm>
#include<cassert>
using namespace std;
using pii = pair<int, int>;
using ll = long long;
#define forn(i, n) for(int i=0; i<(int)n; ++i)
#define forsn(i, s, n) for(int i=s; i<(int)n; ++i)
#define dforn(i, n) for(int i=n-1; i>=0; --i)
#define dforsn(i, s, n) for(int i=n-1; i>=s; --i)
#define PB push_back
#define F first
#define S second


const int MAXN = 2010;
int n, m, ke[MAXN], res[MAXN];
bool av[MAXN], vis[MAXN];
vector<pii> g[MAXN];
vector<int> unused;
vector<int> toVis[MAXN];

void dfs(int v){
	vis[v]=true;
	if(!av[ke[v]]){
		av[ke[v]]=true;
		unused.PB(ke[v]);
	}
	for(pii to:g[v]) if(!vis[to.F]){
		if(av[to.S]) dfs(to.F);
		else toVis[to.S].PB(to.F);
	}
}


std::vector<int> find_reachable(std::vector<int> r, std::vector<int> u, std::vector<int> v, std::vector<int> c) {
	n = (int)r.size();
	m = (int)u.size();
	forn(i, n) ke[i]=r[i];
	
	forn(i, m){
		g[u[i]].PB({v[i], c[i]});
		g[v[i]].PB({u[i], c[i]});
	}
	
	forn(i, n){
		forn(j, n) av[j]=vis[j]=false;
		unused.clear();
		forn(j, n) toVis[j].clear();

		av[ke[i]]=true;
		unused.PB(ke[i]);
		toVis[ke[i]].PB(i);

		while(!unused.empty()){
			vector<int> nw;
			swap(unused, nw);
			for(int col:nw) for(int ve:toVis[col]) if(!vis[ve]) dfs(ve);
		}

		forn(j, n) res[i]+=vis[j];
	}
	int mn = *min_element(res, res+n);	
	std::vector<int> ans(n);
	forn(i, n) ans[i]=(res[i]==mn);
	return ans;
}

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