Submission #1125952

#	Time	Username	Problem	Language	Result	Execution time	Memory
1125952		Kel_Mahmut	Escape Route (JOI21_escape_route)	C++20	0 / 100	9090 ms	111940 KiB

escape_route

#include "escape_route.h"
#include <bits/stdc++.h>
#define pb push_back
#define endl ("\n")
#define all(aa) aa.begin(), aa.end()
typedef long long ll;
using namespace std;

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) {

	const ll inf = 1e18;


	vector<vector<array<ll, 3>>> g(n);
	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]});
	}


	vector<vector<ll>> mes(n, vector<ll>(n, inf));
	for(int u = 0; u < n; u++){
		priority_queue<array<ll, 2>, vector<array<ll, 2>>, greater<array<ll, 2>>> pq;
		pq.push({0, u});
		vector<int> vis(n);
		while(!pq.empty()){
			auto [d, v] = pq.top(); pq.pop();
			if(vis[v]) continue;
			vis[v] = 1;
			mes[u][v] = d;

			for(auto [go, len, tim] : g[v]){
				if(!vis[go] && d + len <= tim){
					pq.push({d + len, go});
				}
			}
		}
	}
	vector<vector<int>> gidible(n);
	for(int u = 0; u < n; u++){
		for(int v = 0; v < n; v++){
			if(mes[u][v] != inf)
				gidible[u].pb(v);
		}
	}

	vector<ll> ans(q, inf);
	for(int qq = 0; qq < q; qq++){
		int uu = U[qq], vv = V[qq], tt = T[qq];
		set<int> s;
		priority_queue<array<ll, 2>, vector<array<ll, 2>>, greater<array<ll, 2>>> pq;
		pq.push({tt, uu});
		vector<int> vis(n);
		while(!pq.empty()){
			auto [d, v] = pq.top(); pq.pop();
			if(vis[v]) continue;
			vis[v] = 1;
			if(v == vv){
				ans[qq] = d - tt;
			}
			s.insert(v);

			for(auto [go, len, tim] : g[v]){
				if(!vis[go] && d + len <= tim){
					pq.push({d + len, go});
				}
			}
		}

		ll days = 1;
		while(ans[qq] == inf){
			vector<int> add;
			for(int u : s){
				if(mes[u][vv] != inf){
					ans[qq] = min(ans[qq], mes[u][vv] + days * S - tt);
				}
				for(int go : gidible[u]){
					if(!vis[go]){
						vis[go] = 1;
						add.pb(go);
					}
				}
			}
			s.clear();
			for(int u : add) s.insert(u);
			add.clear();
			days++;
			assert(days < n + 5);
		}
	}

	return ans;
}

// int main(){
// 	int n, m, q;
// 	ll s;
// 	cin >> n >> m >> s >> q;
// 	vector<int> a(m), b(m);
// 	vector<ll> l(m), c(m);
// 	for(int i = 0; i < m; i++){
// 		cin >> a[i] >> b[i] >> l[i] >> c[i];
// 	}
// 	vector<int> u(q), v(q);
// 	vector<ll> t(q);
// 	for(int i = 0; i < q; i++){
// 		cin >> u[i] >> v[i] >> t[i];
// 	}

// 	auto ar = calculate_necessary_time(n, m, s, q, a, b, l, c, u, v, t);
// 	for(auto x : ar){
// 		cout << x << endl;
// 	}
// }

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