Submission #308961

#	Time	Username	Problem	Language	Result	Execution time	Memory
308961		tengiz05	Crocodile's Underground City (IOI11_crocodile)	C++17	89 / 100	968 ms	62572 KiB

crocodile

#include "crocodile.h"
#include <bits/stdc++.h>
using namespace std;
const int inf = 1e9+7;
const int NN = 2e5+5;
vector<pair<int, int>> edges[NN];
multiset<int> dist[NN];
int travel_plan(int n, int m, int R[][2], int L[], int k, int P[]){
	for(int i=0;i<m;i++){
		edges[R[i][0]].push_back({R[i][1], L[i]});
		edges[R[i][1]].push_back({R[i][0], L[i]});
	}
	priority_queue<pair<int, int>> q;
	for(int i=0;i<k;i++){
		dist[P[i]].insert(0);
		dist[P[i]].insert(0);
		
		q.push({0, P[i]});
	}for(int i=0;i<n;i++){
		if(dist[i].empty()){
			dist[i].insert(inf);
			dist[i].insert(inf);
		}
	}
	while(!q.empty()){
		auto pp = q.top();q.pop();
		int d = -pp.first;
		int u = pp.second;
		auto dd = dist[u].begin();dd++;
		int D = *dd;
		if(D < d)continue;
		for(auto X : edges[u]){
			int v = X.first;
			int cost = X.second;
			auto ss = dist[v].begin();ss++;
			if(D+cost >= *ss)continue;
			dist[v].erase(dist[v].find(*ss));
			dist[v].insert(D + cost);
			auto s1 = dist[v].begin();s1++;
			if(*s1 != inf){
				q.push({-(*s1), v});
			}
		}
	}
	auto ans1 = dist[0].begin();ans1++;
	int ans = *ans1;
	return ans;
}

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