oj.uz

Submission #308939

# Submission time Handle Problem Language Result Execution time Memory
308939 2020-10-02T10:43:54 Z tengiz05 Crocodile's Underground City (IOI11_crocodile) C++17
0 / 100
 11 ms 14464 KB 
#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<n;i++)dist[i].insert(inf), dist[i].insert(inf);
	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>, vector<pair<int, int>>, greater<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]});
	}
	while(!q.empty()){
		auto pp = q.top();q.pop();
		int d = pp.first;
		int u = pp.second;
		if(*dist[u].begin() < d)continue;
		auto dd = dist[u].begin();dd++;
		int D = *dd;
		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(ss);
			dist[v].insert(D + cost);
			auto s1 = dist[v].begin();s1++;
			if(*s1 != inf){
				q.push({*dist[v].begin(), v});
			}	
		}
	}
	auto ans1 = dist[0].begin();ans1++;
	int ans = *ans1;
	return ans;
}

Subtask #1
0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 14464 KB Output is correct
2 Correct 10 ms 14464 KB Output is correct
3 Incorrect 11 ms 14464 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 14464 KB Output is correct
2 Correct 10 ms 14464 KB Output is correct
3 Incorrect 11 ms 14464 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 14464 KB Output is correct
2 Correct 10 ms 14464 KB Output is correct
3 Incorrect 11 ms 14464 KB Output isn't correct
4 Halted 0 ms 0 KB -