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>
#define ll long long
#define pii pair<ll, ll>
const ll inf = 1e18;
const int mxn = 3e5 + 5;
using namespace std;
vector<int> adj[mxn];
int n, m;
ll s, q;
int l[mxn], r[mxn];
ll c[mxn], w[mxn];
ll q_t[mxn];
int block[mxn] = {};
void dijkstra1(int source, pii *dist) {
int vis[n + 1] = {};
for(int i = 0; i < n; i++) dist[i] = {inf, inf};
dist[source] = {0, 0};
for(int i = 0; i < n; i++) {
int u = -1;
pii cur = {inf, inf};
for(int j = 0; j < n; j++) {
if(vis[j]) continue;
if(dist[j] < cur) {
cur = dist[j];
u = j;
}
}
if(u == -1) break;
vis[u] = 1;
ll T = dist[u].second;
ll d = dist[u].first;
for(int i : adj[u]) {
int v = l[i] ^ r[i] ^ u;
if(T + w[i] <= c[i]) {
if(dist[v] > make_pair(d, T + w[i])) {
dist[v] = make_pair(d, T + w[i]);
}
}
dist[v] = min(dist[v], {d + 1, w[i]});
}
}
}
pii dijkstra2(int source, ll *dist) {
int vis[n + 1] = {};
for(int i = 0; i < n; i++) dist[i] = inf;
dist[source] = 0;
ll mn = inf;
int m_id = -1;
for(int i = 0; i < n; i++) {
int u = -1;
ll cur = inf;
for(int j = 0; j < n; j++) {
if(vis[j]) continue;
if(dist[j] < cur) {
cur = dist[j];
u = j;
}
}
if(u == -1) break;
vis[u] = 1;
ll d = dist[u];
for(int i : adj[u]) {
if(block[i]) continue;
int v = l[i] ^ r[i] ^ u;
if(d + w[i] <= c[i]) {
if(dist[v] > d + w[i]) {
dist[v] = d + w[i];
if(c[i] - dist[v] < mn) {
mn = c[i] - dist[v];
m_id = i;
}
}
}
}
}
return {mn, m_id};
}
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;
m = M;
s = S;
q = Q;
for(int i = 0; i < M; i++) {
adj[A[i]].push_back(i);
adj[B[i]].push_back(i);
l[i] = A[i];
r[i] = B[i];
c[i] = C[i];
w[i] = L[i];
}
for(int i = 0; i < Q; i++) q_t[i] = T[i];
pii w0[n][n];
for(int i = 0; i < n; i++) dijkstra1(i, w0[i]);
vector<ll> res(Q);
vector<int> ord(Q);
iota(ord.begin(), ord.end(), 0);
sort(ord.begin(), ord.end(), [](int a, int b) {
return q_t[a] < q_t[b];
});
ll D[n];
auto [mn, id] = dijkstra2(0, D);
for(int i : ord) {
while(mn < T[i]) {
block[id] = 1;
auto [x, y] = dijkstra2(0, D);
mn = x;
id = y;
}
if(D[V[i]] != inf) res[i] = D[V[i]];
else {
res[i] = inf;
for(int j = 0; j < n; j++) {
if(D[j] != inf) res[i] = min(res[i], S + w0[j][V[i]].first * S + w0[j][V[i]].second);
}
}
}
return res;
}
# | 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... |