oj.uz

Submission #799866

# Submission time Handle Problem Language Result Execution time Memory
799866 2023-08-01T07:21:00 Z Sohsoh84 Crocodile's Underground City (IOI11_crocodile) C++17
89 / 100
 883 ms 262144 KB 
#include "crocodile.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;

#define X		first
#define Y		second
#define sep		' '
#define all(x)		(x).begin(), (x).end()
#define debug(x)	cerr << #x << ": " << x << endl;

const ll MAXN = 1e6 + 10;

ll dist[MAXN], n, m;
set<pll> adj_st[MAXN], adj_st_r[MAXN];
vector<pll> adj[MAXN];
priority_queue<pll, vector<pll>, greater<pll>> pq;

inline void check(int v) {
	if (int(adj_st[v].size()) > 1 && (next(adj_st[v].begin()) -> X) < dist[v]) {
		dist[v] = next(adj_st[v].begin()) -> X; 
		pq.push({dist[v], v});
	}
}

inline void fix(int v) {
	for (auto [u, l] : adj[v]) {
		auto it = adj_st_r[u].lower_bound(pll(v, -1));
		if (it != adj_st_r[u].end() && it -> X == v) {
			ll d = it -> Y;
			adj_st_r[u].erase(it);
			adj_st[u].erase(pll(d, v));
		}

		adj_st_r[u].insert({v, dist[v] + l});
		adj_st[u].insert({dist[v] + l, v});
		check(u);
	}
} 

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]) {
	n = N, m = M;
	for (int i = 0; i < m; i++) { 
		adj[R[i][0]].push_back({R[i][1], L[i]});
		adj[R[i][1]].push_back({R[i][0], L[i]});
	}

	memset(dist, 63, sizeof dist);
	for (int i = 0; i < K; i++) {
		int v = P[i];
		dist[v] = 0;
		pq.push({0, v});
	}

	while (!pq.empty()) {
		auto [d_v, v] = pq.top();
		pq.pop();
		if (d_v != dist[v]) continue;
		if (v == 2) {
		}
	
		fix(v);
	}

	dist[0] = min(dist[0], ll(numeric_limits<int>::max()));
	return dist[0];
}

Subtask #1
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 125516 KB Output is correct
2 Correct 49 ms 125516 KB Output is correct
3 Correct 51 ms 125656 KB Output is correct
4 Correct 55 ms 125784 KB Output is correct
5 Correct 52 ms 125884 KB Output is correct
6 Correct 52 ms 125784 KB Output is correct
7 Correct 52 ms 125800 KB Output is correct
8 Correct 52 ms 125884 KB Output is correct

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 125516 KB Output is correct
2 Correct 49 ms 125516 KB Output is correct
3 Correct 51 ms 125656 KB Output is correct
4 Correct 55 ms 125784 KB Output is correct
5 Correct 52 ms 125884 KB Output is correct
6 Correct 52 ms 125784 KB Output is correct
7 Correct 52 ms 125800 KB Output is correct
8 Correct 52 ms 125884 KB Output is correct
9 Correct 56 ms 127060 KB Output is correct
10 Correct 51 ms 125668 KB Output is correct
11 Correct 53 ms 126156 KB Output is correct
12 Correct 64 ms 128548 KB Output is correct
13 Correct 61 ms 128660 KB Output is correct
14 Correct 52 ms 125736 KB Output is correct
15 Correct 55 ms 126092 KB Output is correct

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 125516 KB Output is correct
2 Correct 49 ms 125516 KB Output is correct
3 Correct 51 ms 125656 KB Output is correct
4 Correct 55 ms 125784 KB Output is correct
5 Correct 52 ms 125884 KB Output is correct
6 Correct 52 ms 125784 KB Output is correct
7 Correct 52 ms 125800 KB Output is correct
8 Correct 52 ms 125884 KB Output is correct
9 Correct 56 ms 127060 KB Output is correct
10 Correct 51 ms 125668 KB Output is correct
11 Correct 53 ms 126156 KB Output is correct
12 Correct 64 ms 128548 KB Output is correct
13 Correct 61 ms 128660 KB Output is correct
14 Correct 52 ms 125736 KB Output is correct
15 Correct 55 ms 126092 KB Output is correct
16 Runtime error 883 ms 262144 KB Execution killed with signal 9
17 Halted 0 ms 0 KB -