oj.uz

Submission #367691

# Submission time Handle Problem Language Result Execution time Memory
367691 2021-02-18T02:50:00 Z 8e7 Crocodile's Underground City (IOI11_crocodile) C++14
100 / 100
 615 ms 61160 KB 
//Challenge: Accepted
#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include "crocodile.h"
#define maxn 100005
#define mod 1000000007
#define pii pair<int, int>
#define ll long long
#define ff first
#define ss second
using namespace std;
const int inf = 1<<30;
int mind[maxn][2];
vector<pii> adj[maxn];

inline bool cmp(pii a, pii b) {
	return a.ss > b.ss;
}
priority_queue<pii, vector<pii>, bool (*) (pii, pii) > pq(cmp);
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]) {
	for (int i = 0;i < M;i++) {
		adj[R[i][0]].push_back(make_pair(R[i][1], L[i]));
		adj[R[i][1]].push_back(make_pair(R[i][0], L[i]));
	}
	for (int i = 0;i < N;i++) mind[i][0] = mind[i][1] = inf;
	for (int i = 0;i < K;i++) {
		mind[P[i]][0] = mind[P[i]][1] = 0;
		pq.push(make_pair(P[i], 0));
	}

	while (pq.size()) {
		int cur = pq.top().ff, dis = pq.top().ss;
		pq.pop();
		if (dis != mind[cur][1]) continue;
		for (auto v:adj[cur]) {
			int nd = dis + v.ss, orig = mind[v.ff][1];
			if (nd <= mind[v.ff][0]) {
				mind[v.ff][1] = mind[v.ff][0];
				mind[v.ff][0] = nd;
			} else if (nd < mind[v.ff][1]) {
				mind[v.ff][1] = nd;
			}
			if (mind[v.ff][1] < orig) {
				pq.push(make_pair(v.ff, mind[v.ff][1]));
			}
		}
	}
	return mind[0][1];
}

Subtask #1
46.0 / 46.0

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

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2668 KB Output is correct
2 Correct 2 ms 2668 KB Output is correct
3 Correct 2 ms 2796 KB Output is correct
4 Correct 3 ms 2796 KB Output is correct
5 Correct 3 ms 2796 KB Output is correct
6 Correct 2 ms 2796 KB Output is correct
7 Correct 3 ms 2796 KB Output is correct
8 Correct 3 ms 2796 KB Output is correct
9 Correct 4 ms 2924 KB Output is correct
10 Correct 2 ms 2668 KB Output is correct
11 Correct 3 ms 2796 KB Output is correct
12 Correct 6 ms 3308 KB Output is correct
13 Correct 5 ms 3180 KB Output is correct
14 Correct 3 ms 2668 KB Output is correct
15 Correct 3 ms 2796 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2668 KB Output is correct
2 Correct 2 ms 2668 KB Output is correct
3 Correct 2 ms 2796 KB Output is correct
4 Correct 3 ms 2796 KB Output is correct
5 Correct 3 ms 2796 KB Output is correct
6 Correct 2 ms 2796 KB Output is correct
7 Correct 3 ms 2796 KB Output is correct
8 Correct 3 ms 2796 KB Output is correct
9 Correct 4 ms 2924 KB Output is correct
10 Correct 2 ms 2668 KB Output is correct
11 Correct 3 ms 2796 KB Output is correct
12 Correct 6 ms 3308 KB Output is correct
13 Correct 5 ms 3180 KB Output is correct
14 Correct 3 ms 2668 KB Output is correct
15 Correct 3 ms 2796 KB Output is correct
16 Correct 503 ms 57444 KB Output is correct
17 Correct 89 ms 13812 KB Output is correct
18 Correct 108 ms 15236 KB Output is correct
19 Correct 615 ms 61160 KB Output is correct
20 Correct 322 ms 49516 KB Output is correct
21 Correct 39 ms 7660 KB Output is correct
22 Correct 361 ms 46060 KB Output is correct