Submission #1209418

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

escape_route

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

int N;
int M;
long long int S;
int Q;
vector<int> adjlst[100];
int A[100],B[100];
long long L[100],C[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;

int main(){
		
	scanf(" %d",&N);
	scanf(" %d",&M);
	scanf(" %lld",&S);
	scanf(" %d",&Q);
	
	for(int i = 0; i < M; i++){
		scanf(" %d",&A[i]);
		scanf(" %d",&B[i]);
		scanf(" %lld",&L[i]);
		scanf(" %lld",&C[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;
		
		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;
		
		scanf(" %d",&u);
		scanf(" %d",&v);
		scanf(" %lld",&h);
		
		//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);
	}
}

Compilation message (stderr)

escape_route.cpp: In function 'int main()':
escape_route.cpp:22:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   22 |         scanf(" %d",&N);
      |         ~~~~~^~~~~~~~~~
escape_route.cpp:23:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |         scanf(" %d",&M);
      |         ~~~~~^~~~~~~~~~
escape_route.cpp:24:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   24 |         scanf(" %lld",&S);
      |         ~~~~~^~~~~~~~~~~~
escape_route.cpp:25:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |         scanf(" %d",&Q);
      |         ~~~~~^~~~~~~~~~
escape_route.cpp:28:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   28 |                 scanf(" %d",&A[i]);
      |                 ~~~~~^~~~~~~~~~~~~
escape_route.cpp:29:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   29 |                 scanf(" %d",&B[i]);
      |                 ~~~~~^~~~~~~~~~~~~
escape_route.cpp:30:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   30 |                 scanf(" %lld",&L[i]);
      |                 ~~~~~^~~~~~~~~~~~~~~
escape_route.cpp:31:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   31 |                 scanf(" %lld",&C[i]);
      |                 ~~~~~^~~~~~~~~~~~~~~
escape_route.cpp:119:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  119 |                 scanf(" %d",&u);
      |                 ~~~~~^~~~~~~~~~
escape_route.cpp:120:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  120 |                 scanf(" %d",&v);
      |                 ~~~~~^~~~~~~~~~
escape_route.cpp:121:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  121 |                 scanf(" %lld",&h);
      |                 ~~~~~^~~~~~~~~~~~
/usr/bin/ld: /tmp/ccMKwqzF.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccQ3N6qM.o:escape_route.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/ccMKwqzF.o: in function `main':
grader.cpp:(.text.startup+0x6e0): undefined reference to `calculate_necessary_time(int, int, long long, int, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >, std::vector<long long, std::allocator<long long> >, std::vector<long long, std::allocator<long long> >, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >, std::vector<long long, std::allocator<long long> >)'
collect2: error: ld returned 1 exit status