Submission #524344

#TimeUsernameProblemLanguageResultExecution timeMemory
524344amunduzbaevEscape Route (JOI21_escape_route)C++17
0 / 100
1322 ms112104 KiB
#include "escape_route.h" #include "bits/stdc++.h" using namespace std; #ifndef EVAL #include "grader.cpp" #endif #define int long long #define i32 int32_t const int INF = 1e18; const int NN = 91; int d[NN][NN], g[NN][NN]; int de[NN][NN][NN]; vector<int> p[NN]; vector<int> calculate_necessary_time( i32 n, i32 m, int S, i32 q, vector<i32> a, vector<i32> b, vector<int> l, vector<int> c, vector<i32> u, vector<i32> v, vector<int> T) { memset(g, -1, sizeof g); memset(d, 127, sizeof d); for(int i=0;i<m;i++){ g[a[i]][b[i]] = g[b[i]][a[i]] = i; } auto go = [&](int i, int* d){ vector<int> used(n, 0); while(~i){ used[i] = 1; int t=-1; for(int j=0;j<n;j++){ if(used[j]) continue; if(~g[i][j]){ int k=g[i][j]; if(d[i]%S + l[k] <= c[k]){ d[j] = min(d[j], d[i] + l[k]); } else { d[j] = min(d[j], d[i] + (S - d[i]%S)); } } if(t == -1 || d[j] < d[t]) t = j; } i = t; } }; memset(de, 127, sizeof de); for(int i=0;i<n;i++){ d[i][i] = 0; go(i, d[i]); for(int j=0;j<n;j++){ if(~g[i][j]) p[i].push_back(g[i][j]); } sort(p[i].begin(), p[i].end(), [&](int i, int j){ return c[i] - l[i] > c[j] - l[j]; }); for(int j=0;j<(int)p[i].size();j++){ de[j][i][i] = c[p[i][j]] - l[p[i][j]]; go(i, de[j][i]); for(int k=0;k<n;k++){ if(de[j][i][k] >= S) de[j][i][k] = INF; else de[j][i][k] -= (c[p[i][j]] - l[p[i][j]]); } } } vector<vector<int>> qq(n); vector<int> res(q); for(int i=0;i<q;i++){ qq[u[i]].push_back(i); res[i] = INF; } for(int i=0;i<n;i++){ sort(qq[i].begin(), qq[i].end(), [&](int i, int j){ return (T[i] < T[j]); }); vector<int> cnt(n), D(n, INF), cur(n, -1); D[i] = 0; if(!p[i].empty()) cur[i] = c[p[i][0]] - l[p[i][0]]; while(!qq[i].empty()){ int j = max_element(cur.begin(), cur.end()) - cur.begin(); while(!qq[i].empty() && T[qq[i].back()] > cur[j]){ int in = qq[i].back(); qq[i].pop_back(); for(int g=0;g<n;g++){ res[in] = min(res[in], D[g] + (g != v[in] ? (S - D[g] - T[in]) : 0ll) + d[g][v[in]]); } } if(cur[j] < 0) break; for(int g=0;g<n;g++){ if(D[g] > D[j] + de[cnt[j]][j][g]){ D[g] = D[j] + de[cnt[j]][j][g]; if(cnt[g] < (int)p[g].size()){ cur[g] = c[p[g][cnt[g]]] - l[p[g][cnt[g]]] - D[g]; } } } cnt[j]++; if(cnt[j] < (int)p[j].size()){ cur[j] = c[p[j][cnt[j]]] - l[p[j][cnt[j]]] - D[j]; } else { cur[j] = -1; } } //~ cout<<"here"<<endl; } return res; } /* 4 5 20 1 0 1 3 19 0 2 2 8 1 2 4 15 1 3 5 14 2 3 1 18 0 3 7 4 5 20 6 0 1 3 19 0 2 2 8 1 2 4 15 1 3 5 14 2 3 1 18 0 3 5 0 3 7 0 3 9 2 0 6 3 1 10 1 2 15 */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...