Submission #421936

#	Time	Username	Problem	Language	Result	Execution time	Memory
421936		shenxy	Escape Route (JOI21_escape_route)	C++17	5 / 100	9075 ms	112068 KiB

escape_route

#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 / 5
• Subtask 2: 0 / 20
• Subtask 3: 0 / 10
• Subtask 4: 0 / 35
• Subtask 5: 0 / 30