oj.uz

Submission #583547

# Submission time Handle Problem Language Result Execution time Memory
583547 2022-06-25T14:34:06 Z benson1029 Crocodile's Underground City (IOI11_crocodile) C++14
89 / 100
 461 ms 49128 KB 
#include "crocodile.h"
#include<bits/stdc++.h>
using namespace std;

vector< pair<int,int> > edg[100005];
long long dis[100005], dis1[100005], dis2[100005];
priority_queue< pair<long long, int> > pq;

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]) {
	for(int i=0; i<N; i++) {
		dis1[i] = dis2[i] = 1e17;
		dis[i] = 2e17;
	}
	for(int i=0; i<M; i++) {
		edg[R[i][0]].push_back({R[i][1], L[i]});
		edg[R[i][1]].push_back({R[i][0], L[i]});
	}
	for(int i=0; i<K; i++) {
		dis[P[i]] = dis1[P[i]] = dis2[P[i]] = 0;
		pq.push({0, P[i]});
	}
	while(!pq.empty()) {
		int curr = pq.top().second;
		if(dis[curr] != -pq.top().first) {
			pq.pop();
			continue;
		}
		if(curr==0) return dis[curr];
		pq.pop();
		for(auto i:edg[curr]) {
			if(dis[curr]+i.second < dis1[i.first]) {
				dis2[i.first] = dis1[i.first];
				dis1[i.first] = dis[curr]+i.second;
			} else if(dis[curr]+i.second < dis2[i.first]) {
				dis2[i.first] = dis[curr]+i.second;
			} else continue;
			if(dis2[i.first] < 1e17) {
				dis[i.first] = dis2[i.first];
				pq.push({-dis[i.first], i.first});
			}
		}
	}
}

Compilation message

crocodile.cpp: In function 'int travel_plan(int, int, int (*)[2], int*, int, int*)':
crocodile.cpp:43:1: warning: control reaches end of non-void function [-Wreturn-type]
   43 | }
      | ^

Subtask #1
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 2 ms 2772 KB Output is correct
5 Correct 2 ms 2772 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 2 ms 2772 KB Output is correct
8 Correct 2 ms 2772 KB Output is correct

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 2 ms 2772 KB Output is correct
5 Correct 2 ms 2772 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 2 ms 2772 KB Output is correct
8 Correct 2 ms 2772 KB Output is correct
9 Correct 3 ms 2900 KB Output is correct
10 Correct 2 ms 2672 KB Output is correct
11 Correct 3 ms 2804 KB Output is correct
12 Correct 5 ms 3176 KB Output is correct
13 Correct 5 ms 3156 KB Output is correct
14 Correct 2 ms 2644 KB Output is correct
15 Correct 3 ms 2772 KB Output is correct

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 2 ms 2772 KB Output is correct
5 Correct 2 ms 2772 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 2 ms 2772 KB Output is correct
8 Correct 2 ms 2772 KB Output is correct
9 Correct 3 ms 2900 KB Output is correct
10 Correct 2 ms 2672 KB Output is correct
11 Correct 3 ms 2804 KB Output is correct
12 Correct 5 ms 3176 KB Output is correct
13 Correct 5 ms 3156 KB Output is correct
14 Correct 2 ms 2644 KB Output is correct
15 Correct 3 ms 2772 KB Output is correct
16 Correct 403 ms 43508 KB Output is correct
17 Correct 83 ms 12704 KB Output is correct
18 Correct 80 ms 14016 KB Output is correct
19 Correct 461 ms 49128 KB Output is correct
20 Correct 298 ms 37320 KB Output is correct
21 Correct 38 ms 7432 KB Output is correct
22 Incorrect 298 ms 33020 KB Output isn't correct
23 Halted 0 ms 0 KB -