Submission #1211559

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

escape_route

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

namespace{
	const long long int inf = 1.1e18;
}

int N,M;
long long int S;
int Q;
vector<int> A,B;
vector<long long int> L,C;
	long long int d[100][5100][100];

int main(){
	vector<int> adjlst[100];
	vector<vector<long long int>> ds[100];

	vector<long long int> turns[100];
	vector<long long int> turns1[100];
	bool used[100];
	int dit[100];
	pair<long long int, long long int> adjmat[100][100];
	
	scanf(" %d",&N);
	scanf(" %d",&M);
	scanf(" %d",&S);
	scanf(" %d",&Q);
	
	for(int i = 0; i < M; i++){
		int h,h1;
		long long int h2,h3;
		
		scanf(" %d",&h);
		scanf(" %d",&h1);
		scanf(" %lld",&h2);
		scanf(" %lld",&h3);
		
		A.push_back(h);
		B.push_back(h1);
		L.push_back(h2);
		C.push_back(h3);
	}
	
	for(int i = 0; i < M; i++){
		A.push_back(B[i]);
		B.push_back(A[i]);
		L.push_back(L[i]);
		C.push_back(C[i]);
	}
	
	for(int i = 0; i < M; i++){
		adjlst[A[i]].push_back(i);
		adjlst[B[i]].push_back(i + M);
	}
	
	for(int i = 0; i < N; i++){
		for(int j : adjlst[i]) turns[i].push_back(C[j] - L[j]);
		
		sort(turns[i].begin(),turns[i].end(), greater<int>());
		turns[i].resize(unique(turns[i].begin(),turns[i].end()) - turns[i].begin() );
	}
	
	for(int i = 0; i < N; i++){
		for(int j = 0; j < turns[i].size(); j++){
			vector<long long int> temp = {};
			
			for(int j = 0; j < N; j++){
				temp.push_back(inf);
				used[j] = false;
			}
			
			ds[i].push_back(temp);
			
			ds[i][j][i] = turns[i][j];
			
			for(int k = 0; k < N; k++){
				pair<long long int, int> ii = {inf,-1};
				
				for(int l = 0; l < N; l++) if(!used[l]) ii = min(ii,{ds[i][j][l],l });
					
				if(ii.first == inf) break;
				
				used[ii.second] = true;
				
				int it = ii.second;
				
				for(int l : adjlst[it]){
					if(ii.first + L[l] <= C[l]) ds[i][j][B[l]] = min(ds[i][j][B[l]], ii.first + L[l]);
				}
			}
			
			for(int k = 0; k < N; k++) printf("%d ",ds[i][j][k]);
			printf("\n");
		}
		printf("\n");
	}
	
	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 = turns[i][0];
		long long int diff = inf;
		//it 1
		
		turns1[i].push_back(incre);
		
		for(int j = 0; j < N; j++){
			dit[j] = 0;
			d[i][0][j] = ds[i][0][j];
		}
		
		for(int j = 0; j < N; j++){
			if(d[i][0][j] == inf) continue;
			while(dit[j] != turns[j].size() && turns[j][dit[j]] >= d[i][0][j]){
				dit[j]++;
			}
			if(dit[j] == turns[j].size()) continue;
			diff = min(diff,d[i][0][j] - turns[j][dit[j]] );
		}
		incre = incre - diff;
		
		//it
		
		for(int l = 1; l < M + 2; l++){
			if(incre < 0) break;
			
			turns1[i].push_back(incre);
			
			vector<pair<int,int>> proc;
			
			for(int j = 0; j < N; j++) d[i][l][j] = inf;
			
			for(int j = 0; j < N; j++){
				if(dit[j] == turns[j].size()) continue;
				if(d[i][l - 1][j] - turns[j][dit[j]] != diff) continue;
				for(int k = 0; k < N; k++){
					if(d[i][l - 1][k] == inf && ds[j][dit[j]][k] == inf) d[i][l][k] = min(d[i][l][k], inf);
					else d[i][l][k] = min(d[i][l][k], min(ds[j][dit[j]][k], d[i][l - 1][k] - diff));
				}
				dit[j]++;
			}
			
			diff = inf;
			
			for(int j = 0; j < N; j++){
				if(d[i][l][j] == inf) continue;
				while(dit[j] != turns[j].size() && turns[j][dit[j]] >= d[i][l][j]){
					dit[j]++;
				}
				if(dit[j] == turns[j].size()) continue;
				diff = min(diff,d[i][l][j] - turns[j][dit[j]] );
			}
			
			if(incre - diff < 0) break;
			
			incre = incre - diff;
				
		}
		
		int it = turns1[i].size() - 1;
		
		for(int it = 0; it < turns1[i].size(); it++){
			printf("f: ");
			for(int j = 0; j < N; j++){
				printf("%lld ",d[i][it][j]);
				if(d[i][it][j] == inf) continue;
				adjmat[i][j] = {1,d[i][it][j] - incre};
			}
			printf("   %d\n",incre);
		}
		printf("\n");
	}
	
	
	for(int k = 0; k < N; k++){
		for(int i = 0; i < N; i++){
			for(int j = 0; j < N; j++){
				adjmat[i][j] = min(adjmat[i][j],{adjmat[i][k].first + adjmat[k][j].first, adjmat[k][j].second });
			}
		}
	}
	
	printf("\n");
	for(int i = 0; i < N; i++){
		for(int j = 0; j < N; j++){
			printf("%lld ",adjmat[i][j].first);
		}
		printf("\n");
	}
	printf("\n");
	
	vector<long long> ans;
	
	for(int i = 0; i < Q; i++){
		/*int u = U[i];
		int v = V[i];
		long long int h = T[i];*/
		int u,v;
		long long int h;
		
		scanf(" %d",&u);
		scanf(" %d",&v);
		scanf(" %lld",&h);
		
		long long int it = upper_bound(turns1[u].begin(),turns1[u].end(),h,greater<int>()) - turns1[u].begin() - 1;
		
		if(d[u][it][v] != inf){
			ans.push_back(d[u][it][v] - d[u][it][u]);
			printf("%d   %d %d\n",it,d[u][it][v],d[u][it][u]);
		}
		else{
			
			pair<long long int,long long int> ii = {inf,inf};
			
			for(int j = 0; j < N; j++){
				if(d[u][it][j] != inf) ii = min(adjmat[j][v],ii);
			}
			printf("%lld\n",ii.first * S + ii.second - h);
			ans.push_back(ii.first * S + ii.second - h);			
		}
		
	}
	
	for(long long int i : ans) printf("%d\n",i);
	
}

