Submission #791153

#	Time	Username	Problem	Language	Result	Execution time	Memory
791153		shoryu386	Crocodile's Underground City (IOI11_crocodile)	C++17	89 / 100	465 ms	74856 KiB

crocodile

#include "crocodile.h"
#include <bits/stdc++.h>
using namespace std;
int travel_plan(int n, int m, int edges[][2], int weights[], int exitCount, int exits[]){
	int incoming[n];
	multiset<int> dist[n];
	memset(incoming, 0, sizeof(incoming));
	
	for (int x = 0; x < n; x++) dist[x].insert(INT_MAX/2),dist[x].insert(INT_MAX/2);
	
	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq; //for those who have fulfilled the incoming >= 2 req
	
	
	#define distUpdate(k, newval) dist[k].insert(newval); dist[k].erase(prev(dist[k].end()))
	
	for (int x = 0; x < exitCount; x++){
		distUpdate(exits[x], 0);
		distUpdate(exits[x], 0);
		

		
		pq.push({0, exits[x]});
	}
	
	vector<pair<int, int>> adjList[n];
	for (int x = 0; x < m; x++){
		adjList[edges[x][0]].push_back({edges[x][1], weights[x]});
		adjList[edges[x][1]].push_back({edges[x][0], weights[x]});
	}
	
	while (!pq.empty()){
		
		int d = pq.top().first, node = pq.top().second;
		pq.pop();
		//cout << node << ' ' << d << '\n';
		
		if (d > *prev(dist[node].end())) continue;
		
		for (auto x : adjList[node]){
			//cout << x.first << "upd\n";
			int prevSecond = *prev(dist[x.first].end());
			
			
			
			if ( d + x.second < prevSecond){ //i.e. distUpdate was successful
				incoming[x.first]++;
				distUpdate(x.first, d + x.second);
				
				
				if (incoming[x.first] >= 2) pq.push({*prev(dist[x.first].end()), x.first});
			}
		}
	}
	
	return *prev(dist[0].end());
	
}

• Subtask 1: 46 / 46
• Subtask 2: 43 / 43
• Subtask 3: 0 / 11