| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 590868 |
2022-07-06T12:30:45 Z |
8e7 |
Sky Walking (IOI19_walk) |
C++17 |
|
223 ms |
124012 KB |
//Challenge: Accepted
#include "walk.h"
#include <bits/stdc++.h>
using namespace std;
#ifdef zisk
void debug(){cout << endl;}
template<class T, class ... U> void debug(T a, U ... b){cout << a << " ", debug(b...);}
template<class T> void pary(T l, T r) {
while (l != r)cout << *l << " ", l++;
cout << endl;
}
#else
#define debug(...) 0
#define pary(...) 0
#endif
#define ll long long
#define maxn 100005
#define maxv 500005
#define pii pair<ll, ll>
#define ff first
#define ss second
const ll inf = 1LL<<60;
vector<pii> adj[maxv];
ll dis[maxv];
int prv[maxn], px[maxn];
vector<int> lft[maxn], rht[maxn];
bool on[maxn];
long long min_distance(vector<int> X, vector<int> H, vector<int> L, vector<int> R, vector<int> Y, int st, int ed) {
int n = X.size(), m = L.size();
set<pii> se;
for (int i = 0;i < m;i++) {
lft[L[i]].push_back(i);
rht[R[i]].push_back(i);
}
auto addedge = [&] (int u, int v, int w){
adj[u].push_back({v, w});
adj[v].push_back({u, w});
debug(u, v, w);
};
int term = maxv - 1;
{
int cur = 1;
for (int i = 0;i < n;i++) {
vector<int> ev = lft[i];
ev.insert(ev.end(), rht[i].begin(), rht[i].end());
for (int id:ev) {
int y = Y[id], node = cur++;
if (on[id]) {
if (i == n - 1) addedge(node, term, y);
se.erase(se.find(make_pair(y, id)));
debug("end");
addedge(node, prv[id], X[i] - px[id]);
}
auto it = se.lower_bound(make_pair(y, id));
if (it != se.end()) {
addedge(cur, prv[it->ss], X[i] - px[it->ss]);
prv[it->ss] = cur;
px[it->ss] = X[i];
addedge(node, cur++, abs(y - it->ff));
}
if (it != se.begin()) {
it = prev(it);
addedge(cur, prv[it->ss], X[i] - px[it->ss]);
prv[it->ss] = cur;
px[it->ss] = X[i];
addedge(node, cur++, abs(y - it->ff));
}
if (!on[id]) {
if (i == 0) addedge(node, 0, y);
se.insert(make_pair(y, id));
prv[id] = node;
px[id] = X[i];
on[id] = 1;
}
}
}
}
for (int i = 0;i < maxv;i++) dis[i] = inf;
dis[0] = 0;
priority_queue<pii, vector<pii>, greater<pii> > pq;
pq.push({0, 0});
while (pq.size()) {
auto [d, cur] = pq.top();
pq.pop();
if (d != dis[cur]) continue;
for (auto [v, w]:adj[cur]) {
if (d + w < dis[v]) {
dis[v] = d + w;
pq.push({dis[v], v});
}
}
}
if (dis[term] == inf) return -1;
return dis[term];
}
Compilation message
walk.cpp: In lambda function:
walk.cpp:13:20: warning: statement has no effect [-Wunused-value]
13 | #define debug(...) 0
| ^
walk.cpp:38:3: note: in expansion of macro 'debug'
38 | debug(u, v, w);
| ^~~~~
walk.cpp: In function 'long long int min_distance(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, int, int)':
walk.cpp:13:20: warning: statement has no effect [-Wunused-value]
13 | #define debug(...) 0
| ^
walk.cpp:52:6: note: in expansion of macro 'debug'
52 | debug("end");
| ^~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
20588 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
20544 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
94 ms |
44364 KB |
Output is correct |
| 2 |
Runtime error |
223 ms |
124012 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
94 ms |
44364 KB |
Output is correct |
| 2 |
Runtime error |
223 ms |
124012 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
20588 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
