oj.uz

Submission #835134

# Submission time Handle Problem Language Result Execution time Memory
835134 2023-08-23T08:56:25 Z Hydrolyzed Crocodile's Underground City (IOI11_crocodile) C++14
100 / 100
 399 ms 89168 KB 
#include "crocodile.h"
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int MxN = 100010;

struct state_t {
	int v;
	ll w;
	bool operator < (const state_t &o) const {
		return w > o.w;
	}
	state_t(int _v, ll _w):
		v(_v), w(_w) {}
};

vector<pair<int, ll>> adj[MxN];
priority_queue<state_t> pq;
ll dist[MxN][2]; // [0] = best, [1] = secondary
bitset<MxN> visited;

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]].emplace_back(R[i][1], L[i]);
		adj[R[i][1]].emplace_back(R[i][0], L[i]);
	}
	memset(dist, 0x3f, sizeof dist);
	for(int i=0; i<K; ++i) {
		pq.emplace(P[i], dist[P[i]][0] = 0ll);
	}
	while(!pq.empty()) {
		state_t now = pq.top(); pq.pop();
		if(visited[now.v]) {
			continue;
		}
		visited[now.v] = true;
		for(auto x: adj[now.v]) {
			ll nxt = now.w + x.second;
			if(dist[x.first][1] > nxt) {
				dist[x.first][1] = nxt;
				if(dist[x.first][1] < dist[x.first][0]) {
					swap(dist[x.first][1], dist[x.first][0]);
				}
				if(dist[x.first][1] <= 1e9 + 100) {
					pq.emplace(x.first, dist[x.first][1]);
				}
			}
		}
	}
	return dist[0][1];
}

Subtask #1
46.0 / 46.0

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

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4180 KB Output is correct
2 Correct 2 ms 4180 KB Output is correct
3 Correct 2 ms 4180 KB Output is correct
4 Correct 2 ms 4344 KB Output is correct
5 Correct 2 ms 4308 KB Output is correct
6 Correct 2 ms 4308 KB Output is correct
7 Correct 2 ms 4308 KB Output is correct
8 Correct 2 ms 4308 KB Output is correct
9 Correct 4 ms 4604 KB Output is correct
10 Correct 2 ms 4180 KB Output is correct
11 Correct 2 ms 4308 KB Output is correct
12 Correct 6 ms 4976 KB Output is correct
13 Correct 4 ms 4948 KB Output is correct
14 Correct 2 ms 4180 KB Output is correct
15 Correct 3 ms 4336 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4180 KB Output is correct
2 Correct 2 ms 4180 KB Output is correct
3 Correct 2 ms 4180 KB Output is correct
4 Correct 2 ms 4344 KB Output is correct
5 Correct 2 ms 4308 KB Output is correct
6 Correct 2 ms 4308 KB Output is correct
7 Correct 2 ms 4308 KB Output is correct
8 Correct 2 ms 4308 KB Output is correct
9 Correct 4 ms 4604 KB Output is correct
10 Correct 2 ms 4180 KB Output is correct
11 Correct 2 ms 4308 KB Output is correct
12 Correct 6 ms 4976 KB Output is correct
13 Correct 4 ms 4948 KB Output is correct
14 Correct 2 ms 4180 KB Output is correct
15 Correct 3 ms 4336 KB Output is correct
16 Correct 310 ms 83804 KB Output is correct
17 Correct 54 ms 17612 KB Output is correct
18 Correct 67 ms 20072 KB Output is correct
19 Correct 399 ms 89168 KB Output is correct
20 Correct 218 ms 69588 KB Output is correct
21 Correct 28 ms 10788 KB Output is correct
22 Correct 231 ms 65228 KB Output is correct