#include <bits/stdc++.h>
using namespace std;
const int MN = 60 + 1;
long long pre[MN][MN*MN][MN], stop[MN][MN];
vector<long long> times[MN];
long long adj[MN][MN], bad[MN][MN];
bool vis[MN];
vector<long long> calculate_necessary_time (int n, int m, long long s, int q, vector<int> a, vector<int> b, vector<long long> l, vector<long long> c, vector<int> u, vector<int> v, vector<long long> T) {
memset(adj,0x3f,sizeof adj);
for (int i = 0; i < m; i++) {
adj[++a[i]][++b[i]] = l[i];
adj[b[i]][a[i]] = l[i];
bad[a[i]][b[i]] = bad[b[i]][a[i]] = c[i];
}
for (int st = 1; st <= n; st++) {
memset(stop[st],0x3f,sizeof stop[st]); memset(vis,0,sizeof vis);
stop[st][st] = 0;
for (int iter = 0; iter < n; iter++) {
int mn = -1;
for (int i = 1; i <= n; i++) if (!vis[i] && (mn == -1 || stop[st][i] < stop[st][mn])) mn = i;
if (mn == -1 || stop[st][mn] > 1e18) break;
vis[mn] = true;
for (int i = 1; i <= n; i++) if (adj[mn][i] < 1e18) {
long long att = stop[st][mn];
if (att%s <= bad[mn][i] - adj[mn][i]) att += adj[mn][i];
else att += (s - att%s) + adj[mn][i];
stop[st][i] = min(stop[st][i],att);
}
}
}
for (int st = 1; st <= n; st++) { //no stop all go
times[st].push_back(0);
for (int id = 0; id < (int)times[st].size(); id++) {
long long t = times[st][id];
memset(pre[st][id],0x3f,sizeof pre[st][id]);
memset(vis,0,sizeof vis);
pre[st][id][st] = t;
auto fix = [&] (long long x) {while (x >= s) x -= s; return x;};
for (int iter = 0; iter < n; iter++) {
int mn = -1;
for (int i = 1; i <= n; i++) if (!vis[i] && (mn == -1 || pre[st][id][i] < pre[st][id][mn])) mn = i;
if (mn == -1 || pre[st][id][mn] > 1e18) break;
vis[mn] = true;
for (int i = 1; i <= n; i++) if (adj[mn][i] < 1e18) {
long long att = pre[st][id][mn];
if (fix(att) <= bad[mn][i] - adj[mn][i]) att += adj[mn][i];
else continue; //no stop
pre[st][id][i] = min(pre[st][id][i],att);
}
}
long long nextTime = 1e18 + 5;
for (int i = 1; i <= n; i++) {
long long md = pre[st][id][i]%s;
for (int j = 1; j <= n; j++) if (pre[st][id][i] < 1e18 && md <= bad[i][j] - adj[i][j]) {
nextTime = min(nextTime,bad[i][j] - adj[i][j] + 1 - md + t);
}
}
if (nextTime < s) times[st].push_back(nextTime);
}
}
vector<long long> ret(q);
for (int i = 0; i < q; i++) {
++u[i]; ++v[i];
int id = upper_bound(times[u[i]].begin(),times[u[i]].end(),T[i]) - times[u[i]].begin() - 1;
long long t = times[u[i]][id];
ret[i] = pre[u[i]][id][v[i]] - t;
for (int ed = 1; ed <= n; ed++) {
long long att = pre[u[i]][id][ed] + T[i] - t;
att = att > s ? 2 * s : s;
ret[i] = min(ret[i],att+stop[ed][v[i]]-T[i]);
}
}
return ret;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
30 ms |
65016 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1802 ms |
132024 KB |
Output is correct |
| 2 |
Correct |
1769 ms |
148388 KB |
Output is correct |
| 3 |
Correct |
1761 ms |
138480 KB |
Output is correct |
| 4 |
Correct |
1919 ms |
149760 KB |
Output is correct |
| 5 |
Correct |
1912 ms |
149316 KB |
Output is correct |
| 6 |
Incorrect |
28 ms |
64972 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
30 ms |
65016 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
30 ms |
65016 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
30 ms |
65016 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
