oj.uz

Submission #799870

# Submission time Handle Problem Language Result Execution time Memory
799870 2023-08-01T07:22:17 Z Sohsoh84 Crocodile's Underground City (IOI11_crocodile) C++17
89 / 100
 2000 ms 254808 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 = 1e5 + 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;
		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 6 ms 12756 KB Output is correct
2 Correct 6 ms 12756 KB Output is correct
3 Correct 6 ms 12884 KB Output is correct
4 Correct 7 ms 13140 KB Output is correct
5 Correct 8 ms 13084 KB Output is correct
6 Correct 7 ms 13004 KB Output is correct
7 Correct 8 ms 13184 KB Output is correct
8 Correct 8 ms 13132 KB Output is correct

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 12756 KB Output is correct
2 Correct 6 ms 12756 KB Output is correct
3 Correct 6 ms 12884 KB Output is correct
4 Correct 7 ms 13140 KB Output is correct
5 Correct 8 ms 13084 KB Output is correct
6 Correct 7 ms 13004 KB Output is correct
7 Correct 8 ms 13184 KB Output is correct
8 Correct 8 ms 13132 KB Output is correct
9 Correct 12 ms 14368 KB Output is correct
10 Correct 7 ms 12952 KB Output is correct
11 Correct 8 ms 13472 KB Output is correct
12 Correct 15 ms 15972 KB Output is correct
13 Correct 12 ms 16036 KB Output is correct
14 Correct 7 ms 13012 KB Output is correct
15 Correct 8 ms 13396 KB Output is correct

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 12756 KB Output is correct
2 Correct 6 ms 12756 KB Output is correct
3 Correct 6 ms 12884 KB Output is correct
4 Correct 7 ms 13140 KB Output is correct
5 Correct 8 ms 13084 KB Output is correct
6 Correct 7 ms 13004 KB Output is correct
7 Correct 8 ms 13184 KB Output is correct
8 Correct 8 ms 13132 KB Output is correct
9 Correct 12 ms 14368 KB Output is correct
10 Correct 7 ms 12952 KB Output is correct
11 Correct 8 ms 13472 KB Output is correct
12 Correct 15 ms 15972 KB Output is correct
13 Correct 12 ms 16036 KB Output is correct
14 Correct 7 ms 13012 KB Output is correct
15 Correct 8 ms 13396 KB Output is correct
16 Execution timed out 2056 ms 254808 KB Time limit exceeded
17 Halted 0 ms 0 KB -