Compilation message (stderr)

escape_route.cpp: In function 'int main()':
escape_route.cpp:27:18: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'long long int*' [-Wformat=]
   27 |         scanf(" %d",&S);
      |                 ~^  ~~
      |                  |  |
      |                  |  long long int*
      |                  int*
      |                 %lld
escape_route.cpp:93:61: warning: format '%d' expects argument of type 'int', but argument 2 has type '__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type' {aka 'long long int'} [-Wformat=]
   93 |                         for(int k = 0; k < N; k++) printf("%d ",ds[i][j][k]);
      |                                                            ~^
      |                                                             |
      |                                                             int
      |                                                            %lld
escape_route.cpp:174:37: warning: format '%d' expects argument of type 'int', but argument 2 has type 'long long int' [-Wformat=]
  174 |                         printf("   %d\n",incre);
      |                                    ~^    ~~~~~
      |                                     |    |
      |                                     int  long long int
      |                                    %lld
escape_route.cpp:214:34: warning: format '%d' expects argument of type 'int', but argument 2 has type 'long long int' [-Wformat=]
  214 |                         printf("%d   %d %d\n",it,d[u][it][v],d[u][it][u]);
      |                                 ~^            ~~
      |                                  |            |
      |                                  int          long long int
      |                                 %lld
escape_route.cpp:214:39: warning: format '%d' expects argument of type 'int', but argument 3 has type 'long long int' [-Wformat=]
  214 |                         printf("%d   %d %d\n",it,d[u][it][v],d[u][it][u]);
      |                                      ~^          ~~~~~~~~~~~
      |                                       |                    |
      |                                       int                  long long int
      |                                      %lld
escape_route.cpp:214:42: warning: format '%d' expects argument of type 'int', but argument 4 has type 'long long int' [-Wformat=]
  214 |                         printf("%d   %d %d\n",it,d[u][it][v],d[u][it][u]);
      |                                         ~^                   ~~~~~~~~~~~
      |                                          |                             |
      |                                          int                           long long int
      |                                         %lld
escape_route.cpp:229:45: warning: format '%d' expects argument of type 'int', but argument 2 has type 'long long int' [-Wformat=]
  229 |         for(long long int i : ans) printf("%d\n",i);
      |                                            ~^    ~
      |                                             |    |
      |                                             int  long long int
      |                                            %lld
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",&N);
      |         ~~~~~^~~~~~~~~~
escape_route.cpp:26:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   26 |         scanf(" %d",&M);
      |         ~~~~~^~~~~~~~~~
escape_route.cpp:27:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   27 |         scanf(" %d",&S);
      |         ~~~~~^~~~~~~~~~
escape_route.cpp:28:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   28 |         scanf(" %d",&Q);
      |         ~~~~~^~~~~~~~~~
escape_route.cpp:34:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   34 |                 scanf(" %d",&h);
      |                 ~~~~~^~~~~~~~~~
escape_route.cpp:35:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   35 |                 scanf(" %d",&h1);
      |                 ~~~~~^~~~~~~~~~~
escape_route.cpp:36:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   36 |                 scanf(" %lld",&h2);
      |                 ~~~~~^~~~~~~~~~~~~
escape_route.cpp:37:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |                 scanf(" %lld",&h3);
      |                 ~~~~~^~~~~~~~~~~~~
escape_route.cpp:206:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  206 |                 scanf(" %d",&u);
      |                 ~~~~~^~~~~~~~~~
escape_route.cpp:207:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  207 |                 scanf(" %d",&v);
      |                 ~~~~~^~~~~~~~~~
escape_route.cpp:208:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  208 |                 scanf(" %lld",&h);
      |                 ~~~~~^~~~~~~~~~~~
/usr/bin/ld: /tmp/cc5tlsxN.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccbhzVuu.o:escape_route.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/cc5tlsxN.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