#include <bits/stdc++.h>
#include "escape_route.h"
using namespace std;
#ifdef MIKU
string dbmc = "\033[1;38;2;57;197;187m", dbrs = "\033[0m";
#define debug(x...) cout << dbmc << "[" << #x << "]: ", dout(x)
void dout() { cout << dbrs << endl; }
template <typename T, typename ...U>
void dout(T t, U ...u) { cout << t << (sizeof...(u) ? ", " : ""); dout(u...); }
#else
#define debug(...) 39
#endif
#define fs first
#define sc second
#define mp make_pair
#define FOR(i, j, k) for (int i = j, Z = k; i < Z; i++)
using ll = long long;
typedef pair<int, int> pii;
typedef pair<int, ll> pil;
typedef pair<ll, int> pli;
typedef pair<ll, ll> pll;
namespace {
const int MXN = 95;
const ll INF = 3.9e18;
int n, m, q;
ll s;
vector<int> eu, ev, qu, qv;
vector<ll> elt, ect, qt;
vector<ll> ans;
ll el[MXN][MXN], ec[MXN][MXN];
ll dis[MXN][MXN];
ll dp[MXN][MXN][MXN];
namespace SPFA {
vector<pli> rnk[MXN];
struct CPU {
deque<pair<ll, vector<ll>>> dq;
deque<pli> num;
int ptr[MXN], span[MXN];
vector<ll> a;
ll init(int sr) {
a.resize(n, INF);
a[sr] = 0;
fill(ptr, ptr + n, 0);
dq.push_back(mp(s, a));
return rnk[sr][0].fs;
}
vector<ll> GET(ll t) {
return lower_bound(dq.begin(), dq.end(), mp(t, vector<ll>())) -> sc;
}
void TIDY() {
vector<pii> v(n);
FOR(i, 0, n) v[i] = mp(0, i);
for (auto [t, w] : dq) {
int cnt = n;
FOR(i, 0, n) if (w[i] >= INF) {
v[i].fs++;
cnt--;
}
num.push_back(mp(t, cnt));
}
sort(v.begin(), v.end());
FOR(i, 0, n) span[i] = v[i].sc;
}
} cpu[MXN];
ll time[MXN];
void GET_RNK(int id) {
vector<pli> &dist = rnk[id];
FOR(i, 0, n + 1) dist.push_back(mp(ec[id][i] - el[id][i], i));
sort(dist.begin(), dist.end(), greater<pli>());
}
void PRE() {
FOR(i, 0, n) GET_RNK(i);
FOR(i, 0, n) time[i] = cpu[i].init(i);
}
void RELAX(int id, ll t) {
while (true) {
ll big = -INF;
bool found = false;
FOR(i, 0, n) {
int &e = cpu[id].ptr[i];
ll len = cpu[id].a[i];
if (t + len <= rnk[i][e].fs) {
int j = rnk[i][e].sc;
vector<ll> d = cpu[j].GET(t + len + el[i][j]);
FOR(k, 0, n) cpu[id].a[k] = min(cpu[id].a[k], len + el[i][j] + d[k]);
found = true;
e++;
break;
}
big = max(big, rnk[i][e].fs - cpu[id].a[i]);
}
if (found) continue;
time[id] = big;
debug(big);
break;
}
cpu[id].dq.push_front(mp(t, cpu[id].a));
}
void DO() {
PRE();
while (true) {
auto it = max_element(time, time + n);
if (*it < 0) break;
RELAX(it - time, *it);
}
FOR(i, 0, n) cpu[i].TIDY();
FOR(i, 0, n) {
cout << i << ": " << endl;
FOR(j, 0, n) cout << cpu[i].span[j] << ' ';
cout << endl << endl;
}
}
}
void DIJKSTRA(int sr, ll *dis) {
bitset<MXN> b;
fill(dis, dis + n, INF);
dis[sr] = 0;
b.reset();
FOR($, 0, n) {
int id = -1;
FOR(i, 0, n) {
if (b[i]) continue;
if (id == -1 || dis[i] < dis[id]) id = i;
}
b[id] = true;
ll t = dis[id] % s, day = dis[id] / s;
FOR(i, 0, n) {
if (b[i]) continue;
if (t + el[id][i] <= ec[id][i]) {
dis[i] = min(dis[i], dis[id] + el[id][i]);
} else {
dis[i] = min(dis[i], s * (day + 1) + el[id][i]);
}
if (sr == 4) debug(id, i, dis[i]);
}
}
}
void PRE() {
SPFA::DO();
FOR(i, 0, n) DIJKSTRA(i, dis[i]);
FOR(id, 0, n) {
fill(dp[id][0], dp[id][0] + n, INF);
FOR(j, 0, n) {
int y = SPFA::cpu[id].span[j];
FOR(k, 0, n) {
dp[id][j + 1][k] = min(dp[id][j][k], dis[y][k]);
}
}
}
}
ll query(int u, int v, ll t) {
debug(u, v, t);
vector<ll> w = SPFA::cpu[u].GET(t);
for (auto &i : w) cout << i << ' ';
cout << endl;
if (w[v] != INF) return w[v];
int x = lower_bound(SPFA::cpu[u].num.begin(), SPFA::cpu[u].num.end(), mp(t, 0)) -> sc;
return s - t + dp[u][x][v];
}
vector<ll> solve() {
FOR(i, 0, n) FOR(j, 0, n + 1) {
el[i][j] = INF;
ec[i][j] = 0;
}
FOR(i, 0, m) {
el[eu[i]][ev[i]] = elt[i];
ec[eu[i]][ev[i]] = ect[i];
el[ev[i]][eu[i]] = elt[i];
ec[ev[i]][eu[i]] = ect[i];
}
PRE();
FOR(i, 0, q) ans.push_back(query(qu[i], qv[i], qt[i]));
FOR(i, 0, n) cout << dis[4][i] << ' ';
cout << endl;
return ans;
}
}
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;
::eu = A;
::ev = B;
::elt = L;
::ect = C;
::qu = U;
::qv = V;
::qt = T;
return solve();
}
Compilation message
escape_route.cpp: In function 'void {anonymous}::SPFA::RELAX(int, ll)':
escape_route.cpp:12:20: warning: statement has no effect [-Wunused-value]
12 | #define debug(...) 39
| ^~
escape_route.cpp:100:5: note: in expansion of macro 'debug'
100 | debug(big);
| ^~~~~
escape_route.cpp: In function 'void {anonymous}::DIJKSTRA(int, ll*)':
escape_route.cpp:12:20: warning: statement has no effect [-Wunused-value]
12 | #define debug(...) 39
| ^~
escape_route.cpp:141:18: note: in expansion of macro 'debug'
141 | if (sr == 4) debug(id, i, dis[i]);
| ^~~~~
escape_route.cpp: In function 'll {anonymous}::query(int, int, ll)':
escape_route.cpp:12:20: warning: statement has no effect [-Wunused-value]
12 | #define debug(...) 39
| ^~
escape_route.cpp:159:3: note: in expansion of macro 'debug'
159 | debug(u, v, t);
| ^~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
17 ms |
65396 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
9019 ms |
709396 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
17 ms |
65396 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
17 ms |
65396 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
17 ms |
65396 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
