Submission #832604

#	Time	Username	Problem	Language	Result	Execution time	Memory
832604		Rafi22	Keys (IOI21_keys)	C++17	20 / 100	73 ms	20752 KiB

keys

#include <bits/stdc++.h>
     
using namespace std;
     
#define ll long long 
#define ld long double
#define pb push_back
#define st first
#define nd second
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
int inf=1000000007;
ll infl=1000000000000000007;
     
const int N=307;

vector<pair<int,int>>G[N];
bool is[N];
bool odw[N];
int r[N];

vector<int>find_reachable(vector<int>K,vector<int>U,vector<int>V,vector<int>C)
{
	int n=sz(K),m=sz(U);
	for(int i=0;i<m;i++)
	{
		G[U[i]].pb({V[i],C[i]});
		G[V[i]].pb({U[i],C[i]});
	}
	int mn=inf;
	for(int i=0;i<n;i++)
	{
		memset(is,0,sizeof is);
		memset(odw,0,sizeof odw);
		deque<int>Q;
		Q.pb(i);
		odw[i]=1;
		vector<pair<int,int>>X;
		while(sz(Q)>0)
		{
			int v=Q[0];
			Q.pop_front();
			r[i]++;
			is[K[v]]=1;
			for(auto x:G[v]) X.pb(x);
			for(auto [u,c]:X) 
			{
				if(!odw[u]&&is[c])
				{
					odw[u]=1;
					Q.pb(u);
				}
			}
		}
		mn=min(mn,r[i]);
	}
	vector<int>ans(n,0);
	for(int i=0;i<n;i++) if(r[i]==mn) ans[i]=1;
	return ans;
}
     
/*
int main()
{
	int n,m;
	cin>>n>>m;
	vector<int>K(n);
	vector<int>U(m),V(m),C(m);
	vector<int>V=find_reachable(K,U,V,C);
	for(auto x:V) cout<<x<<" ";
	cout<<endl;
	return 0;
}*/
    

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