제출 #1209423

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1209423		salmon	Escape Route (JOI21_escape_route)	C++20	0 / 100	656 ms	137036 KiB

escape_route

#include "escape_route.h"
#include <bits/stdc++.h>
using namespace std;

vector<int> adjlst[100];
long long int d[100][5100][100];
vector<long long int> t[100];
bool done[100];
int limit[5100];
pair<long long int, long long int> adjmat[100][100];
pair<long long int, long long int> adjmat1[100][5100][100];

long long int inf = 1.1e18;

std::vector<long long> calculate_necessary_time(
    int N, int M, long long S, 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) {

	for(int i = 0; i < N; i++){
		adjlst[i].clear();
	}

	for(int i = 0; i < M; i++){
		adjlst[A[i]].push_back(i);
		adjlst[B[i]].push_back(i);
	}
	
	for(int i = 0; i < N; i++) for(int j = 0; j < N; j++) adjmat[i][j] = {inf,inf};
	
	for(int i = 0; i < N; i++){
		long long int incre = 0;
		long long int nextincre = 0;
		t[i].clear();
		
		for(int l = 0; l < M; l++){
			for(int j = 0; j < N; j++){
				d[i][l][j] = inf;
				limit[i] = inf;
				done[j] = false;
			}
			
			d[i][l][i] = incre;
			
			t[i].push_back(incre);
			
			nextincre = inf;
				
			for(int k = 0; k < N; k++){
				pair<long long int,int> chose = {inf, -1};
				
				for(int j = 0; j < N; j++) if(!done[j]) chose = min( {d[i][l][j],j}, chose);
				
				if(chose.first == inf) break;
				
				int it = chose.second;
				
				nextincre = min(nextincre, limit[it] + incre);
				done[it] = true;
				
				for(int j : adjlst[it]){
					if(chose.first + L[j] <= C[j]){
						if(A[j] == it && d[i][l][B[j]] > chose.first + L[j] ){
							limit[B[j]] = C[j] - (chose.first + L[j]) + 1;
							d[i][l][B[j]] = chose.first + L[j];
						}
						else if(d[i][l][A[j]] > chose.first + L[j]){
							limit[A[j]] = C[j] - (chose.first + L[j]) + 1;
							d[i][l][A[j]] = chose.first + L[j];
						}
					}
				}
			}
			
			if(nextincre == inf) break;
			
			incre = nextincre;
		}
		
		for(int j = 0; j < N; j++){
			if(d[i][0][j] != inf) adjmat[i][j] = {1,d[i][0][j]};
		}
	
	}
	
	for(int k = 0; k < N; k++){
		for(int i = 0; i < N; i++){
			for(int j = 0; j < N; j++){
				if(adjmat[i][k].first != inf && adjmat[k][j].first != inf){
					adjmat[i][j] = min(adjmat[i][j], {adjmat[i][k].first + adjmat[k][j].first, adjmat[k][j].second } );
				}
			}
		}
	}
	/*
	for(int i = 0; i < N; i++){
		for(int j = 0; j < t[i].size(); j++){
			for(int k = 0; k < N; k++){
				
			}
			
			for(int k = 0; k < N; k++){
				
			}
		}
	}*/
	
	for(int i = 0; i < Q; i++){
		int u,v;
		long long int h;
		
		u = U[i];
		v = V[i];
		h = T[i];
		//for(int k : t[u]) printf("%d ",k);
		//printf("\n");
		
		int it = upper_bound(t[u].begin(),t[u].end(),h) - t[u].begin() - 1;
		
		//printf("i: %d\n",it);
		
		if(d[u][it][v] != inf){
			printf("%lld\n",d[u][it][v] - t[u][it]);
			continue;
		}
		
		pair<long long int,long long int> ii = {N + 5, inf};
		
		for(int j = 0; j < N; j++){
			if(d[u][it][j] != inf){
				ii = min(ii,adjmat[j][v]);
			}
		}
		
		printf("%lld\n",ii.first * S + ii.second - h);
	}

	return std::vector<long long>(Q, 0);
}

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