#include<bits/stdc++.h>
#include "escape_route.h"
using namespace std;
typedef long long llint;
typedef pair <llint, llint> pi;
typedef vector <int> Vi;
typedef vector <llint> vi;
const int MAXN = 91;
const int MAXM = 91 * 91;
const llint INF = 1000000000000000000LL;
llint n, m, s, q, br;
llint len[MAXM], c[MAXM];
llint path[MAXN][MAXN], bio[MAXN][MAXN];
vector <pi> v[MAXN];
int p[MAXN][MAXN];
int best[MAXN], siz[MAXN];
llint dist[MAXN][MAXN][MAXN * MAXN], best_val[MAXN];
vi times[MAXN];
void dijkstra (int root) {
for (int i = 0; i < n; i++) {
path[root][i] = INF;
}
path[root][root] = 0;
for (int i = 0; i < n; i++) {
llint mn = INF, ind = -1;
for (int j = 0; j < n; j++) {
if (bio[root][j] == 0 && path[root][j] < mn) {
mn = path[root][j];
ind = j;
}
}
bio[root][ind] = 1;
for (auto pp : v[ind]) {
int sus = pp.first, e = pp.second;
llint novi = path[root][ind] + len[e];
if (path[root][ind] % s <= c[e] - len[e]) {
path[root][sus] = min(path[root][sus], novi);
}
novi += s - path[root][ind] % s;
path[root][sus] = min(path[root][sus], novi);
}
}
}
void init () {
for (int i = 0; i < n; i++) {
times[i].push_back(-(s - 1));
siz[i] = 1;
for (int j = 0; j < n; j++) {
dist[i][j][0] = INF;
p[i][j] = (int)v[j].size() - 1;
}
dist[i][i][0] = s - 1;
best[i] = i;
int e = v[i].back().second;
best_val[i] = (s - 1) - (c[e] - len[e]);
}
}
int get_best_root () {
llint mn = INF, ind = -1;
for (int i = 0; i < n; i++) {
if (best_val[i] < mn) {
mn = best_val[i];
ind = i;
}
}
return ind;
}
void upd_dist (int root, int node, llint d) {
//if (br <= 100) cout << "upd_dist " << root << " " << node << " " << d << endl;
int ind = upper_bound(times[node].begin(), times[node].end(), -d) - times[node].begin() - 1;
llint curr_x = -times[node][ind];
for (int i = 0; i < n; i++) {
if (dist[node][i][ind] == INF) continue;
llint val = dist[node][i][ind] - curr_x + d;
dist[root][i][siz[root]] = min(dist[root][i][siz[root]], val);
}
}
bool upd_best (int root) {
llint mn = INF, ind = -1;
bool smanjio = 0;
for (int i = 0; i < n; i++) {
llint val = dist[root][i][siz[root]];
if (val == INF) continue;
while (p[root][i] >= 0) {
int sus = v[i][p[root][i]].first;
int e = v[i][p[root][i]].second;
if (val > c[e] - len[e]) {
if (val - (c[e] - len[e]) < mn) {
mn = val - (c[e] - len[e]);
ind = i;
}
break;
}
upd_dist(root, sus, dist[root][i][siz[root]] + len[e]);
p[root][i]--;
smanjio = 1;
}
}
best[root] = ind;
best_val[root] = mn;
return smanjio;
}
void ispis (int root, int ind) {
cout << "ispis " << root << endl;
for (int i = 0; i < n; i++) {
cout << "bla " << i << " " << dist[root][i][ind] << endl;
}
cout << endl;
}
void calc () {
while (1) {
br++;
int root = get_best_root();
if (root == -1) break;
int node = best[root];
//if (br <= 100) cout << "sad na " << root << " " << node << endl;
int sus = v[node][p[root][node]].first;
int e = v[node][p[root][node]].second;
llint del = dist[root][node][siz[root] - 1] - (c[e] - len[e]);
for (int i = 0; i < n; i++) {
if (dist[root][i][siz[root] - 1] != INF) {
dist[root][i][siz[root]] = dist[root][i][siz[root] - 1] - del;
} else {
dist[root][i][siz[root]] = INF;
}
}
while (upd_best(root));
times[root].push_back(-dist[root][root][siz[root]]);
siz[root]++;
//if (br <= 100) ispis(root);
}
/*for (int i = 0; i < n; i++) {
cout << "bla " << i << " ";
for (auto t : times[i]) cout << t << " "; cout << endl;
}*/
//ispis(0, 2);
}
bool cmp (pi a, pi b) {
int ia = a.second, ib = b.second;
return c[ia] - len[ia] < c[ib] - len[ib];
}
llint upit (int root, int node, llint d) {
int ind = upper_bound(times[root].begin(), times[root].end(), -d) - times[root].begin() - 1;
llint curr_x = -times[root][ind];
if (dist[root][node][ind] != INF) {
return dist[root][node][ind] - curr_x;
} else {
llint res = INF;
for (int i = 0; i < n; i++) {
if (dist[root][i][ind] != INF) {
res = min(res, s + path[i][node]);
}
}
return res - d;
}
}
vi calculate_necessary_time (int N, int M, llint S, int Q,
Vi A, Vi B, vi L, vi C, Vi U, Vi V, vi T) {
n = N; m = M; s = S; q = Q;
for (int i = 0; i < m; i++) {
len[i] = L[i];
c[i] = C[i];
v[A[i]].push_back({B[i], i});
v[B[i]].push_back({A[i], i});
}
for (int i = 0; i < n; i++) {
sort(v[i].begin(), v[i].end(), cmp);
}
init();
calc();
for (int i = 0; i < n; i++) dijkstra(i);
vi sol;
for (int i = 0; i < q; i++) {
sol.push_back(upit(U[i], V[i], T[i]));
}
return sol;
}
Compilation message
escape_route.cpp: In function 'void calc()':
escape_route.cpp:130:7: warning: unused variable 'sus' [-Wunused-variable]
130 | int sus = v[node][p[root][node]].first;
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
46 ms |
65024 KB |
Output is correct |
| 2 |
Incorrect |
59 ms |
65000 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
635 ms |
130264 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
46 ms |
65024 KB |
Output is correct |
| 2 |
Incorrect |
59 ms |
65000 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
46 ms |
65024 KB |
Output is correct |
| 2 |
Incorrect |
59 ms |
65000 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
46 ms |
65024 KB |
Output is correct |
| 2 |
Incorrect |
59 ms |
65000 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
