Submission #622720

#	Time	Username	Problem	Language	Result	Execution time	Memory
622720		Jomnoi	Sky Walking (IOI19_walk)	C++17	10 / 100	4102 ms	566164 KiB

walk

#include <bits/stdc++.h>
#include "walk.h"
using namespace std;

const int MAX_N = 1e5 + 5;
const long long llINF = 1e18 + 7;

int N, M, cntNode;
int table[MAX_N][20];
map <int, set <pair <int, int>>> graph;
map <int, long long> dist;
map <int, bool> visited;
set <pair <int, int>> intersect[MAX_N];

int getMax(int l, int r) {
	int j = log2(r - l + 1);
	return max(table[l][j], table[r - (1<<j) + 1][j]);
}

int connectVertical(int i, int y) {
	auto itL = intersect[i].lower_bound(make_pair(y, -1)), itR = itL--;
	int now;
	bool newNode = false;
	if(itR != intersect[i].end() and itR->first == y) {
		now = itR->second;
	}
	else {
		now = cntNode++;
		newNode = true;
	}

	if(itR != intersect[i].end()) {
		graph[itR->second].erase(make_pair(itL->second, itR->first - itL->first));
		graph[itL->second].erase(make_pair(itR->second, itR->first - itL->first));
	}

	graph[now].emplace(itL->second, y - itL->first);
	graph[itL->second].emplace(now, y - itL->first);
	if(itR != intersect[i].end() and itR->first > y) {
		graph[now].emplace(itR->second, itR->first - y);
		graph[itR->second].emplace(now, itR->first - y);
	}

	if(newNode == true) {
		intersect[i].emplace(y, now);
	}
	return now;
}

long long min_distance(vector <int> X, vector <int> H, vector <int> Lft, vector <int> Rgh, vector <int> Y, int S, int G) {
	N = X.size(), M = Y.size(), cntNode = N;
	for(int i = 0; i < N; i++) {
		table[i][0] = H[i];
		intersect[i].emplace(0, i);
	}
	for(int j = 1; j < 20; j++) {
		for(int i = 0; i + (1<<j) - 1 < N; i++) {
			table[i][j] = max(table[i][j - 1], table[i + (1<<(j - 1))][j - 1]);
		}
	}

	for(int i = 0; i < M; i++) {
		int prv = Lft[i], nxt;
		int prv2, nxt2;
		prv2 = connectVertical(Lft[i], Y[i]);
		while(prv < Rgh[i]) {
			int l = prv + 1, r = Rgh[i];
			while(l <= r) {
				int mid = (l + r) / 2;

				if(getMax(prv + 1, mid) >= Y[i]) {
					nxt = mid;
					r = mid - 1;
				}
				else {
					l = mid + 1;
				}
			}

			nxt2 = connectVertical(nxt, Y[i]);
			graph[prv2].emplace(nxt2, X[nxt] - X[prv]);
			graph[nxt2].emplace(prv2, X[nxt] - X[prv]);
			prv = nxt, prv2 = nxt2;
		}
	}

	for(int i = 0; i < cntNode; i++) {
		dist[i] = llINF;
	}

	priority_queue <pair <long long, int>> pq;
	pq.emplace(0, S);
	dist[S] = 0;
	while(!pq.empty()) {
		auto [d, u] = pq.top();
		pq.pop();

		if(visited[u] == true) {
			continue;
		}
		visited[u] = false;

		if(u == G) {
			return dist[u];
		}
		for(auto [v, w] : graph[u]) {
			if(visited[v] == false and dist[u] + w < dist[v]) {
				dist[v] = dist[u] + w;
				pq.emplace(-dist[v], v);
			}
		}
	}
	return -1;
}

Compilation message (stderr)

walk.cpp: In function 'long long int min_distance(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, int, int)':
walk.cpp:81:35: warning: 'nxt' may be used uninitialized in this function [-Wmaybe-uninitialized]
   81 |    graph[prv2].emplace(nxt2, X[nxt] - X[prv]);
      |                                   ^

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