oj.uz

Submission #672358

# Submission time Handle Problem Language Result Execution time Memory
672358 2022-12-15T16:50:04 Z Hacv16 Crocodile's Underground City (IOI11_crocodile) C++17
100 / 100
 535 ms 133916 KB 
#include<bits/stdc++.h>
//#include "crocodile.h"
using namespace std;
 
typedef long long ll;
 
const int MAX = 2e6 + 15;
const int INF = 0x3f3f3f3f;
 
#define fr first
#define sc second
 
ll dist[MAX][2], ans;
bool seen[MAX];
vector<pair<ll, ll>> adj[MAX];
 
int travel_plan(int n, int m, int R[][2], int L[], int k, int P[]){
	for(int i = 0; i < m; i++){
		ll u = R[i][0], v = R[i][1], w = L[i];
 
		adj[u].push_back({v, w});
		adj[v].push_back({u, w});
	}
 
	for(int i = 0; i < n; i++)
		dist[i][0] = dist[i][1] = INF;
 
	priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> q;
 
	for(int i = 0; i < k; i++){
		dist[P[i]][0] = dist[P[i]][1] = 0;
		q.push({0, P[i]});
	}
 
	while(q.size()){
		ll u = q.top().sc; q.pop();
 
		if(seen[u]) continue;
 
		seen[u] = true;
 
		for(auto e : adj[u]){
			ll v = e.fr, w = e.sc;
 
			if(dist[u][1] + w < dist[v][0]){
				dist[v][1] = dist[v][0];
				dist[v][0] = dist[u][1] + w;
				q.push({dist[v][1], v});
 
			}else if(dist[u][1] + w < dist[v][1]){
				dist[v][1] = dist[u][1] + w;
				q.push({dist[v][1], v});
			}
		}
	}
 
	return dist[0][1];
}

Subtask #1
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 47188 KB Output is correct
2 Correct 23 ms 47280 KB Output is correct
3 Correct 24 ms 47228 KB Output is correct
4 Correct 25 ms 47408 KB Output is correct
5 Correct 25 ms 47360 KB Output is correct
6 Correct 29 ms 47280 KB Output is correct
7 Correct 30 ms 47392 KB Output is correct
8 Correct 27 ms 47492 KB Output is correct

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 47188 KB Output is correct
2 Correct 23 ms 47280 KB Output is correct
3 Correct 24 ms 47228 KB Output is correct
4 Correct 25 ms 47408 KB Output is correct
5 Correct 25 ms 47360 KB Output is correct
6 Correct 29 ms 47280 KB Output is correct
7 Correct 30 ms 47392 KB Output is correct
8 Correct 27 ms 47492 KB Output is correct
9 Correct 30 ms 47616 KB Output is correct
10 Correct 25 ms 47276 KB Output is correct
11 Correct 27 ms 47504 KB Output is correct
12 Correct 26 ms 47972 KB Output is correct
13 Correct 31 ms 48124 KB Output is correct
14 Correct 29 ms 47328 KB Output is correct
15 Correct 28 ms 47444 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 47188 KB Output is correct
2 Correct 23 ms 47280 KB Output is correct
3 Correct 24 ms 47228 KB Output is correct
4 Correct 25 ms 47408 KB Output is correct
5 Correct 25 ms 47360 KB Output is correct
6 Correct 29 ms 47280 KB Output is correct
7 Correct 30 ms 47392 KB Output is correct
8 Correct 27 ms 47492 KB Output is correct
9 Correct 30 ms 47616 KB Output is correct
10 Correct 25 ms 47276 KB Output is correct
11 Correct 27 ms 47504 KB Output is correct
12 Correct 26 ms 47972 KB Output is correct
13 Correct 31 ms 48124 KB Output is correct
14 Correct 29 ms 47328 KB Output is correct
15 Correct 28 ms 47444 KB Output is correct
16 Correct 446 ms 125916 KB Output is correct
17 Correct 107 ms 64504 KB Output is correct
18 Correct 133 ms 66900 KB Output is correct
19 Correct 535 ms 133916 KB Output is correct
20 Correct 274 ms 112668 KB Output is correct
21 Correct 60 ms 54952 KB Output is correct
22 Correct 303 ms 109292 KB Output is correct