Submission #440919

#	Time	Username	Problem	Language	Result	Execution time	Memory
440919		ogibogi2004	Keys (IOI21_keys)	C++17	37 / 100	1121 ms	17424 KiB

keys

#include <bits/stdc++.h>
#include "keys.h"
using namespace std;
vector<pair<int,int> >g[2048];
vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c) {
	vector<int> ans(r.size(), 1);
	int n=r.size();
	int m=u.size();
	for(int i=0;i<m;i++)
	{
		g[u[i]].push_back({v[i],c[i]});
		g[v[i]].push_back({u[i],c[i]});
	}
	set<int>found_keys;
	bool vis[2048];
	queue<int>edges[2048];
	int minans=n;
	for(int i=0;i<n;i++)
	{
		found_keys.clear();
		queue<int>q;
		memset(vis,0,sizeof(vis));
		vis[i]=1;
		int cnt=0;
		q.push(i);
		while(!q.empty())
		{
			int f=q.front();
			q.pop();cnt++;
			if(found_keys.find(r[f])==found_keys.end())
			{
				while(!edges[r[f]].empty())
				{
					int w=edges[r[f]].front();
					edges[r[f]].pop();
					if(vis[w])continue;
					q.push(w);vis[w]=1;
				}
			}
			found_keys.insert(r[f]);
			for(auto xd:g[f])
			{
				if(vis[xd.first])continue;
				if(found_keys.find(xd.second)!=found_keys.end())
				{
					vis[xd.first]=1;
					q.push(xd.first);
				}
				else edges[xd.second].push(xd.first);
			}
		}
		for(int j=0;j<2048;j++)
		{
			while(!edges[j].empty())edges[j].pop();
		}
		ans[i]=cnt;
		minans=min(minans,ans[i]);
	}
	for(int i=0;i<n;i++)
	{
		if(ans[i]==minans)ans[i]=1;
		else ans[i]=0;
	}
	return ans;
}

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