Submission #1051611

#	Time	Username	Problem	Language	Result	Execution time	Memory
1051611		MarwenElarbi	Keys (IOI21_keys)	C++17	37 / 100	677 ms	17212 KiB

keys

#include <bits/stdc++.h>
using namespace std;
const int nax=2e3+5;
#define pb push_back
#define fi first
#define se second
vector<pair<int,int>> adj[nax];
set<int> colors;
vector<int> tab(nax);
set<pair<int,int>> to_do;
bool vis[nax];
int cnt=0;
void dfs(int x){
	if(vis[x]) return;
	vis[x]=true;
	if(!colors.count(tab[x])){
		colors.insert(tab[x]);
		while(true){
			auto cur=to_do.lower_bound({tab[x],0});
			if(cur!=to_do.end()&&cur->fi==tab[x]){
				if(!vis[cur->se]) dfs(cur->se);
				to_do.erase(*cur);
			}else break;
		}
	}
	cnt++;
	for(auto u:adj[x]){
		if(vis[u.fi]) continue;
		if(colors.count(u.se)) dfs(u.fi);
		else to_do.insert({u.se,u.fi});
	}
}
std::vector<int> find_reachable(std::vector<int> r, std::vector<int> u, std::vector<int> v, std::vector<int> c) {
	int n=r.size();
	int m=u.size();
	tab=r;
	for (int i = 0; i < m; ++i)
	{
		adj[u[i]].pb({v[i],c[i]});
		adj[v[i]].pb({u[i],c[i]});
	}
	vector<int> nab(n);
	int mn=n;
	for (int i = 0; i < n; ++i)
	{
		cnt=0;
		memset(vis,0,sizeof vis);
		to_do.clear();
		colors.clear();
		dfs(i);
		nab[i]=cnt;
		mn=min(mn,nab[i]);
	}
	vector<int> ans(n);
	for (int i = 0; i < n; ++i)
	{
		ans[i]=(nab[i]==mn ? 1 : 0);
	}
	return ans;
}

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