oj.uz

Submission #622720

# Submission time Handle Problem Language Result Execution time Memory
622720 2022-08-04T13:48:07 Z Jomnoi Sky Walking (IOI19_walk) C++17
10 / 100
 4000 ms 566164 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 4 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 4 ms 4996 KB Output is correct
5 Correct 4 ms 5244 KB Output is correct
6 Correct 5 ms 5264 KB Output is correct
7 Correct 3 ms 5204 KB Output is correct
8 Correct 3 ms 5140 KB Output is correct
9 Correct 3 ms 5076 KB Output is correct
10 Correct 6 ms 5332 KB Output is correct
11 Correct 5 ms 5016 KB Output is correct
12 Correct 4 ms 5012 KB Output is correct
13 Correct 4 ms 4948 KB Output is correct
14 Correct 3 ms 4948 KB Output is correct
15 Correct 3 ms 5012 KB Output is correct
16 Correct 4 ms 4948 KB Output is correct
17 Correct 5 ms 5332 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 2233 ms 277080 KB Output is correct
4 Execution timed out 4078 ms 337664 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 505 ms 36556 KB Output is correct
2 Execution timed out 4102 ms 566164 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 505 ms 36556 KB Output is correct
2 Execution timed out 4102 ms 566164 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 4 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 4 ms 4996 KB Output is correct
5 Correct 4 ms 5244 KB Output is correct
6 Correct 5 ms 5264 KB Output is correct
7 Correct 3 ms 5204 KB Output is correct
8 Correct 3 ms 5140 KB Output is correct
9 Correct 3 ms 5076 KB Output is correct
10 Correct 6 ms 5332 KB Output is correct
11 Correct 5 ms 5016 KB Output is correct
12 Correct 4 ms 5012 KB Output is correct
13 Correct 4 ms 4948 KB Output is correct
14 Correct 3 ms 4948 KB Output is correct
15 Correct 3 ms 5012 KB Output is correct
16 Correct 4 ms 4948 KB Output is correct
17 Correct 5 ms 5332 KB Output is correct
18 Correct 4 ms 4948 KB Output is correct
19 Correct 3 ms 4948 KB Output is correct
20 Correct 2233 ms 277080 KB Output is correct
21 Execution timed out 4078 ms 337664 KB Time limit exceeded
22 Halted 0 ms 0 KB -