oj.uz

Submission #302668

# Submission time Handle Problem Language Result Execution time Memory
302668 2020-09-19T03:16:18 Z shrek12357 Crocodile's Underground City (IOI11_crocodile) C++14
100 / 100
 678 ms 54636 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <map>
#include <set>
#include <climits>
#include <cmath>
#include <fstream>
#include <queue>
#include "crocodile.h"
using namespace std;

const long long INF = 1e10;
const int MAXN = 1e5+5;
#define ll long long

priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> pq;
pair<ll , ll> dist[MAXN];
bool vis[MAXN];
vector<pair<int, int>> adjList[MAXN];

int travel_plan(int n, int m, int r[][2], int l[], int k, int p[]) {
	for (int i = 0; i < m; i++) {
		adjList[r[i][0]].push_back({ r[i][1], l[i] });
		adjList[r[i][1]].push_back({ r[i][0], l[i] });
	}
	for (int i = 0; i < n; i++) {
		dist[i] = { INF, INF };
		vis[i] = false;
	}
	for (int i = 0; i < k; i++) {
		dist[p[i]] = { 0, 0 };
		pq.push({ 0, p[i] });
	}
	while (pq.size() > 0) {
		int cur = pq.top().second;
		int d = pq.top().first;
		pq.pop();
		if (vis[cur] || d != dist[cur].second) {
			continue;
		}
		if (cur == 0) {
			return d;
		}
		vis[cur] = true;
		for (auto i : adjList[cur]) {
			if (vis[i.first]) {
				continue;
			}
			if (d + i.second > dist[i.first].second) {
				continue;
			}
			if (d + i.second < dist[i.first].first) {
				dist[i.first].second = dist[i.first].first;
				dist[i.first].first = d + i.second;
			}
			else {
				dist[i.first].second = d + i.second;
			}
			pq.push({ d + i.second, i.first });
		}
	}
}

Compilation message

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

Subtask #1
46.0 / 46.0

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

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2688 KB Output is correct
2 Correct 2 ms 2688 KB Output is correct
3 Correct 2 ms 2688 KB Output is correct
4 Correct 3 ms 2816 KB Output is correct
5 Correct 3 ms 2816 KB Output is correct
6 Correct 3 ms 2816 KB Output is correct
7 Correct 3 ms 2816 KB Output is correct
8 Correct 3 ms 2816 KB Output is correct
9 Correct 4 ms 2944 KB Output is correct
10 Correct 2 ms 2688 KB Output is correct
11 Correct 3 ms 2816 KB Output is correct
12 Correct 7 ms 3200 KB Output is correct
13 Correct 6 ms 3200 KB Output is correct
14 Correct 2 ms 2688 KB Output is correct
15 Correct 3 ms 2816 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2688 KB Output is correct
2 Correct 2 ms 2688 KB Output is correct
3 Correct 2 ms 2688 KB Output is correct
4 Correct 3 ms 2816 KB Output is correct
5 Correct 3 ms 2816 KB Output is correct
6 Correct 3 ms 2816 KB Output is correct
7 Correct 3 ms 2816 KB Output is correct
8 Correct 3 ms 2816 KB Output is correct
9 Correct 4 ms 2944 KB Output is correct
10 Correct 2 ms 2688 KB Output is correct
11 Correct 3 ms 2816 KB Output is correct
12 Correct 7 ms 3200 KB Output is correct
13 Correct 6 ms 3200 KB Output is correct
14 Correct 2 ms 2688 KB Output is correct
15 Correct 3 ms 2816 KB Output is correct
16 Correct 570 ms 51124 KB Output is correct
17 Correct 99 ms 14584 KB Output is correct
18 Correct 115 ms 16120 KB Output is correct
19 Correct 678 ms 54636 KB Output is correct
20 Correct 351 ms 43384 KB Output is correct
21 Correct 48 ms 7928 KB Output is correct
22 Correct 396 ms 38800 KB Output is correct