oj.uz

Submission #799865

# Submission time Handle Problem Language Result Execution time Memory
799865 2023-08-01T07:18:55 Z Sohsoh84 Crocodile's Underground City (IOI11_crocodile) C++17
89 / 100
 888 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);
	}

	return dist[0];
}

Subtask #1
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 125516 KB Output is correct
2 Correct 53 ms 125556 KB Output is correct
3 Correct 59 ms 125744 KB Output is correct
4 Correct 54 ms 125796 KB Output is correct
5 Correct 52 ms 125876 KB Output is correct
6 Correct 51 ms 125748 KB Output is correct
7 Correct 53 ms 125804 KB Output is correct
8 Correct 52 ms 125824 KB Output is correct

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 125516 KB Output is correct
2 Correct 53 ms 125556 KB Output is correct
3 Correct 59 ms 125744 KB Output is correct
4 Correct 54 ms 125796 KB Output is correct
5 Correct 52 ms 125876 KB Output is correct
6 Correct 51 ms 125748 KB Output is correct
7 Correct 53 ms 125804 KB Output is correct
8 Correct 52 ms 125824 KB Output is correct
9 Correct 56 ms 127180 KB Output is correct
10 Correct 55 ms 125744 KB Output is correct
11 Correct 62 ms 126156 KB Output is correct
12 Correct 65 ms 128716 KB Output is correct
13 Correct 60 ms 128748 KB Output is correct
14 Correct 51 ms 125740 KB Output is correct
15 Correct 53 ms 126172 KB Output is correct

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 125516 KB Output is correct
2 Correct 53 ms 125556 KB Output is correct
3 Correct 59 ms 125744 KB Output is correct
4 Correct 54 ms 125796 KB Output is correct
5 Correct 52 ms 125876 KB Output is correct
6 Correct 51 ms 125748 KB Output is correct
7 Correct 53 ms 125804 KB Output is correct
8 Correct 52 ms 125824 KB Output is correct
9 Correct 56 ms 127180 KB Output is correct
10 Correct 55 ms 125744 KB Output is correct
11 Correct 62 ms 126156 KB Output is correct
12 Correct 65 ms 128716 KB Output is correct
13 Correct 60 ms 128748 KB Output is correct
14 Correct 51 ms 125740 KB Output is correct
15 Correct 53 ms 126172 KB Output is correct
16 Runtime error 888 ms 262144 KB Execution killed with signal 9
17 Halted 0 ms 0 KB -