#include "walk.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
#define pii pair<int, int>
#define f first
#define s second
#define vi vector<int>
#define int long long
#define size(x) (int)((x).size())
const int inf = 1e18;
const int siz = 5e6+40;
int dist [siz];
struct Compare {
bool operator()(int a, int b) {
return (dist[a] > dist[b]);
}
};
int min_distance(std::vector<signed> pos, std::vector<signed> heightOf, std::vector<signed> leftP, std::vector<signed> rightP, std::vector<signed> yLevel, signed oriX, signed tarX) {
leftP.push_back(oriX);
rightP.push_back(oriX);
yLevel.push_back(0);
leftP.push_back(tarX);
rightP.push_back(tarX);
yLevel.push_back(0);
const int n = size(pos);
const int nbP = size(leftP);
vector<pii> insAt [n];
vector<pii> remAt [n];
for (int i = 0; i < nbP; i++) {
insAt[leftP[i]].push_back({yLevel[i], i});
remAt[rightP[i]].push_back({yLevel[i], i});
}
vi cut [n];
set<pii> se;
for (int i = 0; i < n; i++) {
for (pii j : insAt[i]) {
se.insert(j);
}
for (auto j = se.begin(); j != se.end(); j = next(j)) {
if (j->f > heightOf[i]) {
break;
}
cut[i].push_back(j->s);
}
for (pii j : remAt[i]) {
se.erase(j);
}
}
set<pii> possNodes;
for (int i = 0; i < n; i++) {
for (int j : cut[i]) possNodes.insert({i, yLevel[j]});
}
map<pii, int> compress;
int cnt = 0;
for (auto i : possNodes) compress[i] = cnt++;
vi inter [nbP];
for (int i = 0; i < n; i++) {
for (int j = 0; j < size(cut[i]); j++) {
inter[cut[i][j]].push_back(i);
}
}
vector<pair<pii, int>> e;
for (int i = 0; i < n; i++) {
vi loc;
for (int j : cut[i]) {
loc.push_back(yLevel[j]);
}
sort(loc.begin(), loc.end());
for (int j = 0; j < size(loc)-1; j++) {
e.push_back({{compress[{i, loc[j]}], compress[{i, loc[j+1]}]}, loc[j+1]-loc[j]});
}
}
for (int i = 0; i < nbP; i++) {
assert(size(inter[i]) >= 1);
for (int j = 0; j < size(inter[i])-1; j++) {
e.push_back({{compress[{inter[i][j], yLevel[i]}], compress[{inter[i][j+1], yLevel[i]}]}, pos[inter[i][j+1]]-pos[inter[i][j]]});
}
}
vector<pii> graph [size(compress)];
for (auto i : e) {
assert(i.s >= 0);
graph[i.f.f].push_back({i.f.s, i.s});
graph[i.f.s].push_back({i.f.f, i.s});
}
priority_queue<int, vector<int>, Compare> q;
for (int i = 0; i < size(compress); i++) dist[i] = inf;
dist[compress[{oriX, 0}]] = 0;
q.push(compress[{oriX, 0}]);
bool vis [size(compress)];
for (int i = 0; i < size(compress); i++) vis[i] = false;
while (!q.empty()) {
int x = q.top();
q.pop();
if (vis[x]) continue;
vis[x] = true;
for (pii e : graph[x]) {
int nd = dist[x]+e.s;
if (nd < dist[e.f]) {
dist[e.f] = nd;
q.push(e.f);
}
}
}
int tarXEncoded = compress[{tarX, 0}];
int res = dist[tarXEncoded];
return res;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
1966 ms |
231228 KB |
Output is correct |
4 |
Incorrect |
1625 ms |
234856 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
170 ms |
30920 KB |
Output is correct |
2 |
Execution timed out |
4078 ms |
852508 KB |
Time limit exceeded |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
170 ms |
30920 KB |
Output is correct |
2 |
Execution timed out |
4078 ms |
852508 KB |
Time limit exceeded |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |