Submission #791159

#	Time	Username	Problem	Language	Result	Execution time	Memory
791159		shoryu386	Crocodile's Underground City (IOI11_crocodile)	C++17	100 / 100	678 ms	86164 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[]){
	#define ll long long
	ll incoming[n];
	multiset<ll> dist[n];
	set<int> bruh;
	memset(incoming, 0, sizeof(incoming));
	
	for (ll x = 0; x < n; x++) dist[x].insert(LLONG_MAX/20),dist[x].insert(LLONG_MAX/20);
	
	priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> 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 (ll x = 0; x < exitCount; x++){
		distUpdate(exits[x], 0);
		distUpdate(exits[x], 0);

		incoming[exits[x]] = INT_MIN;
		
		pq.push({0, exits[x]});
	}
	
	vector<pair<ll, ll>> adjList[n];
	for (ll 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()){
		
		ll d = pq.top().first, node = pq.top().second;
		pq.pop();
		//cout << node << ' ' << d << '\n';
		
		if (d > *prev(dist[node].end()) || bruh.count(node) != 0) continue;
		bruh.insert(node);
		for (auto x : adjList[node]){
			//cout << x.first << "upd\n";
			ll 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: 11 / 11