Submission #758949

#	Time	Username	Problem	Language	Result	Execution time	Memory
758949		jer033	Voting Cities (NOI22_votingcity)	C++17	20 / 100	49 ms	520 KiB

Main

#include <iostream>
#include <algorithm>
using namespace std;
using ll = long long;

ll const big = 2000000000;
ll const ultrabig = 12000000000000;
ll const infinity = 1234567890123456;

ll edges[20007];
ll lastedgeindex[5007];

ll tempo[5007];
ll final[5007];

ll edgedecoder(ll edge, ll id)
{
	if (id==0)
		return edge/ultrabig;
	if (id==2)
		return edge%big;
	return (edge/big)%6000;
}

ll startindex(ll lastedgeindex[5007], ll i)
{
	if (i==0)
		return 0;
	return lastedgeindex[i-1]+1;
}

int main()
{
	ll n, e, k;
	cin >> n >> e >> k;
	ll edgecount=0;
	for (ll i=1; i<=k; i++)
	{
		ll votingbooth;
		cin >> votingbooth;
		votingbooth+=1;
		edges[edgecount] = votingbooth*big;
		edgecount++;
	}
	for (ll i=1; i<=e; i++)
	{
		ll ui, vi, ci;
		cin >> ui >> vi >> ci;
		ui+=1;
		vi+=1;
		edges[edgecount] = vi*ultrabig+ui*big+ci;
		edgecount++;
	}
	sort(edges, edges+edgecount);
	edges[edgecount]=-1;
	/*for (ll i=0; i<edgecount; i++)
	{
		cout << edgedecoder(edges[i], 0) << ' ' << edgedecoder(edges[i], 1) << ' ' << edgedecoder(edges[i], 2) << '\n';
	}*/
	ll counter=0;
	for (ll city=0; city<=n; city++)
	{
		while (edgedecoder(edges[counter], 0)==city)
		{
			counter++;
		}
		lastedgeindex[city]=counter-1;
	}
	
	for (ll i=0; i<=n; i++)
	{
		tempo[i]=infinity;
		final[i]=infinity;
	}
	tempo[0]=0;
	final[0]=0;
	ll curr=0;
	for (ll iteration=1; iteration<=n; iteration++)
	{
		for (ll edgetocheck=startindex(lastedgeindex, curr); edgetocheck<=lastedgeindex[curr]; edgetocheck++)
		{
			ll newcity=edgedecoder(edges[edgetocheck], 1);
			ll travelcost=edgedecoder(edges[edgetocheck], 2);
			if (final[newcity]==infinity)
			{
				tempo[newcity]=min(tempo[newcity], final[curr]+travelcost);
			}
		}
		
		ll lowestcost=infinity;
		ll bestindex=n+1;
		for (ll city=1; city<=n; city++)
		{
			if (final[city]==infinity and tempo[city]<lowestcost)
			{
				lowestcost=tempo[city];
				bestindex=city;
			}
		}
		curr=bestindex;
		final[bestindex]=lowestcost;
	}
	
	ll q;
	cin >> q;
	for (ll query=1; query<=q; query++)
	{
		ll start, p1, p2, p3, p4, p5;
		cin >> start >> p1 >> p2 >> p3 >> p4 >> p5;
		start+=1;
		if (final[start]!=infinity)
			cout << final[start] << '\n';
		else
			cout << "-1\n";
	}
}

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 5 / 5
• Subtask 4: 5 / 5
• Subtask 5: 0 / 5
• Subtask 6: 0 / 10
• Subtask 7: 0 / 15
• Subtask 8: 0 / 50