Submission #1169669

#	Time	Username	Problem	Language	Result	Execution time	Memory
1169669		Amostmh	Voting Cities (NOI22_votingcity)	C++20	0 / 100	539 ms	1114112 KiB

Main

//3-19-2025

#include <bits/stdc++.h>

using namespace std;

vector<vector<pair<int,int>>> edges;
vector<pair<int,int>> optimal_route;
queue<int> vcity;
vector<bool> checked;

//Shortest path to any voting city
void go(){
	//A list of connecting edges to the checked cities;
	priority_queue<pair<int,pair<int,int>>> next_edges;
	
	/**/
	while(!vcity.empty()){
		
		//Populate next_edges;
		for(auto e : edges[vcity.front()])
		{
			if(checked[e.second])continue;
			next_edges.push( { e.first, {e.second,vcity.front()} } );
		}
		vcity.pop();
		
		//Prioritize the connecting edges with least cost;
		while(!next_edges.empty()){
			int next_n = next_edges.top().second.first;
			int from_n = next_edges.top().second.second;
			int travel_cost = next_edges.top().first;
						
			//If the edge is connecting to a city not travelled before
			if(!checked[next_n]){
				checked[next_n] = true;
				
				optimal_route[next_n] = {from_n,travel_cost};
				vcity.push({next_n});
				
				next_edges.pop();
				break;
			}
			
			next_edges.pop();
			
			
		}

	}
	/**/
}

//Use the precomputed path travel, store the cost of each edge in a priority queue;
vector<int> traverse(int s)
{
	//If we arrived at a voting city, return nothing ( no path to continue );
	if(s == -1)return {0};
	
	vector<int> rt = traverse(optimal_route[s].first);
	rt.push_back(optimal_route[s].second);

	return rt;
}

int main()
{
	int n, e, k;
	cin >> n >> e >> k;
	
	
	for(int i = 0; i < n+4; ++i)
	{
		edges.push_back({});
	}
	checked.assign(n+4,false);
	optimal_route.assign(n+4,{-2,0});
	
	for(int i = 0; i < k; ++i)
	{
		int foo; cin >> foo;
		optimal_route[foo] = {-1,0};
		vcity.push(foo);
	}
	
	for(int i = 0; i < e; ++i)
	{
		int u,v,c;
		cin >> u >> v >> c;
		assert(u<n);
		edges[v].push_back({c,u});
	}
	
	//Precompute the optimal path
	go();
	
	//For every S, we already know the closest path to reach a voting city
	//We will have the cost of all the toll recorded in a vector
	//After sorting the vector, we greedily choose the optimal way to use our tickets
	int q; cin >> q;
	for(int i = 0; i < q; ++i)
	{
		int s,foo;
		vector<int> ticket;
		cin >> s;
		
		int available = 0;
		
		for(int j = 0; j < 5; ++j){cin>>foo;if(foo != -1)available += 1;ticket.push_back(foo);}
		
		if(optimal_route[s].first == -2){
			cout << -1 << '\n';
			continue;
		}
		vector<int> journeyCosts = traverse(s);
		
		
		long long total = 0;
		for(auto a : journeyCosts){total += a;}
		
		sort(journeyCosts.begin(),journeyCosts.end(),greater<int>());
		
		
		
		for(int j = 0; j < journeyCosts.size()-1; ++j){
			
			long long discount = 0;

			int usingTicket;
			
			for(int t = 0; t < 5; ++t)
			{
				if(ticket[t] != -1){
					if( (t+1)*journeyCosts[j]/10 - ticket[t] > discount ){
						discount = (t+1)*journeyCosts[j]/10 - ticket[t];
						usingTicket = t;
					}
				}
			}
			
			if(discount > 0)
			{
				total -= discount;
				ticket[usingTicket] = -1;
				available-= 1;
			}
			
			if(available == 0)break;
			
		}
		
		cout << total << '\n';
	}

	
	return 0;
}

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