oj.uz

Submission #154399

# Submission time Handle Problem Language Result Execution time Memory
154399 2019-09-21T17:00:06 Z rama_pang Sky Walking (IOI19_walk) C++14
100 / 100
 2431 ms 202280 KB 
#include "walk.h"
#include <bits/stdc++.h>
using namespace std;
 
struct point {
	int x, y, idx;	
    point() { }
    point(int x, int y, int idx) { this->x = x, this->y = y, this->idx = idx; }
    bool operator < (const point &r) const {
        return x < r.x || (x == r.x && y < r.y);
    }
    bool operator == (const point &r) const {
        return x == r.x && y == r.y;
    }
};
 
long long dijkstra(int s, int g, vector<vector<pair<long long, int>>> G) {
	priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq;
	vector<long long> dist(G.size(), -1);
	pq.push({0, s}); dist[s] = 0;
	while (!pq.empty()) {
		auto top = pq.top();
		pq.pop();
		if (top.first != dist[top.second]) continue;
		for (auto v : G[top.second]) {
			if (dist[v.second] > top.first + v.first || dist[v.second] == -1) {
				dist[v.second] = top.first + v.first;
				pq.push({dist[v.second], v.second});
			}
		}
	}	
	return dist[g];
}
 
void add_edge(point &x, point &y, vector<vector<pair<long long, int>>> &G) {
	G[x.idx].emplace_back(abs(y.x - x.x) + abs(y.y - x.y), y.idx);
	G[y.idx].emplace_back(abs(y.x - x.x) + abs(y.y - x.y), x.idx);
	return;
}
 
