# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
147981 |
2019-08-31T10:28:54 Z |
Xylofo |
Sky Walking (IOI19_walk) |
C++14 |
|
4000 ms |
245920 KB |
#pragma GCC optimize("Ofast")
#include "walk.h"
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define trav(a, x) for(auto& a : x)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define eb emplace_back
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
const ll INF =1e18;
#ifdef LOCAL
#include "../../../../MixedFunc/pretty_debug.h"
#else
#define debug(...) //ignore
#endif
struct Graph {
int n,m;
vi x,y,h;
unordered_map<ll, int> V; // verts, indexed by 2e9*x+h
vector<vector<pair<int,ll>>> E; // adj-list
vector<map<ll,int> > perBuild, perWalk;
Graph(vi& x, vi& y, vi& h)
: n(sz(x)), m(sz(y)), x(x), y(y), h(h), perBuild(n), perWalk(m) {}
int at(ll x, ll h) { // return vertex handle of (x,h)
auto p = x*(ll(2e9))+ h;
if (!V.count(p)) { V[p] = sz(E); E.eb(); }
return V[p];
}
void add(int build, int walk) { // pt (x[build], y[walk]) is important
ll X = x[build], Y = y[walk];
//assert(h[build] >= Y);
int q = at(X, Y);
perBuild[build][Y] = q;
perWalk[walk][X] = q;
}
void edge(int a, int b, ll c){ // create edge
E[a].eb(b,c);
E[b].eb(a,c);
}
void edges(map<ll,int>& vert) { // create edges on line
vector<pair<ll,int> > vv(all(vert));
rep(i,1,sz(vv))
edge(vv[i-1].second, vv[i].second, vv[i].first-vv[i-1].first);
}
void addUpDown(vi& l, vi& r) { // add things directely above/below points added.
vector<vi> start(n), end(n);
rep(i,0,m) start[l[i]].eb(i), end[r[i]].eb(i);
map<ll,int> active;
rep(i,0,n) {
trav(w,end[i]) active.erase(y[w]);
trav(w,start[i]) active[y[w]] = w;
vi toAdd;
for(auto [hh, _] : perBuild[i]) {
auto it = active.upper_bound(hh);
auto maybeAdd = [&](int w) { if (y[w] <= h[i]) toAdd.eb(w); };
if(it != active.end()) maybeAdd(it->second);
it = active.lower_bound(hh);
if(it != active.begin()) maybeAdd((--it)->second);
}
trav(w, toAdd) add(i,w);
}
}
void build(){
trav(v, perBuild) edges(v);
trav(v, perWalk) edges(v);
}
};
template<class T>
auto dijkstra(int source, vector<vector<pair<int, T>>> &g) {
int n = sz(g);
vector<T> dist(n, numeric_limits<T>::max());
//vector<pair<int,T> > dad(n, {-1, 0});
priority_queue<pair<T,int> > pq;
dist[source] = 0;
pq.emplace(0,source);
while(!pq.empty()) {
T d; int x;
tie(d,x) = pq.top();
d = -d;
pq.pop();
if(d > dist[x]) continue;
for(auto [y,w] : g[x]) {
if(dist[y] > d + w) {
dist[y] = d + w;
//dad[y] = {x, w};
pq.emplace(-dist[y], y);
}
}
}
return dist;
}
ll min_distance(vi x, vi h, vi l, vi r, vi y, int s, int g) {
int n = sz(x), m = sz(l);
debug(n,m);
auto stALL= [&](){
vector<map<ll,int>> Q;
auto pcomp = [&] (vi idx) {
Q.eb();
int hh = 0;
for(int i : idx) if(h[i] > hh) {
hh = h[i];
Q.back()[hh] = i;
}
};
{ vi ind; rep(i,s,n) ind.eb(i); pcomp(ind); }
{ vi ind; for(int i = s; i >= 0; --i) ind.eb(i); pcomp(ind); }
{ vi ind; rep(i,g,n) ind.eb(i); pcomp(ind); }
{ vi ind; for(int i = g; i >= 0; --i) ind.eb(i); pcomp(ind); }
//debug(Q);
Graph G(x,y,h);
int S = G.perBuild[s][0] = G.at(x[s], 0);
int T = G.perBuild[g][0] = G.at(x[g], 0);
debug("added", s, g);
rep(i,0,m) {
// add endpoints
G.add(l[i],i);
G.add(r[i],i);
//add closest to s and g in each direction.
for(auto &q: Q) {
auto it = q.lower_bound(y[i]);
if(it == q.end()) continue;
int j = it->second;
if(l[i] <= j && j <= r[i]) G.add(j, i);
}
}
debug("added pts 1");
debug(sz(G.E));
G.addUpDown(l,r);
debug("added pts 2");
debug(sz(G.E));
G.build();
debug("added edges");
auto dist = dijkstra(S, G.E);
//auto[dist, dad] = dijkstra(at(x[s],0),E);
//for(int q = at(x[g],0); dad[q].first != -1; q = dad[q].first) {
// debug(iV[q]);
//}
ll ans = dist[T];
if (ans >= INF) ans = -1;
return ans;
};
return stALL();
}
Compilation message
walk.cpp: In member function 'void Graph::addUpDown(vi&, vi&)':
walk.cpp:70:16: warning: decomposition declaration only available with -std=c++1z or -std=gnu++1z
for(auto [hh, _] : perBuild[i]) {
^
walk.cpp:70:22: warning: unused variable '_' [-Wunused-variable]
for(auto [hh, _] : perBuild[i]) {
^
walk.cpp: In function 'auto dijkstra(int, std::vector<std::vector<std::pair<int, T> > >&)':
walk.cpp:101:14: warning: decomposition declaration only available with -std=c++1z or -std=gnu++1z
for(auto [y,w] : g[x]) {
^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
256 KB |
Output is correct |
2 |
Correct |
2 ms |
256 KB |
Output is correct |
3 |
Correct |
2 ms |
376 KB |
Output is correct |
4 |
Correct |
2 ms |
256 KB |
Output is correct |
5 |
Correct |
2 ms |
376 KB |
Output is correct |
6 |
Correct |
3 ms |
376 KB |
Output is correct |
7 |
Correct |
3 ms |
376 KB |
Output is correct |
8 |
Correct |
2 ms |
376 KB |
Output is correct |
9 |
Correct |
3 ms |
376 KB |
Output is correct |
10 |
Correct |
2 ms |
376 KB |
Output is correct |
11 |
Correct |
2 ms |
376 KB |
Output is correct |
12 |
Correct |
2 ms |
376 KB |
Output is correct |
13 |
Correct |
2 ms |
348 KB |
Output is correct |
14 |
Correct |
2 ms |
376 KB |
Output is correct |
15 |
Correct |
2 ms |
376 KB |
Output is correct |
16 |
Correct |
2 ms |
376 KB |
Output is correct |
17 |
Correct |
2 ms |
376 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
256 KB |
Output is correct |
3 |
Correct |
1650 ms |
128612 KB |
Output is correct |
4 |
Correct |
1543 ms |
133884 KB |
Output is correct |
5 |
Correct |
1264 ms |
105028 KB |
Output is correct |
6 |
Correct |
1190 ms |
97740 KB |
Output is correct |
7 |
Correct |
1091 ms |
105072 KB |
Output is correct |
8 |
Correct |
1916 ms |
143812 KB |
Output is correct |
9 |
Correct |
1309 ms |
123544 KB |
Output is correct |
10 |
Correct |
1865 ms |
144352 KB |
Output is correct |
11 |
Correct |
1237 ms |
98612 KB |
Output is correct |
12 |
Correct |
681 ms |
64644 KB |
Output is correct |
13 |
Correct |
1662 ms |
149160 KB |
Output is correct |
14 |
Correct |
917 ms |
70380 KB |
Output is correct |
15 |
Correct |
857 ms |
71284 KB |
Output is correct |
16 |
Correct |
732 ms |
69236 KB |
Output is correct |
17 |
Correct |
708 ms |
66388 KB |
Output is correct |
18 |
Correct |
1125 ms |
75640 KB |
Output is correct |
19 |
Correct |
19 ms |
3764 KB |
Output is correct |
20 |
Correct |
260 ms |
35120 KB |
Output is correct |
21 |
Correct |
615 ms |
64888 KB |
Output is correct |
22 |
Correct |
645 ms |
65216 KB |
Output is correct |
23 |
Correct |
1177 ms |
83208 KB |
Output is correct |
24 |
Correct |
656 ms |
65992 KB |
Output is correct |
25 |
Correct |
671 ms |
65932 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
237 ms |
24948 KB |
Output is correct |
2 |
Correct |
2509 ms |
175088 KB |
Output is correct |
3 |
Correct |
2503 ms |
182096 KB |
Output is correct |
4 |
Correct |
2581 ms |
188300 KB |
Output is correct |
5 |
Correct |
2783 ms |
191132 KB |
Output is correct |
6 |
Correct |
2560 ms |
176588 KB |
Output is correct |
7 |
Correct |
1187 ms |
98616 KB |
Output is correct |
8 |
Correct |
670 ms |
64588 KB |
Output is correct |
9 |
Correct |
2247 ms |
163988 KB |
Output is correct |
10 |
Correct |
1048 ms |
89456 KB |
Output is correct |
11 |
Correct |
21 ms |
6308 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
237 ms |
24948 KB |
Output is correct |
2 |
Correct |
2509 ms |
175088 KB |
Output is correct |
3 |
Correct |
2503 ms |
182096 KB |
Output is correct |
4 |
Correct |
2581 ms |
188300 KB |
Output is correct |
5 |
Correct |
2783 ms |
191132 KB |
Output is correct |
6 |
Correct |
2560 ms |
176588 KB |
Output is correct |
7 |
Correct |
1187 ms |
98616 KB |
Output is correct |
8 |
Correct |
670 ms |
64588 KB |
Output is correct |
9 |
Correct |
2247 ms |
163988 KB |
Output is correct |
10 |
Correct |
1048 ms |
89456 KB |
Output is correct |
11 |
Correct |
21 ms |
6308 KB |
Output is correct |
12 |
Correct |
2487 ms |
181584 KB |
Output is correct |
13 |
Correct |
2452 ms |
187444 KB |
Output is correct |
14 |
Correct |
2891 ms |
191156 KB |
Output is correct |
15 |
Correct |
1823 ms |
147888 KB |
Output is correct |
16 |
Correct |
1871 ms |
151096 KB |
Output is correct |
17 |
Correct |
2420 ms |
187000 KB |
Output is correct |
18 |
Correct |
1943 ms |
147972 KB |
Output is correct |
19 |
Correct |
2000 ms |
150716 KB |
Output is correct |
20 |
Correct |
1180 ms |
95992 KB |
Output is correct |
21 |
Correct |
63 ms |
13152 KB |
Output is correct |
22 |
Correct |
1615 ms |
144200 KB |
Output is correct |
23 |
Correct |
1419 ms |
128848 KB |
Output is correct |
24 |
Correct |
941 ms |
85156 KB |
Output is correct |
25 |
Correct |
1214 ms |
118484 KB |
Output is correct |
26 |
Correct |
623 ms |
61428 KB |
Output is correct |
27 |
Correct |
2818 ms |
190948 KB |
Output is correct |
28 |
Correct |
2115 ms |
184832 KB |
Output is correct |
29 |
Correct |
2576 ms |
176528 KB |
Output is correct |
30 |
Correct |
1259 ms |
98056 KB |
Output is correct |
31 |
Correct |
2347 ms |
163852 KB |
Output is correct |
32 |
Correct |
838 ms |
77928 KB |
Output is correct |
33 |
Correct |
777 ms |
77628 KB |
Output is correct |
34 |
Correct |
991 ms |
86404 KB |
Output is correct |
35 |
Correct |
1117 ms |
95636 KB |
Output is correct |
36 |
Correct |
849 ms |
78416 KB |
Output is correct |
37 |
Correct |
655 ms |
64888 KB |
Output is correct |
38 |
Correct |
605 ms |
65100 KB |
Output is correct |
39 |
Correct |
1070 ms |
83060 KB |
Output is correct |
40 |
Correct |
671 ms |
66056 KB |
Output is correct |
41 |
Correct |
691 ms |
65848 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
256 KB |
Output is correct |
2 |
Correct |
2 ms |
256 KB |
Output is correct |
3 |
Correct |
2 ms |
376 KB |
Output is correct |
4 |
Correct |
2 ms |
256 KB |
Output is correct |
5 |
Correct |
2 ms |
376 KB |
Output is correct |
6 |
Correct |
3 ms |
376 KB |
Output is correct |
7 |
Correct |
3 ms |
376 KB |
Output is correct |
8 |
Correct |
2 ms |
376 KB |
Output is correct |
9 |
Correct |
3 ms |
376 KB |
Output is correct |
10 |
Correct |
2 ms |
376 KB |
Output is correct |
11 |
Correct |
2 ms |
376 KB |
Output is correct |
12 |
Correct |
2 ms |
376 KB |
Output is correct |
13 |
Correct |
2 ms |
348 KB |
Output is correct |
14 |
Correct |
2 ms |
376 KB |
Output is correct |
15 |
Correct |
2 ms |
376 KB |
Output is correct |
16 |
Correct |
2 ms |
376 KB |
Output is correct |
17 |
Correct |
2 ms |
376 KB |
Output is correct |
18 |
Correct |
2 ms |
376 KB |
Output is correct |
19 |
Correct |
2 ms |
256 KB |
Output is correct |
20 |
Correct |
1650 ms |
128612 KB |
Output is correct |
21 |
Correct |
1543 ms |
133884 KB |
Output is correct |
22 |
Correct |
1264 ms |
105028 KB |
Output is correct |
23 |
Correct |
1190 ms |
97740 KB |
Output is correct |
24 |
Correct |
1091 ms |
105072 KB |
Output is correct |
25 |
Correct |
1916 ms |
143812 KB |
Output is correct |
26 |
Correct |
1309 ms |
123544 KB |
Output is correct |
27 |
Correct |
1865 ms |
144352 KB |
Output is correct |
28 |
Correct |
1237 ms |
98612 KB |
Output is correct |
29 |
Correct |
681 ms |
64644 KB |
Output is correct |
30 |
Correct |
1662 ms |
149160 KB |
Output is correct |
31 |
Correct |
917 ms |
70380 KB |
Output is correct |
32 |
Correct |
857 ms |
71284 KB |
Output is correct |
33 |
Correct |
732 ms |
69236 KB |
Output is correct |
34 |
Correct |
708 ms |
66388 KB |
Output is correct |
35 |
Correct |
1125 ms |
75640 KB |
Output is correct |
36 |
Correct |
19 ms |
3764 KB |
Output is correct |
37 |
Correct |
260 ms |
35120 KB |
Output is correct |
38 |
Correct |
615 ms |
64888 KB |
Output is correct |
39 |
Correct |
645 ms |
65216 KB |
Output is correct |
40 |
Correct |
1177 ms |
83208 KB |
Output is correct |
41 |
Correct |
656 ms |
65992 KB |
Output is correct |
42 |
Correct |
671 ms |
65932 KB |
Output is correct |
43 |
Correct |
237 ms |
24948 KB |
Output is correct |
44 |
Correct |
2509 ms |
175088 KB |
Output is correct |
45 |
Correct |
2503 ms |
182096 KB |
Output is correct |
46 |
Correct |
2581 ms |
188300 KB |
Output is correct |
47 |
Correct |
2783 ms |
191132 KB |
Output is correct |
48 |
Correct |
2560 ms |
176588 KB |
Output is correct |
49 |
Correct |
1187 ms |
98616 KB |
Output is correct |
50 |
Correct |
670 ms |
64588 KB |
Output is correct |
51 |
Correct |
2247 ms |
163988 KB |
Output is correct |
52 |
Correct |
1048 ms |
89456 KB |
Output is correct |
53 |
Correct |
21 ms |
6308 KB |
Output is correct |
54 |
Correct |
2487 ms |
181584 KB |
Output is correct |
55 |
Correct |
2452 ms |
187444 KB |
Output is correct |
56 |
Correct |
2891 ms |
191156 KB |
Output is correct |
57 |
Correct |
1823 ms |
147888 KB |
Output is correct |
58 |
Correct |
1871 ms |
151096 KB |
Output is correct |
59 |
Correct |
2420 ms |
187000 KB |
Output is correct |
60 |
Correct |
1943 ms |
147972 KB |
Output is correct |
61 |
Correct |
2000 ms |
150716 KB |
Output is correct |
62 |
Correct |
1180 ms |
95992 KB |
Output is correct |
63 |
Correct |
63 ms |
13152 KB |
Output is correct |
64 |
Correct |
1615 ms |
144200 KB |
Output is correct |
65 |
Correct |
1419 ms |
128848 KB |
Output is correct |
66 |
Correct |
941 ms |
85156 KB |
Output is correct |
67 |
Correct |
1214 ms |
118484 KB |
Output is correct |
68 |
Correct |
623 ms |
61428 KB |
Output is correct |
69 |
Correct |
2818 ms |
190948 KB |
Output is correct |
70 |
Correct |
2115 ms |
184832 KB |
Output is correct |
71 |
Correct |
2576 ms |
176528 KB |
Output is correct |
72 |
Correct |
1259 ms |
98056 KB |
Output is correct |
73 |
Correct |
2347 ms |
163852 KB |
Output is correct |
74 |
Correct |
838 ms |
77928 KB |
Output is correct |
75 |
Correct |
777 ms |
77628 KB |
Output is correct |
76 |
Correct |
991 ms |
86404 KB |
Output is correct |
77 |
Correct |
1117 ms |
95636 KB |
Output is correct |
78 |
Correct |
849 ms |
78416 KB |
Output is correct |
79 |
Correct |
655 ms |
64888 KB |
Output is correct |
80 |
Correct |
605 ms |
65100 KB |
Output is correct |
81 |
Correct |
1070 ms |
83060 KB |
Output is correct |
82 |
Correct |
671 ms |
66056 KB |
Output is correct |
83 |
Correct |
691 ms |
65848 KB |
Output is correct |
84 |
Correct |
180 ms |
20476 KB |
Output is correct |
85 |
Correct |
2970 ms |
185472 KB |
Output is correct |
86 |
Correct |
3521 ms |
214232 KB |
Output is correct |
87 |
Correct |
128 ms |
20972 KB |
Output is correct |
88 |
Correct |
136 ms |
20988 KB |
Output is correct |
89 |
Correct |
124 ms |
20964 KB |
Output is correct |
90 |
Correct |
54 ms |
9304 KB |
Output is correct |
91 |
Correct |
3 ms |
632 KB |
Output is correct |
92 |
Correct |
45 ms |
7104 KB |
Output is correct |
93 |
Correct |
814 ms |
67252 KB |
Output is correct |
94 |
Correct |
61 ms |
13360 KB |
Output is correct |
95 |
Correct |
1751 ms |
151860 KB |
Output is correct |
96 |
Correct |
1424 ms |
130220 KB |
Output is correct |
97 |
Correct |
1089 ms |
89160 KB |
Output is correct |
98 |
Correct |
1231 ms |
118400 KB |
Output is correct |
99 |
Execution timed out |
4026 ms |
245920 KB |
Time limit exceeded |
100 |
Halted |
0 ms |
0 KB |
- |