Submission #114582

#	Time	Username	Problem	Language	Result	Execution time	Memory
114582		ly20	Shortcut (IOI16_shortcut)	C++14	0 / 100	124 ms	150008 KiB

shortcut

#include<bits/stdc++.h>
using namespace std;
#define debug(args...) //fprintf(stderr,args)
#include "shortcut.h"
const int MAXN=2123456;
const long long INF=11234567891234567;
vector<int> dm[MAXN],grafo[MAXN],peso[MAXN];
int marc[MAXN];
long long dist[MAXN],mx,idm;
set<pair<int,int> > s;
void dfs(int v)
{
	while(!s.empty())
	{
		int cur=(s.begin())->second;s.erase(s.begin());
		marc[cur]=1;
		for(int i=0;i<grafo[cur].size();i++)
		{
			int viz=grafo[cur][i],ps=peso[cur][i];
			if(marc[viz])continue;
			if(dist[viz]!=INF)s.erase(make_pair(dist[viz],viz));
			dist[viz]=min(dist[viz],dist[cur]+ps);
			s.insert(make_pair(dist[viz],viz));
		}
	}
}
long long find_shortcut(int n,vector<int> l,vector<int> d,int c)
{
	int tot=n;
	for(int i=0;i<n-1;i++)
	{
		grafo[i].push_back(i+1);grafo[i+1].push_back(i);
		peso[i].push_back(l[i]);peso[i+1].push_back(l[i+1]);
	}
	for(int i=0;i<n;i++)
	{
		if(d[i]!=0)
		{
			grafo[i].push_back(tot);grafo[tot].push_back(i);
			peso[i].push_back(d[i]);peso[tot].push_back(d[i]);
			tot++;
		}
	}
	debug("tot=%d\n",tot);
	long long resp=INF;
	for(int i=0;i<n;i++)
	{
		for(int j=i+1;j<n;j++)
		{
			grafo[i].push_back(j);grafo[j].push_back(i);
			peso[i].push_back(c);peso[j].push_back(c);
			idm=0;mx=0;
			for(int k=0;k<tot;k++)
			{
				dist[k]=INF;marc[k]=0;
			}
			dist[0]=0;
			s.insert(make_pair(dist[0],0));
			dfs(0);
			/*if(i==0 && j==6)
			{
				for(int i=0;i<tot;i++)debug("dist[%d]=%lld\n",i,dist[i]);
				debug("\n");
			}*/
			for(int k=0;k<tot;k++)
			{
				if(mx<=dist[k])
				{
					mx=dist[k];idm=k;
				}
			}
			vector<long long> idmk;
			for(int k=0;k<tot;k++)
			{
				if(mx==dist[k])
				{
					idmk.push_back(k);
				}
			}
			long long mxk=0;
			for(int i=0;i<idmk.size();i++)
			{
				idm=idmk[i];
				for(int k=0;k<tot;k++)
				{
					dist[k]=INF;marc[k]=0;
				}
				dist[idm]=0;
				mx=0;
				s.insert(make_pair(dist[idm],idm));
				dfs(idm);
				for(int k=0;k<tot;k++)
				{
					mx=max(dist[k],mx);
				}
				mxk=max(mxk,mx);
			}
			for(int k=0;k<tot;k++)
			{
				mx=max(dist[k],mx);
			}
			resp=min(resp,mx);
			debug("%d %d\n",i,j);
			debug("%d %d\n",mx,idm);
			grafo[i].pop_back();grafo[j].pop_back();
			peso[i].pop_back();peso[j].pop_back();
		}
	}
	return resp;
}
/*int main()
{
	int n,c;
	vector<int> l,d;
	scanf("%d %d",&n,&c);
	int v;
	for(int i=0;i<n-1;i++)scanf("%d",&v),l.push_back(v);
	for(int i=0;i<n;i++)scanf("%d",&v),d.push_back(v);
	printf("%lld\n",find_shortcut(n,l,d,c));
}*/
/*
9 30
10 10 10 10 10 10 10 10
20 0 30 0 0 40 0 40 0
*/

Compilation message (stderr)

shortcut.cpp: In function 'void dfs(int)':
shortcut.cpp:17:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<grafo[cur].size();i++)
               ~^~~~~~~~~~~~~~~~~~
shortcut.cpp: In function 'long long int find_shortcut(int, std::vector<int>, std::vector<int>, int)':
shortcut.cpp:81:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int i=0;i<idmk.size();i++)
                ~^~~~~~~~~~~~

• 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