# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
144441 |
2019-08-16T21:26:05 Z |
qkxwsm |
Sky Walking (IOI19_walk) |
C++14 |
|
1930 ms |
600652 KB |
#include "walk.h"
#include <bits/stdc++.h>
using namespace std;
template<class T, class U>
void ckmin(T &a, U b)
{
if (a > b) a = b;
}
template<class T, class U>
void ckmax(T &a, U b)
{
if (a < b) a = b;
}
#define MP make_pair
#define PB push_back
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
#define FOR(i, a, b) for (auto i = (a); i < (b); i++)
#define FORD(i, a, b) for (auto i = (a) - 1; i >= (b); i--)
#define SZ(x) ((int) (x).size())
#define ALL(x) (x).begin(), (x).end()
#define MAXN 2000013
#define INF 1000000007
#define LLINF 2696969696969696969
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpi;
typedef vector<pll> vpl;
int N, M, S, T, V;
pll arr[MAXN];
vpl edge[MAXN];
vpl edge1[MAXN];
vl hs[MAXN];
vector<array<ll, 3> > events;
set<int> s;
int st[MAXN];
ll dist[MAXN];
ll ans;
ll dijkstra()
{
S = st[S]; T = st[T];
priority_queue<pll, vector<pll>, greater<pll> > q;
FOR(i, 0, V) dist[i] = LLINF;
// FOR(i, 0, V)
// {
// for (auto e : edge1[i])
// {
// cerr << i << " -> " << e.se << " len " << e.fi << endl;
// }
// }
dist[S] = 0; q.push({0, S});
while(!q.empty())
{
ll d = q.top().fi; int u = q.top().se; q.pop();
if (u == T) break;
if (d != dist[u]) continue;
for (auto e : edge1[u])
{
ll nd = d + e.fi; int v = e.se;
if (dist[v] > nd)
{
dist[v] = nd;
q.push({nd, v});
}
}
}
return dist[T];
}
ll min_distance(vi x, vi h, vi l, vi r, vi y, int source, int sink)
{
N = SZ(x);
FOR(i, 0, N)
{
arr[i] = {x[i], h[i]};
}
M = SZ(y);
FOR(i, 0, M)
{
int u = l[i], v = r[i]; ll h = y[i];
edge[u].PB({h, v});
edge[v].PB({h, u});
}
S = source; T = sink;
FOR(i, 0, N)
{
events.PB({arr[i].se, INF, i});
for (auto p : edge[i])
{
if (p.se < i) continue;
events.PB({p.fi, i, p.se});
}
hs[i].PB(0);
hs[i].PB(arr[i].se);
}
sort(ALL(events));
reverse(ALL(events));
FOR(i, 0, SZ(events))
{
auto e = events[i];
if (e[1] == INF)
{
s.insert(e[2]); continue;
}
else
{
int u = e[1], v = e[2];
// cerr << u << " -> " << v << endl;
for (auto it = s.UB(u); *it != v; it++)
{
hs[*it].PB(e[0]);
}
hs[u].PB(e[0]);
hs[v].PB(e[0]);
}
}
FOR(i, 0, N)
{
sort(ALL(hs[i]));
hs[i].erase(unique(ALL(hs[i])), hs[i].end());
st[i] = V;
V += SZ(hs[i]);
// cerr << "X COOR " << arr[i].fi << endl;
// for (int x : hs[i])
// {
// cerr << x << ' ';
// }
// cerr << endl;
// cerr << "ST " << i << " = " << st[i] << endl;
}
// cerr << "V = " << V << endl;
st[N] = V;
FOR(i, 0, N)
{
FOR(j, st[i], st[i + 1] - 1)
{
ll dy = hs[i][j + 1 - st[i]] - hs[i][j - st[i]];
edge1[j].PB({dy, j + 1});
edge1[j + 1].PB({dy, j});
}
}
s.clear();
FOR(i, 0, SZ(events))
{
auto e = events[i]; ll h = e[0];
if (e[1] == INF)
{
s.insert(e[2]); continue;
}
else
{
int u = e[1], v = e[2];
for (auto it = s.LB(u); *it != v; it++)
{
int x = *it, y = *(next(it));
int idx = st[x] + LB(ALL(hs[x]), h) - hs[x].begin();
int idy = st[y] + LB(ALL(hs[y]), h) - hs[y].begin();
edge1[idx].PB({arr[y].fi - arr[x].fi, idy});
edge1[idy].PB({arr[y].fi - arr[x].fi, idx});
}
}
}
ans = dijkstra();
if (ans >= LLINF) return -1;
return ans;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
132 ms |
141304 KB |
Output is correct |
2 |
Correct |
132 ms |
141304 KB |
Output is correct |
3 |
Correct |
133 ms |
141192 KB |
Output is correct |
4 |
Correct |
132 ms |
141304 KB |
Output is correct |
5 |
Correct |
132 ms |
141288 KB |
Output is correct |
6 |
Correct |
133 ms |
141272 KB |
Output is correct |
7 |
Correct |
132 ms |
141292 KB |
Output is correct |
8 |
Correct |
134 ms |
141304 KB |
Output is correct |
9 |
Correct |
131 ms |
141304 KB |
Output is correct |
10 |
Correct |
149 ms |
141432 KB |
Output is correct |
11 |
Correct |
131 ms |
141304 KB |
Output is correct |
12 |
Correct |
131 ms |
141220 KB |
Output is correct |
13 |
Correct |
131 ms |
141212 KB |
Output is correct |
14 |
Correct |
154 ms |
141304 KB |
Output is correct |
15 |
Correct |
133 ms |
141304 KB |
Output is correct |
16 |
Correct |
131 ms |
141240 KB |
Output is correct |
17 |
Correct |
133 ms |
141432 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
138 ms |
141176 KB |
Output is correct |
2 |
Correct |
132 ms |
141224 KB |
Output is correct |
3 |
Correct |
956 ms |
229992 KB |
Output is correct |
4 |
Correct |
1527 ms |
254716 KB |
Output is correct |
5 |
Correct |
1047 ms |
239860 KB |
Output is correct |
6 |
Correct |
904 ms |
230972 KB |
Output is correct |
7 |
Correct |
1027 ms |
237356 KB |
Output is correct |
8 |
Correct |
1251 ms |
251424 KB |
Output is correct |
9 |
Correct |
1179 ms |
237916 KB |
Output is correct |
10 |
Correct |
1930 ms |
285708 KB |
Output is correct |
11 |
Correct |
754 ms |
200880 KB |
Output is correct |
12 |
Correct |
789 ms |
199264 KB |
Output is correct |
13 |
Correct |
1666 ms |
271176 KB |
Output is correct |
14 |
Correct |
561 ms |
193136 KB |
Output is correct |
15 |
Correct |
522 ms |
187868 KB |
Output is correct |
16 |
Correct |
467 ms |
188988 KB |
Output is correct |
17 |
Correct |
489 ms |
187512 KB |
Output is correct |
18 |
Correct |
402 ms |
195512 KB |
Output is correct |
19 |
Correct |
143 ms |
143648 KB |
Output is correct |
20 |
Correct |
259 ms |
165388 KB |
Output is correct |
21 |
Correct |
412 ms |
187484 KB |
Output is correct |
22 |
Correct |
443 ms |
187680 KB |
Output is correct |
23 |
Correct |
508 ms |
198620 KB |
Output is correct |
24 |
Correct |
504 ms |
188200 KB |
Output is correct |
25 |
Correct |
479 ms |
187100 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
214 ms |
154988 KB |
Output is correct |
2 |
Runtime error |
1046 ms |
600652 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
214 ms |
154988 KB |
Output is correct |
2 |
Runtime error |
1046 ms |
600652 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
132 ms |
141304 KB |
Output is correct |
2 |
Correct |
132 ms |
141304 KB |
Output is correct |
3 |
Correct |
133 ms |
141192 KB |
Output is correct |
4 |
Correct |
132 ms |
141304 KB |
Output is correct |
5 |
Correct |
132 ms |
141288 KB |
Output is correct |
6 |
Correct |
133 ms |
141272 KB |
Output is correct |
7 |
Correct |
132 ms |
141292 KB |
Output is correct |
8 |
Correct |
134 ms |
141304 KB |
Output is correct |
9 |
Correct |
131 ms |
141304 KB |
Output is correct |
10 |
Correct |
149 ms |
141432 KB |
Output is correct |
11 |
Correct |
131 ms |
141304 KB |
Output is correct |
12 |
Correct |
131 ms |
141220 KB |
Output is correct |
13 |
Correct |
131 ms |
141212 KB |
Output is correct |
14 |
Correct |
154 ms |
141304 KB |
Output is correct |
15 |
Correct |
133 ms |
141304 KB |
Output is correct |
16 |
Correct |
131 ms |
141240 KB |
Output is correct |
17 |
Correct |
133 ms |
141432 KB |
Output is correct |
18 |
Correct |
138 ms |
141176 KB |
Output is correct |
19 |
Correct |
132 ms |
141224 KB |
Output is correct |
20 |
Correct |
956 ms |
229992 KB |
Output is correct |
21 |
Correct |
1527 ms |
254716 KB |
Output is correct |
22 |
Correct |
1047 ms |
239860 KB |
Output is correct |
23 |
Correct |
904 ms |
230972 KB |
Output is correct |
24 |
Correct |
1027 ms |
237356 KB |
Output is correct |
25 |
Correct |
1251 ms |
251424 KB |
Output is correct |
26 |
Correct |
1179 ms |
237916 KB |
Output is correct |
27 |
Correct |
1930 ms |
285708 KB |
Output is correct |
28 |
Correct |
754 ms |
200880 KB |
Output is correct |
29 |
Correct |
789 ms |
199264 KB |
Output is correct |
30 |
Correct |
1666 ms |
271176 KB |
Output is correct |
31 |
Correct |
561 ms |
193136 KB |
Output is correct |
32 |
Correct |
522 ms |
187868 KB |
Output is correct |
33 |
Correct |
467 ms |
188988 KB |
Output is correct |
34 |
Correct |
489 ms |
187512 KB |
Output is correct |
35 |
Correct |
402 ms |
195512 KB |
Output is correct |
36 |
Correct |
143 ms |
143648 KB |
Output is correct |
37 |
Correct |
259 ms |
165388 KB |
Output is correct |
38 |
Correct |
412 ms |
187484 KB |
Output is correct |
39 |
Correct |
443 ms |
187680 KB |
Output is correct |
40 |
Correct |
508 ms |
198620 KB |
Output is correct |
41 |
Correct |
504 ms |
188200 KB |
Output is correct |
42 |
Correct |
479 ms |
187100 KB |
Output is correct |
43 |
Correct |
214 ms |
154988 KB |
Output is correct |
44 |
Runtime error |
1046 ms |
600652 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
45 |
Halted |
0 ms |
0 KB |
- |