Submission #206275

#	Time	Username	Problem	Language	Result	Execution time	Memory
206275		Sorting	Sky Walking (IOI19_walk)	C++14	10 / 100	57 ms	10340 KiB

walk

#include "walk.h"
#include <bits/stdc++.h>

using namespace std;

const long long inf  = 1e18 + 7;
const int kN = 63;

vector<int> x, h, l, r, y;
vector<int> cross[kN];
int s, g, n, m;
vector<array<int, 3>> adj[kN][kN];
long long dist[kN][kN];

int find_in_cross(int idx, int val){
	return lower_bound(cross[idx].begin(), cross[idx].end(), val) - cross[idx].begin();
}

long long dijkstra(int start1, int start2, int end1, int end2){
	for(int i = 0; i < kN; ++i)
		for(int j = 0; j < kN; ++j)
			dist[i][j] = inf;

	priority_queue<array<long long, 3>, vector<array<long long, 3>>, greater<array<long long, 3>>> pq;

	dist[start1][start2] = 0;
	pq.push({0, start1, start2});

	while(!pq.empty()){
		array<long long, 3> state = pq.top();
		pq.pop();

		int u1 = state[1], u2 = state[2];
		if(state[0] != dist[u1][u2])
			continue;
		if(u1 == end1 && u2 == end2)
			break;

		for(auto edge: adj[u1][u2]){
			int to1 = edge[0], to2 = edge[1];
			if(dist[to1][to2] > dist[u1][u2] + edge[2]){
				dist[to1][to2] = dist[u1][u2] + edge[2];
				pq.push({dist[to1][to2], to1, to2});
			}
		}
	}

	return dist[end1][end2];
}

long long min_distance(vector<int> _x, vector<int> _h, vector<int> _l, vector<int> _r, vector<int> _y, int _s, int _g){
	x = _x, h = _h, l = _l, r = _r, y = _y, s = _s, g = _g;

	n = x.size(), m = y.size();

	sort(x.begin(), x.end());
	for(int i = 0; i < m; ++i){
		for(int j = l[i]; j <= r[i]; ++j){
			if(h[j] >= y[i])
				cross[j].push_back(y[i]);
		}
	}

	for(int i = 0; i < n; ++i){
		cross[i].push_back(0);
		cross[i].push_back(h[i]);
	}

	for(int i = 0; i < n; ++i)
		sort(cross[i].begin(), cross[i].end());

	for(int i = 0; i < n; ++i){
		vector<int> new_cross;
		for(int j = 0; j < (int)cross[i].size() - 1; ++j){
			if(cross[i][j] != cross[i][j + 1])
				new_cross.push_back(cross[i][j]);
		}

		if(!cross[i].empty())
			new_cross.push_back(cross[i].back());

		cross[i] = new_cross;
	}

	for(int i = 0; i < n; ++i){
		for(int j = 0; j < (int)cross[i].size() - 1; ++j){
			adj[i][j].push_back({i, j + 1, cross[i][j + 1] - cross[i][j]});
			adj[i][j + 1].push_back({i, j, cross[i][j + 1] - cross[i][j]});
		}
	}

	for(int i = 0; i < m; ++i){
		int pr = -1;
		for(int j = l[i]; j <= r[i]; ++j){
			if(h[j] >= y[i]){
				if(pr == -1){
					pr = j;
					continue;
				}

				int j_2 = find_in_cross(j, y[i]), pr_2 = find_in_cross(pr, y[i]);
				adj[j][j_2].push_back({pr, pr_2, x[j] - x[pr]});
				adj[pr][pr_2].push_back({j, j_2, x[j] - x[pr]});

				pr = j;
			}
		}
	}

	long long ret = dijkstra(s, 0, g, 0);
	if(ret == inf)
		ret = -1;

	return ret; 
}
/*
5
3
0 6
4 6
5 6
6 6
9 6
3 4 1
1 3 3
0 2 6
0 4
*/

• Subtask 1: 10 / 10
• Subtask 2: 0 / 14
• Subtask 3: 0 / 15
• Subtask 4: 0 / 18
• Subtask 5: 0 / 43