Submission #146918

#	Time	Username	Problem	Language	Result	Execution time	Memory
146918		tincamatei	Sky Walking (IOI19_walk)	C++14	24 / 100	654 ms	179312 KiB

walk

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

const int MAX_N = 100000;
const int MAX_M = 100000;
const int MAX_NODES = 11 * MAX_N;
const long long INF = 1LL << 60;

using namespace std;


int lastid;
vector<pair<int, int> > graph[MAX_NODES];
int baseId[MAX_NODES];
vector<int> eventI[MAX_N], eventE[MAX_N];
vector<int> x, h;

priority_queue<pair<long long, int> > coada;
long long dist[MAX_NODES];

struct Skywalk {
	int l, r, h;
	int lastnode;
} skywalk[MAX_M];

struct CmpSkywalk {
	bool operator() (int a, int b) {
		return skywalk[a].h < skywalk[b].h || (skywalk[a].h == skywalk[b].h && a < b);
	}
};

set<int, CmpSkywalk> segs;

void addEdge(int a, int b, int c) {
	graph[a].push_back({b, c});
	graph[b].push_back({a, c});
}

long long runDijkstra(int s, int g) {
	for(int i = 0; i < lastid; ++i)
		dist[i] = INF;
	
	dist[s] = 0;
	coada.push({0, s});

	while(!coada.empty()) {
		long long cost = -coada.top().first;
		int nod = coada.top().second;
		coada.pop();

		if(cost == dist[nod]) {
			for(auto it: graph[nod]) {
				if(cost + it.second < dist[it.first]) {
					dist[it.first] = cost + it.second;
					coada.push({-dist[it.first], it.first});
				}
			}
		}
	}

	if(dist[g] != INF)
		return dist[g];
	return -1;
}

long long min_distance(std::vector<int> _x, std::vector<int> _h, std::vector<int> l, std::vector<int> r, std::vector<int> y, int s, int g) {
	x = _x;
	h = _h;
	int N = x.size();
	int M = l.size();

	for(int i = 0; i < M; ++i) {
		skywalk[i] = {l[i], r[i], y[i], -1};
		eventI[l[i]].push_back(i);
		eventE[r[i]].push_back(i);
	}

	for(int i = 0; i < N; ++i) {
		int base = lastid++, lasth = 0;
		baseId[i] = base;
		for(auto it: eventI[i])
			segs.insert(it);
		
		set<int>::iterator it = segs.begin();
		while(it != segs.end() && skywalk[*it].h <= h[i]) {
			int nod = lastid++;
			addEdge(nod, base, skywalk[*it].h - lasth);
			base = nod;
			lasth = skywalk[*it].h;

			if(skywalk[*it].lastnode != -1) {
				addEdge(base, skywalk[*it].lastnode, x[i] - x[skywalk[*it].l]);
				skywalk[*it].l = i;
			}
			skywalk[*it].lastnode = base;
			it++;
		}

		for(auto it: eventE[i])
			segs.erase(it);
	}

	return runDijkstra(baseId[s], baseId[g]);
}

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