This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "escape_route.h"
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
#define BIT(mask,i) (((mask) >> (i))&1LL)
#define MASK(i) (1LL << (i))
#define MP make_pair
#define pll pair <ll,ll>
#define fi first
#define se second
#define sz(a) (ll((a).size()))
namespace{
const ll MAXN = 90;
const ll INF = 1e18;
ll n,m,s,q;
ll c[MAXN+10][MAXN+10],l[MAXN+10][MAXN+10];
ll pre[MAXN+10][MAXN+10];
bool used[MAXN+10];
ll dist[MAXN+10];
ll last_c[MAXN+10];
struct query{
ll u,v,t,id;
};
vector <query> all_query;
vector <ll> ans;
void solve(){
ans.resize(sz(all_query));
sort(all_query.begin(),all_query.end(),[&](query x,query y){return x.u < y.u;});
for (ll i = 1;i <= n;i ++){
for (ll j = 1;j <= n;j ++){dist[j] = INF;used[j] = 0;}
dist[i] = 0;
for (ll z = 1;z <= n;z ++){
ll u = 0;
for (ll j = 1;j <= n;j ++){
if (!used[j] && (!u || dist[j] < dist[u]))u=j;
}
used[u] = 1;
for (ll v = 1;v <= n;v ++){
if (used[v])continue;
if (c[u][v] == 0)continue;
// if (i == 1 && u == 3)cout<<v<<endl;
ll x = dist[u]%s;
ll w;
if (x + l[u][v] > c[u][v])w = dist[u]+s-x+l[u][v];
else w = dist[u]+l[u][v];
dist[v] = min(dist[v],w);
}
}
for (ll j = 1;j <= n;j ++)pre[j][i] = dist[j];
}
// cout<<l[3][4]<<' '<<c[3][4]<<endl;
// for (ll i = 1;i <= n;i ++)for (ll j = 1;j <= n;j ++)cout<<pre[i][j]<<" \n"[j==n];
for (ll i = 1,ptr = 0;i <= n;i ++){
vector <query> cur_query;
while (ptr<sz(all_query)&&all_query[ptr].u==i){
cur_query.push_back(all_query[ptr]);
ptr++;
}
sort(cur_query.begin(),cur_query.end(),[&](query x,query y){return x.t < y.t;});
// for (auto x:cur_query){
// cout<<x.u<<' '<<x.v<<' '<<x.t<<endl;
// }
ll ptr_cur=0;
ll st = 0;
while (1){
// cout<<st<<endl;
for (ll j = 1;j <= n;j ++){
dist[j] = INF;
used[j] = 0;
}
dist[i] = st;
ll range = INF;
for (ll j = 1;j <= n;j ++){
ll u = 0;
for (ll k = 1;k <= n;k ++){
if (!used[k]&&(!u || dist[k]<dist[u]))u=k;
}
used[u] = 1;
if (dist[u]==INF)break;
if (u != i)range = min(range,last_c[u] - dist[u]);
for (ll v = 1;v <= n;v ++){
if (!used[v] && c[u][v]){
if (dist[u] + l[u][v] <= min(dist[v],c[u][v])){
last_c[v] = c[u][v];
dist[v] = dist[u] + l[u][v];
}
}
}
}
while (ptr_cur<sz(cur_query)&&cur_query[ptr_cur].t <= st+range){
ll u,v,t,id,res=INF;
query x = cur_query[ptr_cur];
tie(u,v,t,id) = tie(x.u,x.v,x.t,x.id);
if (dist[v]!=INF)res = dist[v]-st;
else{
for (ll k = 1;k <= n;k ++){
if (dist[k] != INF){
res = min(res,pre[v][k]+s-t);
}
}
}
ans[id]=res;
ptr_cur++;
}
if (range==INF)break;
// cout<<range<<endl;
st+=range+1;
}
}
}
}
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) {
n = N,m = M,s = S,q = Q;
for (ll i = 1;i <= n;i ++){
for (ll j = 1;j <= n;j ++){
c[i][j] = 0;
l[i][j] = 1;
}
}
for (ll i = 0;i < m;i ++){
ll u,v;
u = A[i]+1,v = B[i]+1;
c[u][v] = c[v][u] = C[i];
l[u][v] = l[v][u] = L[i];
}
for (ll i = 0;i < q;i ++){
all_query.push_back({U[i]+1,V[i]+1,T[i],i});
}
solve();
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... |