제출 #1157997

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1157997		mendeke	Escape Route (JOI21_escape_route)	C++20	5 / 100	9091 ms	111940 KiB

escape_route

#include "escape_route.h"
#include<bits/stdc++.h>
#define ll long long
#define F first
#define S second
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define all(x) x.begin(), x.end()

using namespace std;

std::vector<long long> calculate_necessary_time(int N, int M, long long S, int Q, std::vector<int> A, std::vector<int> B,std::vector<long long> L, std::vector<long long> C, std::vector<int> U,std::vector<int> V, std::vector<long long> T) {
	ll n = N, m = M, tm = S, q = Q, d[2002];
	vector <ll> ans;
	vector <pair <ll, pair <ll, ll>>> g[2002];
	for (int i = 0; i < m; i++){
		g[A[i]].pb ({B[i], {L[i], C[i]}});
		g[B[i]].pb ({A[i], {L[i], C[i]}});
	}    
	for (int i = 0; i < n; i++){
		random_shuffle (all (g[i]));
	}
	for (int i = 0; i < q; i++){
		ll a = U[i], b = V[i], c = T[i];
		set <pair <ll, ll>> s;
		for (int i = 0; i < n; i++){
			d[i] = 1e18;
		}
		d[a] = c;
		s.insert ({d[a], a});
		int cnt1 = 40;
		while (cnt1 > 0 && s.size()){
			cnt1--;
			pair <ll, ll> mn = *s.begin();
			ll v = mn.S, w = mn.F;
			s.erase (mn);
			int cnt = 40;
			for (auto i: g[v]){
				if (cnt == 0){
					break;
				}
				cnt--;
				if (w % tm + i.S.F <= i.S.S && w + i.S.F < d[i.F]){
					s.erase ({d[i.F], i.F});
					d[i.F] = w + i.S.F;
					s.insert ({d[i.F], i.F});
				}
				else if (w % tm + i.S.F > i.S.S){
					a = (tm - w % tm) + i.S.F + w;
					if (a < d[i.F]){
						s.erase ({d[i.F], i.F});
						d[i.F] = a;
						s.insert ({d[i.F], i.F});
					}
				}
			}
		}
		ans.pb (d[b] - c);
	}
	return ans;
}

• Subtask 1: 5 / 5
• Subtask 2: 0 / 20
• Subtask 3: 0 / 10
• Subtask 4: 0 / 35
• Subtask 5: 0 / 30