Submission #1157682

#	Time	Username	Problem	Language	Result	Execution time	Memory
1157682		shn	Escape Route (JOI21_escape_route)	C++20	0 / 100	9093 ms	111940 KiB

escape_route

#include "escape_route.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
const int N = 92;

struct node{
	long long w , lim;
	int to;
};

vector < node > g[N];

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> v,vector<int> u, vector<long long> t){
	vector < long long > ans;
	for(int i = 0; i < m; i++){
		g[a[i]].pb({l[i] , c[i] , b[i]});
		g[b[i]].pb({l[i] , c[i] , a[i]});
	}
	for(int i = 0; i < q; i++){
		set < pair < pair < int , long long > , int > > st;
		st.insert({{0 , t[i]} , v[i]});
		pair < int , long long > dst[n];
		for(int i = 0; i < n; i++) dst[i] = {n + 1 , n + 1};
		dst[v[i]] = {0 , t[i]};
		while(st.size()){
			int v = st.begin() -> second;
			st.erase(st.begin());
			for(node it : g[v]){
				int d = dst[v].first , tim = dst[v].second;
				if(0 <= tim && tim <= it.lim - it.w){
					tim += it.w;
				}
				else{
					tim = it.w;
					d++;
				}
				if(dst[it.to].first > d || dst[it.to].first == d && dst[it.to].second > tim){
					st.erase({dst[it.to] , it.to});
					dst[it.to] = {d , tim};
					st.insert({dst[it.to] , it.to});
				}
			}
		}
		ans.pb(dst[u[i]].first * s + dst[u[i]].second - t[i]);
	}
	return ans;
}

// int main(){
	// int n , m;
	// long long s;
	// int q;
	// cin >> n >> m >> s >> q;
	// vector < int > a , b;
	// vector < long long > l , c;
	// for(int i = 0; i < m; i++){
		// int x , y , z , t;
		// cin >> x >> y >> z >> t;
		// a.pb(x);
		// b.pb(y);
		// l.pb(z);
		// c.pb(t);
	// }
	// vector < int > v , u;
	// vector < long long > t;
	// for(int i = 0; i < q; i++){
		// int x , y , z;
		// cin >> x >> y >> z;
		// v.pb(x);
		// u.pb(y);
		// t.pb(z);
	// }
	// vector < long long > ans = calculate_necessary_time(n , m , s , q , a , b , l , c , v , u , t);
	// for(auto it : ans){
		// cout << it << '\n';
	// }
// }

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