Submission #889206

#	Time	Username	Problem	Language	Result	Execution time	Memory
889206		Muhammad_Aneeq	Shortcut (IOI16_shortcut)	C++17	0 / 100	2056 ms	49920 KiB

shortcut

#include <vector>
#include <set>
using namespace std;
int const N=1e6+10;
multiset<pair<int,int>>nei[N]={};
long long dis[N]={};
int vis[N]={};
long long ans=1e17+10;
int ns;
long long bfs(int x)
{
	for (int i=0;i<ns;i++)
	{
		vis[i]=0;
		dis[i]=1e17+10;
	}
	dis[x]=0;
	set<pair<long long,int>>s;
	s.insert({0,x});
	while (s.size())
	{
		int x=(*begin(s)).second;
		s.erase(*begin(s));
		if (vis[x])
			continue;
		vis[x]=1;
		for (auto i:nei[x])
		{
			if (dis[i.first]>dis[x]+i.second)
			{
				s.erase({dis[i.first],i.first});
				dis[i.first]=dis[x]+i.second;
				s.insert({dis[i.first],i.first});
			}
		}
	}
	long long z=0;
	for (int i=0;i<ns;i++)
		z=max(z,dis[i]);
	return z;
}
void find()
{
	long long f=0;
	for (int i=0;i<ns;i++)
	{
		long long z=bfs(i);
		f=max(f,z);
	}
	ans=min(ans,f);
}
long long find_shortcut(int n,vector<int>l,vector<int>d,int c)
{
	for (int i=0;i<n-1;i++)
	{
		nei[i].insert({i+1,l[i]});
		nei[i+1].insert({i,l[i]});
	}
	ns=n;
	for (int i=0;i<n;i++)
	{
		if (d[i])
		{
			nei[i].insert({ns,d[i]});
			nei[ns].insert({i,d[i]});
			ns++;
		}
	}
	for (int i=0;i<n;i++)
		for (int j=i+1;j<n;j++)
		{
			nei[i].insert({j,c});
			nei[j].insert({i,c});
			find();
			nei[i].erase(nei[i].find({j,c}));
			nei[j].erase(nei[j].find({i,c}));
		}
	return ans;
}

• Subtask 1: 0 / 9
• Subtask 2: 0 / 14
• Subtask 3: 0 / 8
• Subtask 4: 0 / 7
• Subtask 5: 0 / 33
• Subtask 6: 0 / 22
• Subtask 7: 0 / 4
• Subtask 8: 0 / 3