Submission #1157707

#	Time	Username	Problem	Language	Result	Execution time	Memory
1157707		shn	Escape Route (JOI21_escape_route)	C++20	5 / 100	9091 ms	111940 KiB

escape_route

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

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 < long long , long long > , int > > st;
		st.insert({{0 , t[i]} , v[i]});
		pair < long long , long long > dst[n];
		for(int i = 0; i < n; i++) dst[i] = {n + 5 , n + 100};
		dst[v[i]] = {0 , t[i]};
		while(st.size()){
			int v = st.begin() -> second;
			st.erase(st.begin());
			for(node it : g[v]){
				long long d = dst[v].first , tim = dst[v].second;
				// cout << v << ' ' << it.to << ' ' << d << ' ' << tim << '\n';
				if(0 <= tim && tim <= it.lim - it.w){
					tim += it.w;
				}
				else{
					tim = it.w;
					d++;
				}
				// d += tim / s;
				// tim %= s;
				// cout << d << ' ' << s << '\n';
				if(min(dst[it.to] , {d , tim}) != dst[it.to]){
					st.erase({dst[it.to] , it.to});
					dst[it.to] = {d , tim};
					st.insert({dst[it.to] , it.to});
				}
			}
		}
		// for(int i = 0; i < n; i++){
			// cout << dst[i].first << ' ' << dst[i].second << '\n';
		// }
		ans.pb(dst[u[i]].first * s + dst[u[i]].second - t[i]);
	}
	// cout << "sdg";
	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;
// 		long long 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; long long 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: 5 / 5
• Subtask 2: 0 / 20
• Subtask 3: 0 / 10
• Subtask 4: 0 / 35
• Subtask 5: 0 / 30