이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "escape_route.h"
#include <bits/stdc++.h>
#define pb push_back
#define f first
#define sc second
using namespace std;
typedef long long int ll;
typedef string str;
const ll inf = 5e17;
const int N = 90;
vector<tuple<int, ll, ll>> v[N];
bitset<N> bl;
priority_queue<pair<ll, int>> pq;
ll dis2[N][N];
const int P = 1000;
ll dis1[N][P][N];
ll sth[N][P];
int PI[N];
ll change[N];
vector<ll> calculate_necessary_time(int n, int m, ll S, int q, vector<int> A, vector<int> B,
vector<ll> L, vector<ll> C, vector<int> U, vector<int> V, vector<ll> T){
vector<ll> ans(q, inf);
for(int i = 0; i < m; i++){
v[A[i]].pb({B[i], L[i], C[i]});
v[B[i]].pb({A[i], L[i], C[i]});
}
for(int s = 0; s < n; s++){
fill(dis2[s], dis2[s]+n, inf);
for(int i = 0; i < n; i++) bl[i] = 0;
dis2[s][s] = 0;
pq.push({0, s});
while(!pq.empty()){
int nd = pq.top().sc; pq.pop();
if(bl[nd]) continue;
bl[nd] = 1;
for(auto [x, l, c]: v[nd])
if((dis2[s][nd]%S+l<=c ? dis2[s][nd]+l:((dis2[s][nd]+S-1)/S)*S+l) < dis2[s][x]){
dis2[s][x] = (dis2[s][nd]%S+l<=c ? dis2[s][nd]+l:((dis2[s][nd]+S-1)/S)*S+l);
pq.push({-dis2[s][x], x});
}
}
}
for(int s = 0; s < n; s++){
ll t = 0;
int p = 0;
PI[s] = 1;
while(1){
ll nxt = inf;
sth[s][p] = t;
fill(dis1[s][p], dis1[s][p]+n, inf);
for(int i = 0; i < n; i++) bl[i] = 0;
fill(change, change+n, inf);
dis1[s][p][s] = t;
pq.push({0, s});
while(!pq.empty()){
int nd = pq.top().sc; pq.pop();
if(bl[nd]) continue;
bl[nd] = 1;
for(auto [x, l, c]: v[nd]) if(dis1[s][p][nd]+l <= min(dis1[s][p][x]-1, c)){
dis1[s][p][x] = dis1[s][p][nd]+l;
change[x] = c-dis1[s][p][x]+1;
pq.push({-dis1[s][p][x], x});
}
}
for(int i = 0; i < n; i++) if(dis1[s][p][i] != inf) dis1[s][p][i]-=t;
nxt = min(nxt, *min_element(change, change+n));
if(nxt == inf) break;
t+=nxt;
p++, PI[s]++;
}
}
for(int i = 0; i < q; i++){
int p = (upper_bound(sth[U[i]], sth[U[i]]+PI[U[i]], T[i])-sth[U[i]])-1;
if(dis1[U[i]][p][V[i]] != inf){
ans[i] = min(ans[i], dis1[U[i]][p][V[i]]);
continue;
}
for(int j = 0; j < n; j++) if(dis1[U[i]][p][j] != inf)
ans[i] = min(ans[i], S-T[i]+dis2[j][V[i]]);
}
return ans;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |