Submission #118246

#	Time	Username	Problem	Language	Result	Execution time	Memory
118246		dorijanlendvaj	Shortcut (IOI16_shortcut)	C++14	0 / 100	2050 ms	404 KiB

shortcut

#include "shortcut.h"
#define ll long long
#include <bits/stdc++.h>
using namespace std;
const int MOD=1000000007;
#define x first
const ll LLINF=1ll<<60;
#define y second
#define pb push_back
#define pii pair<int,int>
#define vi vector<int> 
#define vl vector<ll>
const char en='\n';

void fil(int start,vl&dist,int n,vi l,vi d,int c,int lo,int hi)
{
	priority_queue<pair<ll,int>> pq;
	pq.push({0,start});
	vector<bool> bio;
	bio.resize(2*n);
	while (pq.size())
	{
		int i=pq.top().y;
		ll di=pq.top().x;
		pq.pop();
		if (bio[i]) continue;
		bio[i]=1;
		dist[i]=-di;
		//cout<<lo<<' '<<hi<<' '<<i<<' '<<start<<' '<<-di<<endl;
		if (i%2==0)
		{
			pq.push({di-d[i/2],i+1});
			if (i<n*2-2) pq.push({di-l[i/2],i+2});
			if (i/2==lo) pq.push({di-c,hi*2});
			if (i>0) pq.push({di-l[i/2-1],i-2});
			if (i/2==hi) pq.push({di-c,lo*2});
		}
		else
		{
			pq.push({di-d[i/2],i-1});
		}
	}
}

const int dissss=-361;

ll find_shortcut(int n,vi l,vi d,int c)
{
	assert(n<=100);
	ll mi=LLINF;
	for (int lll=0;lll<n;++lll) for (int r=lll+1;r<n;++r)
	{
		ll ma=0,ii=-1,jj=-1;
		for (int j=0;j<n;++j)
		{
			vl dist(2*n,LLINF);
			fil(j*2+1,dist,n,l,d,c,lll,r);
			for (int i=0;i<2*n;++i)
			{
				ma=max(ma,dist[i]);
				if (dist[i]==dissss) ii=i,jj=j*2+1;
			}
		}
		mi=min(mi,ma);
		if (ma==dissss) cout<<lll<<' '<<r<<' '<<ii<<' '<<jj<<en;
	}
	return mi;
}

• 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