Submission #1209733

#	Time	Username	Problem	Language	Result	Execution time	Memory
1209733		salmon	Escape Route (JOI21_escape_route)	C++20	Compilation error	0 ms	0 KiB

escape_route

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

long long int d[100][5100][100];

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) {
		
	vector<int> adjlst[100];
	vector<long long int> t[100];
	bool done[100];
	long long int limit[100];
	pair<long long int, long long int> adjmat[100][100];
	long long int inf = 1.1e18;

	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 + 1; l++){
			for(int j = 0; j < N; j++){
				d[i][l][j] = inf;
				limit[j] = 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 < N; j++){
			assert (adjmat[i][j].first <= N);
		}
	}
	/*
	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++){
				
			}
		}
	}*/
	
	vector<long long int > ans;
	
	for(int i = 0; i < Q; i++){
		int u,v;
		long long int h;
		
		u = U[i];
		v = V[i];
		h = T[i];
		
		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){
			ans.push_back(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]);
			}
		}
		
		ans.push_back(ii.first * S + ii.second - h);
	}

	return ans;
}

int main(){

	vector<long long int> v = calculate_necessary_time(2,1,10,1,{0},{1},{6},{8},{0},{1},{3}) ;
	
	for(long long int j : v){
		printf("%lld\n",j);
	}

}

/*
2 1 20 1
0 1 5 8
*/

Compilation message (stderr)

/usr/bin/ld: /tmp/ccZS68nX.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccptFSfr.o:escape_route.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status