Submission #421988

#	Time	Username	Problem	Language	Result	Execution time	Memory
421988		oolimry	Escape Route (JOI21_escape_route)	C++17	5 / 100	9035 ms	111960 KiB

escape_route

#include "escape_route.h"
#include <bits/stdc++.h>
using namespace std;
#define sz(x) (int) (x).size()
#define all(x) (x).begin(), (x).end()
#define show(x) cerr << #x << " is " << x << endl;
#define show2(x,y) cerr << #x << " is " << x << " " << #y << " is " << y << endl;
#define show3(x,y,z) cerr << #x << " is " << x << " " << #y << " is " << y << " " << #z << " is " << z << endl;
#define tern(cond, a, b) (cond ? a : b)
typedef long long lint;
typedef pair<lint,lint> ii;
 
lint byou;
vector<lint> dis0[95];
vector<lint> distest;
bool done[95];
lint inf = (1LL << 59LL);
 
struct edge{
	lint to, L, C;
};
vector<edge> adj[95];
 
inline void relax(vector<lint> &dis, int a, int b, lint L, lint C){
	lint x = dis[a] % byou;
	if(x <= C-L) dis[b] = min(dis[b], dis[a] + L);
	else{
		lint t2 = ((dis[a]/byou) + 1) * byou + L;
		dis[b] = min(dis[b], t2);
	}
}
 
vector<long long> calculate_necessary_time(int n, int m, long long SSS, 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){
	byou = SSS;
	
	for(int st = 0;st < n;st++){
		dis0[st].resize(n);
		fill(all(dis0[st]), inf);
		dis0[st][st] = 0;
		for(int k = 0;k < 2*n;k++){
			for(int i = 0;i < m;i++){
				relax(dis0[st], A[i], B[i], L[i], C[i]);
				relax(dis0[st], B[i], A[i], L[i], C[i]);
			}
		}
	}
	
	for(int i = 0;i < m;i++){
		adj[A[i]].push_back({B[i], L[i], C[i]});
		adj[B[i]].push_back({A[i], L[i], C[i]});
	}
	
	distest.resize(n+1);
	for(int a = 0;a < n;a++){
		for(int b = 0;b < n;b++){
			lint low = -1, high = byou+1;
			while(low != high-1){
				lint mid = (low+high)/2;
				
				fill(all(distest), inf);
				distest[a] = mid;
				fill(done,done+n+1,0);
				
				for(int k = 0;k < n;k++){
					int mp = n;
					for(int i = 0;i < n;i++){
						if(not done[i] and distest[i] < distest[mp]) mp = i;
					}
					
					done[mp] = true;
					if(mp == b) break;
					
					for(edge e : adj[mp]){
						if(not done[e.to]) relax(distest, mp, e.to, e.L, e.C);
					}
				}
				
				if(distest[b] < byou) low = mid;
				else high = mid;
			}
		}
	}
	
	vector<lint> ans(Q);
	
	for(int q = 0;q < Q;q++){
		fill(all(distest), inf);
		distest[U[q]] = T[q];
		fill(done,done+n+1,0);
		
		for(int k = 0;k < n;k++){
			int mp = n;
			for(int i = 0;i < n;i++){
				if(not done[i] and distest[i] < distest[mp]) mp = i;
			}
			
			done[mp] = true;
			if(distest[mp] > byou) break;
			
			for(edge e : adj[mp]){
				if(not done[e.to]) relax(distest, mp, e.to, e.L, e.C);
			}
		}
		
		lint res = distest[V[q]];
		
		for(int u = 0;u < n;u++){
			if(distest[u] < byou){
				res = min(res, byou + dis0[u][V[q]]);
			}
		}
		
		res -= T[q];
		ans[q] = res;
	}
	
	return ans;
}

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