oj.uz

Submission #421936

# Submission time Handle Problem Language Result Execution time Memory
421936 2021-06-09T13:57:44 Z shenxy Escape Route (JOI21_escape_route) C++17
5 / 100
 9000 ms 112068 KB 
#include "escape_route.h"
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
typedef pair<long long, long long> ii;
typedef pair<ii, int> iii;
vector<long long> calculate_necessary_time(int N, int M, long long S, int Q, vector<int> A, vector<int> B, vector<long long> L, vector<long long> C, vector<int> U, vector<int> V, vector<long long> T) {
	vector<iii> adjlist[N];
	vector<long long> ans;
	for (int i = 0; i < M; ++i) {
		adjlist[A[i]].push_back(iii(ii(L[i], C[i]), B[i]));
		adjlist[B[i]].push_back(iii(ii(L[i], C[i]), A[i]));
	}
	for (int i = 0; i < Q; ++i) {
		ii dist[N];
		for (int i = 0; i < N; ++i) dist[i] = ii(100, 0);
		dist[U[i]] = ii(0, T[i]);
		priority_queue< iii, vector<iii>, greater<iii> > pq;
		pq.push(iii(dist[U[i]], U[i]));
		while (!pq.empty()) {
			iii x = pq.top();
			pq.pop();
			if (x.first != dist[x.second]) continue;
			if (x.second == V[i]) break;
			for (iii i: adjlist[x.second]) {
				ii dst;
				if (x.first.second + i.first.first <= i.first.second) dst = ii(x.first.first, x.first.second + i.first.first);
				else dst = ii(x.first.first + 1, i.first.first);
				if (dst < dist[i.second]) {
					dist[i.second] = dst;
					pq.push(iii(dst, i.second));
				}
			}
		}
		ans.push_back(S * dist[V[i]].first + dist[V[i]].second - T[i]);
	}
	return ans;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 64972 KB Output is correct
2 Correct 34 ms 65040 KB Output is correct
3 Correct 41 ms 64956 KB Output is correct
4 Correct 28 ms 65032 KB Output is correct
5 Correct 33 ms 65024 KB Output is correct
6 Correct 30 ms 64964 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 9075 ms 112068 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 64972 KB Output is correct
2 Correct 34 ms 65040 KB Output is correct
3 Correct 41 ms 64956 KB Output is correct
4 Correct 28 ms 65032 KB Output is correct
5 Correct 33 ms 65024 KB Output is correct
6 Correct 30 ms 64964 KB Output is correct
7 Execution timed out 9075 ms 112068 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 64972 KB Output is correct
2 Correct 34 ms 65040 KB Output is correct
3 Correct 41 ms 64956 KB Output is correct
4 Correct 28 ms 65032 KB Output is correct
5 Correct 33 ms 65024 KB Output is correct
6 Correct 30 ms 64964 KB Output is correct
7 Execution timed out 9075 ms 112068 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 64972 KB Output is correct
2 Correct 34 ms 65040 KB Output is correct
3 Correct 41 ms 64956 KB Output is correct
4 Correct 28 ms 65032 KB Output is correct
5 Correct 33 ms 65024 KB Output is correct
6 Correct 30 ms 64964 KB Output is correct
7 Execution timed out 9075 ms 112068 KB Time limit exceeded
8 Halted 0 ms 0 KB -