oj.uz

Submission #250474

# Submission time Handle Problem Language Result Execution time Memory
250474 2020-07-18T06:46:47 Z kostia244 Crocodile's Underground City (IOI11_crocodile) C++17
100 / 100
 809 ms 62188 KB 
#include "crocodile.h"
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int maxn = 1<<17;
vector<array<int, 2>> g[maxn];
array<int, 2> dist[maxn];
priority_queue<array<int, 2>> pq;
void relax(int u, int d) {
	if(d > 1<<30) return;
	int old = dist[u][1];
	if(dist[u][0] > d) {
		dist[u][1] = dist[u][0];
		dist[u][0] = d;
	} else if(dist[u][1] > d) {
		dist[u][1] = d;
	}
	if(dist[u][1] < old)
		pq.push({-dist[u][1], u});
}
int travel_plan(int n, int m, int r[][2], int l[], int k, int p[]) {
	fill(begin(dist), end(dist), array<int, 2>{1<<30, 1<<30});
	for(int i = 0; i < k; i++) {
		relax(p[i], 0);
		relax(p[i], 0);
	}
	for(int i = 0; i < m; i++) {
		g[r[i][0]].push_back({r[i][1], l[i]});
		g[r[i][1]].push_back({r[i][0], l[i]});
	}
	while(!pq.empty()) {
		auto [cst, u] = pq.top();
		pq.pop();
		cst *= -1;
		if(cst > dist[u][1]) continue;
		for(auto [i, w] : g[u])
			relax(i, cst + w);
	}
	return dist[0][1];
}

Subtask #1
46.0 / 46.0

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

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4480 KB Output is correct
2 Correct 3 ms 4480 KB Output is correct
3 Correct 3 ms 4480 KB Output is correct
4 Correct 6 ms 4480 KB Output is correct
5 Correct 4 ms 4480 KB Output is correct
6 Correct 3 ms 4480 KB Output is correct
7 Correct 4 ms 4480 KB Output is correct
8 Correct 4 ms 4480 KB Output is correct
9 Correct 5 ms 4736 KB Output is correct
10 Correct 3 ms 4480 KB Output is correct
11 Correct 3 ms 4608 KB Output is correct
12 Correct 8 ms 4864 KB Output is correct
13 Correct 7 ms 4992 KB Output is correct
14 Correct 4 ms 4480 KB Output is correct
15 Correct 4 ms 4480 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4480 KB Output is correct
2 Correct 3 ms 4480 KB Output is correct
3 Correct 3 ms 4480 KB Output is correct
4 Correct 6 ms 4480 KB Output is correct
5 Correct 4 ms 4480 KB Output is correct
6 Correct 3 ms 4480 KB Output is correct
7 Correct 4 ms 4480 KB Output is correct
8 Correct 4 ms 4480 KB Output is correct
9 Correct 5 ms 4736 KB Output is correct
10 Correct 3 ms 4480 KB Output is correct
11 Correct 3 ms 4608 KB Output is correct
12 Correct 8 ms 4864 KB Output is correct
13 Correct 7 ms 4992 KB Output is correct
14 Correct 4 ms 4480 KB Output is correct
15 Correct 4 ms 4480 KB Output is correct
16 Correct 569 ms 58500 KB Output is correct
17 Correct 93 ms 14712 KB Output is correct
18 Correct 111 ms 16248 KB Output is correct
19 Correct 809 ms 62188 KB Output is correct
20 Correct 348 ms 51196 KB Output is correct
21 Correct 45 ms 9208 KB Output is correct
22 Correct 365 ms 47480 KB Output is correct