Submission #154399

#	Time	Username	Problem	Language	Result	Execution time	Memory
154399		rama_pang	Sky Walking (IOI19_walk)	C++14	100 / 100	2431 ms	202280 KiB

walk

#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 / 10
• Subtask 2: 14 / 14
• Subtask 3: 15 / 15
• Subtask 4: 18 / 18
• Subtask 5: 43 / 43