Submission #894796

#	Time	Username	Problem	Language	Result	Execution time	Memory
894796		Faisal_Saqib	Keys (IOI21_keys)	C++17	37 / 100	180 ms	27108 KiB

keys

#include <vector>
#include <queue>
#include <iostream>
using namespace std;
const int N=3000;
vector<pair<int,int>> edge_with_key[N];
bool used_key[N];
bool marked[N];
int par[N];
vector<int> comp[N];
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 mi=2*n;
	int ed=u.size();
	vector<int> ap;
	for(int i=0;i<ed;i++)
		edge_with_key[c[i]].push_back({u[i],v[i]});
	for(int st=0;st<n;st++)
	{
		for(int ke=0;ke<n;ke++)
		{
			par[ke]=ke;
			comp[ke]={ke};
			used_key[ke]=marked[ke]=0;
		}
		queue<int> keys;	
		keys.push(r[st]);
		used_key[r[st]]=1;
		marked[st]=1;
		while(keys.size())
		{
			int f=keys.front();
			for(auto [s,e]:edge_with_key[f])
			{
				int ps=par[s];
				int pe=par[e];
				if(ps==pe)
					continue;
				if(pe==(par[st]))
					swap(ps,pe);
				// cout<<"Hello "<<endl;
				// cout<<ps<<' '<<pe<<endl; 
				// cout<<"Comp ";
				for(auto ip:comp[pe])
				{
					comp[ps].push_back(ip);
					par[ip]=ps;
					if(ps==par[st] and !used_key[r[ip]])
					{
						used_key[r[ip]]=1;
						keys.push(r[ip]);
					}
				}
				comp[pe].clear();
				// for(auto it:comp[ps])
				// {
				// 	cout<<it<<' ';
				// }
				// cout<<endl;
			}
			keys.pop();
		}
		int cnt=0;
		for(int ke=0;ke<n;ke++)
			cnt+=(par[ke]==par[st]);
		mi=min(mi,cnt);
		ap.push_back(cnt);
	}
	vector<int> cp;
	for(int i=0;i<n;i++)
	{
		cp.push_back((ap[i]==mi));
	}
	return cp;
}

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