void build_graph(vector<int> x, vector<int> h, vector<int> l, vector<int> r, vector<int> y, int &s, int &g, vector<vector<pair<long long, int>>> &G) {
	int n = x.size(), m = y.size();
	vector<vector<int>> building(n);
	vector<vector<pair<int, int>>> event(n);
	building[s].emplace_back(0);
	building[g].emplace_back(0);
	for (int i = 0; i < m; i++) {
		building[l[i]].emplace_back(y[i]);
		building[r[i]].emplace_back(y[i]);
		event[l[i]].emplace_back(y[i], +1);
		if (r[i] + 1 < n) event[r[i] + 1].emplace_back(y[i], -1);
	}

	multiset<int> alive; //find intersection directly above or below or on start points and endpoints of skywalks
	for (int i = 0; i < n; i++) { //proof of correctness:
		for (auto &e : event[i]) { //let s = 0 and g = n - 1
			if (e.second == +1) alive.insert(e.first); //permuting all possible ways, we can always go right (shortest path)
			else alive.erase(alive.find(e.first)); //if there is a backtrack (left) segment, continued by another segment
		} //we can always directly go there without going left at all. QED.
		vector<int> tmp = building[i]; //as we always go right, x-distance is always the same -> minimize y-distance
		for (auto &b : building[i]) { //to minimize, we cannot use the same skywalk twice
			if (b == 0) continue; //thus we should only switch only at start and endpoint,
			auto it = alive.upper_bound(b); //and if there are start and end point of another segment directly above or below
			if (it != alive.end()) tmp.emplace_back(*it); //if we switch to below, we can just switch at the end of the current skywalk
			it = alive.lower_bound(b); //if above, switch at new segment start point
			if (it != alive.begin()) tmp.emplace_back(*prev(it)); //applying all of this, we only need to use 6 intersections
		} //on, directly above, and directly below the start and end points of a skywalk
		sort(tmp.begin(), tmp.end()); 
		tmp.resize(unique(tmp.begin(), tmp.end()) - tmp.begin());
        while (!tmp.empty() && tmp.back() > h[i]) tmp.pop_back();
		building[i] = tmp; //delete double counting
	}

    alive.clear(); //get intersection points closest to s and g for every skywalks
    vector<pair<int, int>> height_building; //observation: there exists a pl (pivot left) and pr (pivot right) such that
    vector<pair<int, pair<int, int>>> height_skywalk; //the shortest path = shortest path from s to pl + pl to pr + pr to g
    for (int i = 0; i < n; i++) alive.insert(i); //we can model s to pl as only going left -> ignore eerything on the right,
    for (int i = 0; i < n; i++) height_building.emplace_back(h[i], i); //and get all shortest path from s to 0
    for (int i = 0; i < m; i++) height_skywalk.push_back({y[i], {l[i], r[i]}}); //then we can go from those shortest points from 0 to n
    sort(height_building.begin(), height_building.end()); //and then from n to g (model the same, but from g to n-1)
    sort(height_skywalk.begin(), height_skywalk.end()); 
    for (int i = 0, loc = 0; i < m; i++) { //also model from s to n-1, and from g to 0 -> thus every possible left-right path is possible
        while (loc < n && height_skywalk[i].first > height_building[loc].first) alive.erase(height_building[loc++].second); //(right-right-tight),
        if (height_skywalk[i].second.first <= s && s <= height_skywalk[i].second.second) { //(right, right, left), (left, right, tight),
            auto it = alive.lower_bound(s); //and (left, right, left). Midpath is always right -> get every point in 0...s and g...n-1 and get their shortest path
            building[*it].emplace_back(height_skywalk[i].first); //from s, you can go left or right -> get nearest intersection point for every skywalk
            if (it != alive.begin()) building[*prev(it)].emplace_back(height_skywalk[i].first); //like s = 0, g = n-1; you can ignore the opposite side
        } //nearest intersection point of every skywalk becomes "startpoints" for those skywalks
        if (height_skywalk[i].second.first <= g && g <= height_skywalk[i].second.second) { //ergo for s-right, and for g
            auto it = alive.lower_bound(g);
            building[*it].emplace_back(height_skywalk[i].first);
            if (it != alive.begin()) building[*prev(it)].emplace_back(height_skywalk[i].first);
        }
    }
    //build nodes and edges
	vector<point> points; //thus for shortest path from s to g
	for (int i = 0; i < n; i++) { //just need 18 intersection points for every skywalk
		for (auto &j : building[i]) { //startpoint and endpoint (2), and nearest to s and to e from left and from right (4),
            int num = points.size(); //also create intersections directly above or below those intersection points
			points.emplace_back(x[i], j, num); //2 * 6 = 18 intersections for every skywalk
		}
	}
    G.resize(points.size());
    auto cmpx = [&](const point &x, const point &y) { return x.x < y.x || (x.x == y.x && x.y < y.y); };
    auto cmpy = [&](const point &x, const point &y) { return x.y < y.y || (x.y == y.y && x.x < y.x); };
    sort(points.begin(), points.end(), cmpx);
    for (int i = 0; i < n; i++) {
        int lo = lower_bound(points.begin(), points.end(), point(x[i], 0, -1), cmpx) - points.begin();
        int hi = upper_bound(points.begin(), points.end(), point(x[i], h[i], -1), cmpx) - points.begin();
        for (int j = lo + 1; j < hi; j++) add_edge(points[j - 1], points[j], G);
	}
    sort(points.begin(), points.end(), cmpy);
    for (int i = 0; i < m; i++) {
        int lo = lower_bound(points.begin(), points.end(), point(x[l[i]], y[i], -1), cmpy) - points.begin();
        int hi = upper_bound(points.begin(), points.end(), point(x[r[i]], y[i], -1), cmpy) - points.begin();
        for (int j = lo + 1; j < hi; j++) add_edge(points[j - 1], points[j], G);
    }
    s = points[lower_bound(points.begin(), points.end(), point(x[s], 0, -1), cmpy) - points.begin()].idx;
    g = points[lower_bound(points.begin(), points.end(), point(x[g], 0, -1), cmpy) - points.begin()].idx;
    return;
}
 
