Submission #1209733

#TimeUsernameProblemLanguageResultExecution timeMemory
1209733salmonEscape Route (JOI21_escape_route)C++20
Compilation error
0 ms0 KiB
//#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