#include "escape_route.h"
#include<bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
#define mp make_pair
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef long double ld;
template <typename T> bool chkmin(T &x,T y){return x>y?x=y,1:0;}
template <typename T> bool chkmax(T &x,T y){return x<y?x=y,1:0;}
ll readint(){
ll x=0,f=1; char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
const ll inf=(ll)1e18;
int n,tot;
int v[100005],nxt[100005],h[95];
ll s,c[100005],b[100005],res[3000005];
vector<pair<ll,int>> qs[95][95];
pair<ll,ll> d[95];
void addedge(int x,int y,ll w,ll t){
v[++tot]=y; c[tot]=w; b[tot]=t; nxt[tot]=h[x]; h[x]=tot;
v[++tot]=x; c[tot]=w; b[tot]=t; nxt[tot]=h[y]; h[y]=tot;
}
pair<ll,ll> dijkstra(int u,int v,ll t){
for(int i=0;i<n;i++) d[i]=mp(inf,0ll);
d[u]=mp(0,t);
set<pair<pair<ll,ll>,int>> st;
st.emplace(mp(d[u],u));
while(!st.empty()){
auto it=st.begin();
int x=it->se;
st.erase(it);
for(int p=h[x];p;p=nxt[p]){
pair<ll,ll> nd;
if(d[x].se+c[p]<=b[p]){
nd.fi=d[x].fi;
nd.se=d[x].se+c[p];
}else{
nd.fi=d[x].fi+1;
nd.se=c[p];
}
if(nd<d[::v[p]]){
if(d[::v[p]].fi!=inf) st.erase(st.find(mp(d[::v[p]],::v[p])));
d[::v[p]]=nd;
st.insert(mp(d[::v[p]],::v[p]));
}
}
}
return d[v];
}
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){
n=N; s=S;
for(int i=0;i<M;i++) addedge(A[i],B[i],L[i],C[i]);
for(int i=0;i<Q;i++){
qs[U[i]][V[i]].pb(mp(T[i],i));
}
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
sort(qs[i][j].begin(),qs[i][j].end());
int sz=(int)qs[i][j].size();
for(int k=0;k<sz;k++){
int l=k+1,r=sz-1,p=k;
pair<ll,ll> tm=dijkstra(i,j,qs[i][j][k].fi);
while(l<=r){
int mid=(l+r)/2;
pair<ll,ll> tmp=dijkstra(i,j,qs[i][j][mid].fi);
if(tmp.fi==tm.fi&&tmp.se-tm.se==qs[i][j][mid].fi-qs[i][j][k].fi) p=mid,l=mid+1;
else r=mid-1;
}
for(int f=k;f<=p;f++) res[qs[i][j][k].se]=tm.fi*s+tm.se+(qs[i][j][f].fi-qs[i][j][k].fi)-qs[i][j][f].fi;
k=p;
}
}
}
vector<ll> ret;
for(int i=0;i<Q;i++) ret.pb(res[i]);
return ret;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
14 ms |
67420 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
9069 ms |
153304 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
14 ms |
67420 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
14 ms |
67420 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
14 ms |
67420 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
