Submission #524354

#	Time	Username	Problem	Language	Result	Execution time	Memory
524354		amunduzbaev	Escape Route (JOI21_escape_route)	C++17	100 / 100	2540 ms	200404 KiB

escape_route

#include "escape_route.h"
#include "bits/stdc++.h"
using namespace std;
#ifndef EVAL
#include "grader.cpp"
#endif
#define int long long
#define i32 int32_t

const int INF = 1e18;
const int NN = 91;
int d[NN][NN], g[NN][NN];
int de[NN][NN][NN], used[NN];
vector<int> p[NN];

vector<int> calculate_necessary_time(
i32 n, i32 m, int S, i32 q, vector<i32> a, vector<i32> b,
vector<int> l, vector<int> c, vector<i32> u,
vector<i32> v, vector<int> T) {
	memset(g, -1, sizeof g);
	for(int i=0;i<m;i++){
		g[a[i]][b[i]] = 
		g[b[i]][a[i]] = i;
		p[a[i]].push_back(i);
		p[b[i]].push_back(i);
	}
	
	auto go = [&](int i, int* d){
		memset(used, 0, sizeof used);
		while(~i){
			used[i] = 1;
			int t=-1;
			for(int j=0;j<n;j++){
				if(used[j]) continue;
				if(~g[i][j]){
					int k=g[i][j];
					if(d[i]%S + l[k] <= c[k]){
						d[j] = min(d[j], d[i] + l[k]);
					} else {
						d[j] = min(d[j], d[i] + (S - d[i]%S) + l[k]);
					}
				}
				
				if(d[j] < INF && (t == -1 || d[j] < d[t])) t = j;
			}
			
			i = t;
		}
	};
	//~ cout<<d[0][0]<<"\n"<<INF<<"\n";
	for(int i=0;i<NN;i++){
		for(int j=0;j<NN;j++){
			for(int k=0;k<NN;k++){
				de[i][j][k] = INF;
			} d[i][j] = INF;
		}
	}
	
	for(int i=0;i<n;i++){
		d[i][i] = 0;
		go(i, d[i]);
		
		sort(p[i].begin(), p[i].end(), [&](int i, int j){
			return c[i] - l[i] > c[j] - l[j];
		});
		for(int j=0;j<(int)p[i].size();j++){
			de[j][i][i] = c[p[i][j]] - l[p[i][j]];
			go(i, de[j][i]);
			for(int k=0;k<n;k++){
				if(de[j][i][k] >= S) de[j][i][k] = INF;
				else de[j][i][k] -= (c[p[i][j]] - l[p[i][j]]);
			}
		}
	}
	
	vector<vector<int>> qq(n);
	vector<int> res(q);
	for(int i=0;i<q;i++){
		qq[u[i]].push_back(i);
		res[i] = INF;
	}
	
	for(int i=0;i<n;i++){
		sort(qq[i].begin(), qq[i].end(), [&](int i, int j){
			return (T[i] < T[j]);
		});
		
		vector<int> cnt(n), D(n, INF), cur(n, -1);
		D[i] = 0;
		if(!p[i].empty()) cur[i] = c[p[i][0]] - l[p[i][0]];
		while(!qq[i].empty()){
			int j = max_element(cur.begin(), cur.end()) - cur.begin();
			while(!qq[i].empty() && T[qq[i].back()] > cur[j]){
				int in = qq[i].back(); qq[i].pop_back();
				for(int g=0;g<n;g++){
					if(D[g] == INF) continue;
					res[in] = min(res[in], D[g] + 
					(g != v[in] ? (S - D[g] - T[in]) : 0ll) + d[g][v[in]]);
				}
			}
			
			if(cur[j] < 0) break;
			for(int g=0;g<n;g++){
				if(D[g] > D[j] + de[cnt[j]][j][g]){
					D[g] = D[j] + de[cnt[j]][j][g];
					if(cnt[g] < (int)p[g].size()){
						cur[g] = c[p[g][cnt[g]]] - l[p[g][cnt[g]]] - D[g];
					}
				}
			}
			
			cnt[j]++;
			if(cnt[j] < (int)p[j].size()){
				cur[j] = c[p[j][cnt[j]]] - l[p[j][cnt[j]]] - D[j];
			} else {
				cur[j] = -1;
			}
		}
		
		//~ cout<<"here"<<endl;
	} return res;
}

/*

4 5 20 1
0 1 3 19
0 2 2 8
1 2 4 15
1 3 5 14
2 3 1 18
0 3 7

4 5 20 6
0 1 3 19
0 2 2 8
1 2 4 15
1 3 5 14
2 3 1 18
0 3 5
0 3 7
0 3 9
2 0 6
3 1 10
1 2 15

*/

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