oj.uz

Submission #114580

# Submission time Handle Problem Language Result Execution time Memory
114580 2019-06-01T20:54:58 Z ly20 Shortcut (IOI16_shortcut) C++14
Compilation error
 0 ms 0 KB 
#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<int> idmk;
			for(int k=0;k<tot;k++)
			{
				if(mx==dist[k])
				{
					idmk.push_back(i);
				}
			}
			int 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

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++)
                ~^~~~~~~~~~~~
shortcut.cpp:96:19: error: no matching function for call to 'max(int&, long long int&)'
     mxk=max(mxk,mx);
                   ^
In file included from /usr/include/c++/7/bits/char_traits.h:39:0,
                 from /usr/include/c++/7/ios:40,
                 from /usr/include/c++/7/istream:38,
                 from /usr/include/c++/7/sstream:38,
                 from /usr/include/c++/7/complex:45,
                 from /usr/include/c++/7/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:52,
                 from shortcut.cpp:1:
/usr/include/c++/7/bits/stl_algobase.h:219:5: note: candidate: template<class _Tp> constexpr const _Tp& std::max(const _Tp&, const _Tp&)
     max(const _Tp& __a, const _Tp& __b)
     ^~~
/usr/include/c++/7/bits/stl_algobase.h:219:5: note:   template argument deduction/substitution failed:
shortcut.cpp:96:19: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'long long int')
     mxk=max(mxk,mx);
                   ^
In file included from /usr/include/c++/7/bits/char_traits.h:39:0,
                 from /usr/include/c++/7/ios:40,
                 from /usr/include/c++/7/istream:38,
                 from /usr/include/c++/7/sstream:38,
                 from /usr/include/c++/7/complex:45,
                 from /usr/include/c++/7/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:52,
                 from shortcut.cpp:1:
/usr/include/c++/7/bits/stl_algobase.h:265:5: note: candidate: template<class _Tp, class _Compare> constexpr const _Tp& std::max(const _Tp&, const _Tp&, _Compare)
     max(const _Tp& __a, const _Tp& __b, _Compare __comp)
     ^~~
/usr/include/c++/7/bits/stl_algobase.h:265:5: note:   template argument deduction/substitution failed:
shortcut.cpp:96:19: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'long long int')
     mxk=max(mxk,mx);
                   ^
In file included from /usr/include/c++/7/algorithm:62:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:65,
                 from shortcut.cpp:1:
/usr/include/c++/7/bits/stl_algo.h:3462:5: note: candidate: template<class _Tp> constexpr _Tp std::max(std::initializer_list<_Tp>)
     max(initializer_list<_Tp> __l)
     ^~~
/usr/include/c++/7/bits/stl_algo.h:3462:5: note:   template argument deduction/substitution failed:
shortcut.cpp:96:19: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
     mxk=max(mxk,mx);
                   ^
In file included from /usr/include/c++/7/algorithm:62:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:65,
                 from shortcut.cpp:1:
/usr/include/c++/7/bits/stl_algo.h:3468:5: note: candidate: template<class _Tp, class _Compare> constexpr _Tp std::max(std::initializer_list<_Tp>, _Compare)
     max(initializer_list<_Tp> __l, _Compare __comp)
     ^~~
/usr/include/c++/7/bits/stl_algo.h:3468:5: note:   template argument deduction/substitution failed:
shortcut.cpp:96:19: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
     mxk=max(mxk,mx);
                   ^