long long min_distance(vector<int> x, vector<int> h, vector<int> l, vector<int> r, vector<int> y, int s, int g) {
	vector<vector<pair<long long, int>>> G;
    build_graph(x, h, l, r, y, s, g, G);
	return dijkstra(s, g, G);
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 3 ms 256 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 252 KB Output is correct
5 Correct 3 ms 376 KB Output is correct
6 Correct 3 ms 376 KB Output is correct
7 Correct 2 ms 380 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 3 ms 376 KB Output is correct
11 Correct 3 ms 376 KB Output is correct
12 Correct 3 ms 376 KB Output is correct
13 Correct 3 ms 376 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 256 KB Output is correct
16 Correct 3 ms 376 KB Output is correct
17 Correct 2 ms 376 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 921 ms 94144 KB Output is correct
4 Correct 1070 ms 91872 KB Output is correct
5 Correct 724 ms 71352 KB Output is correct
6 Correct 753 ms 71852 KB Output is correct
7 Correct 863 ms 71168 KB Output is correct
8 Correct 1006 ms 103396 KB Output is correct
9 Correct 872 ms 84824 KB Output is correct
10 Correct 1085 ms 97956 KB Output is correct
11 Correct 742 ms 67492 KB Output is correct
12 Correct 557 ms 40820 KB Output is correct
13 Correct 1095 ms 101276 KB Output is correct
14 Correct 811 ms 80712 KB Output is correct
15 Correct 713 ms 60788 KB Output is correct
16 Correct 525 ms 44384 KB Output is correct
17 Correct 510 ms 41272 KB Output is correct
18 Correct 1099 ms 116052 KB Output is correct
19 Correct 23 ms 4304 KB Output is correct
20 Correct 259 ms 40876 KB Output is correct
21 Correct 518 ms 40460 KB Output is correct
22 Correct 486 ms 39476 KB Output is correct
23 Correct 928 ms 72548 KB Output is correct
24 Correct 494 ms 40516 KB Output is correct
25 Correct 562 ms 40900 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 144 ms 14816 KB Output is correct
2 Correct 1204 ms 129060 KB Output is correct
3 Correct 1285 ms 134064 KB Output is correct
4 Correct 1546 ms 134700 KB Output is correct
5 Correct 1695 ms 138056 KB Output is correct
6 Correct 1607 ms 135656 KB Output is correct
7 Correct 729 ms 68740 KB Output is correct
8 Correct 492 ms 45512 KB Output is correct
9 Correct 1590 ms 134936 KB Output is correct
10 Correct 754 ms 69516 KB Output is correct
11 Correct 39 ms 7644 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 144 ms 14816 KB Output is correct
2 Correct 1204 ms 129060 KB Output is correct
3 Correct 1285 ms 134064 KB Output is correct
4 Correct 1546 ms 134700 KB Output is correct
5 Correct 1695 ms 138056 KB Output is correct
6 Correct 1607 ms 135656 KB Output is correct
7 Correct 729 ms 68740 KB Output is correct
8 Correct 492 ms 45512 KB Output is correct
9 Correct 1590 ms 134936 KB Output is correct
10 Correct 754 ms 69516 KB Output is correct
11 Correct 39 ms 7644 KB Output is correct
12 Correct 1343 ms 133560 KB Output is correct
13 Correct 1350 ms 133640 KB Output is correct
14 Correct 1719 ms 138092 KB Output is correct
15 Correct 1118 ms 100476 KB Output is correct
16 Correct 1174 ms 105188 KB Output is correct
17 Correct 1392 ms 134212 KB Output is correct
18 Correct 1105 ms 100232 KB Output is correct
19 Correct 1179 ms 104956 KB Output is correct
20 Correct 824 ms 67616 KB Output is correct
21 Correct 140 ms 15344 KB Output is correct
22 Correct 948 ms 99592 KB Output is correct
23 Correct 890 ms 89488 KB Output is correct
24 Correct 653 ms 54136 KB Output is correct
25 Correct 898 ms 81364 KB Output is correct
26 Correct 515 ms 39400 KB Output is correct
27 Correct 1855 ms 137476 KB Output is correct
28 Correct 1310 ms 131360 KB Output is correct
29 Correct 1649 ms 135608 KB Output is correct
30 Correct 793 ms 68176 KB Output is correct
31 Correct 1656 ms 134984 KB Output is correct
32 Correct 573 ms 51172 KB Output is correct
33 Correct 543 ms 47800 KB Output is correct
34 Correct 712 ms 65148 KB Output is correct
35 Correct 740 ms 62508 KB Output is correct
36 Correct 612 ms 48612 KB Output is correct
37 Correct 479 ms 40548 KB Output is correct
38 Correct 534 ms 39676 KB Output is correct
39 Correct 853 ms 72644 KB Output is correct
40 Correct 545 ms 40624 KB Output is correct
41 Correct 552 ms 40888 KB Output is correct

Subtask #5
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 3 ms 256 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 252 KB Output is correct
5 Correct 3 ms 376 KB Output is correct
6 Correct 3 ms 376 KB Output is correct
7 Correct 2 ms 380 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 3 ms 376 KB Output is correct
11 Correct 3 ms 376 KB Output is correct
12 Correct 3 ms 376 KB Output is correct
13 Correct 3 ms 376 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 256 KB Output is correct
16 Correct 3 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 376 KB Output is correct
20 Correct 921 ms 94144 KB Output is correct
21 Correct 1070 ms 91872 KB Output is correct
22 Correct 724 ms 71352 KB Output is correct
23 Correct 753 ms 71852 KB Output is correct
24 Correct 863 ms 71168 KB Output is correct
25 Correct 1006 ms 103396 KB Output is correct
26 Correct 872 ms 84824 KB Output is correct
27 Correct 1085 ms 97956 KB Output is correct
28 Correct 742 ms 67492 KB Output is correct
29 Correct 557 ms 40820 KB Output is correct
30 Correct 1095 ms 101276 KB Output is correct
31 Correct 811 ms 80712 KB Output is correct
32 Correct 713 ms 60788 KB Output is correct
33 Correct 525 ms 44384 KB Output is correct
34 Correct 510 ms 41272 KB Output is correct
35 Correct 1099 ms 116052 KB Output is correct
36 Correct 23 ms 4304 KB Output is correct
37 Correct 259 ms 40876 KB Output is correct
38 Correct 518 ms 40460 KB Output is correct
39 Correct 486 ms 39476 KB Output is correct
40 Correct 928 ms 72548 KB Output is correct
41 Correct 494 ms 40516 KB Output is correct
42 Correct 562 ms 40900 KB Output is correct
43 Correct 144 ms 14816 KB Output is correct
44 Correct 1204 ms 129060 KB Output is correct
45 Correct 1285 ms 134064 KB Output is correct
46 Correct 1546 ms 134700 KB Output is correct
47 Correct 1695 ms 138056 KB Output is correct
48 Correct 1607 ms 135656 KB Output is correct
49 Correct 729 ms 68740 KB Output is correct
50 Correct 492 ms 45512 KB Output is correct
51 Correct 1590 ms 134936 KB Output is correct
52 Correct 754 ms 69516 KB Output is correct
53 Correct 39 ms 7644 KB Output is correct
54 Correct 1343 ms 133560 KB Output is correct
55 Correct 1350 ms 133640 KB Output is correct
56 Correct 1719 ms 138092 KB Output is correct
57 Correct 1118 ms 100476 KB Output is correct
58 Correct 1174 ms 105188 KB Output is correct
59 Correct 1392 ms 134212 KB Output is correct
60 Correct 1105 ms 100232 KB Output is correct
61 Correct 1179 ms 104956 KB Output is correct
62 Correct 824 ms 67616 KB Output is correct
63 Correct 140 ms 15344 KB Output is correct
64 Correct 948 ms 99592 KB Output is correct
65 Correct 890 ms 89488 KB Output is correct
66 Correct 653 ms 54136 KB Output is correct
67 Correct 898 ms 81364 KB Output is correct
68 Correct 515 ms 39400 KB Output is correct
69 Correct 1855 ms 137476 KB Output is correct
70 Correct 1310 ms 131360 KB Output is correct
71 Correct 1649 ms 135608 KB Output is correct
72 Correct 793 ms 68176 KB Output is correct
73 Correct 1656 ms 134984 KB Output is correct
74 Correct 573 ms 51172 KB Output is correct
75 Correct 543 ms 47800 KB Output is correct
76 Correct 712 ms 65148 KB Output is correct
77 Correct 740 ms 62508 KB Output is correct
78 Correct 612 ms 48612 KB Output is correct
79 Correct 479 ms 40548 KB Output is correct
80 Correct 534 ms 39676 KB Output is correct
81 Correct 853 ms 72644 KB Output is correct
82 Correct 545 ms 40624 KB Output is correct
83 Correct 552 ms 40888 KB Output is correct
84 Correct 125 ms 12464 KB Output is correct
85 Correct 1370 ms 138232 KB Output is correct
86 Correct 2015 ms 171648 KB Output is correct
87 Correct 146 ms 20564 KB Output is correct
88 Correct 183 ms 18384 KB Output is correct
89 Correct 135 ms 20588 KB Output is correct
90 Correct 44 ms 5756 KB Output is correct
91 Correct 4 ms 632 KB Output is correct
92 Correct 39 ms 5000 KB Output is correct
93 Correct 564 ms 47092 KB Output is correct
94 Correct 135 ms 15348 KB Output is correct
95 Correct 1149 ms 105636 KB Output is correct
96 Correct 899 ms 91832 KB Output is correct
97 Correct 765 ms 72472 KB Output is correct
98 Correct 815 ms 81436 KB Output is correct
99 Correct 2431 ms 202280 KB Output is correct
100 Correct 1541 ms 134068 KB Output is correct
101 Correct 1882 ms 151828 KB Output is correct
102 Correct 798 ms 68532 KB Output is correct
103 Correct 585 ms 53688 KB Output is correct
104 Correct 556 ms 47844 KB Output is correct
105 Correct 715 ms 64824 KB Output is correct
106 Correct 726 ms 64400 KB Output is correct
107 Correct 785 ms 66316 KB Output is correct
108 Correct 105 ms 10556 KB Output is correct
109 Correct 1322 ms 104772 KB Output is correct
110 Correct 1508 ms 132884 KB Output is correct
111 Correct 1218 ms 134008 KB Output is correct
112 Correct 765 ms 61796 KB Output is correct
113 Correct 662 ms 55636 KB Output is correct