oj.uz

Submission #431327

# Submission time Handle Problem Language Result Execution time Memory
431327 2021-06-17T11:00:48 Z _fractal Sky Walking (IOI19_walk) C++14
0 / 100
 1701 ms 146112 KB 
#include "walk.h"
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
#include <iostream>
using namespace std;

long long min_distance(vector<int> x, vector<int> h, vector<int> l, vector<int> r, vector<int> y, int s, int e) {
	int n = x.size();
	int m = l.size();
	int sz = n - 1;
	vector<pair<int, int>> add, now;
	set<int> is;
	map<int, int> can[n];
	vector<pair<int, int>> g[1 << 20];
	for (int i = 0; i < m; ++i)
		add.push_back({y[i], i});
	for (int i = 0; i < n; ++i)
		now.push_back({h[i], i});
	sort(add.begin(), add.end());
	reverse(add.begin(), add.end());
	sort(now.begin(), now.end());
	for (int i = 0; i < m; ++i) {
		while (now.size() && now.back().first >= add[i].first) {
			is.insert(now.back().second);
			now.pop_back();
		}
		int j = add[i].second;
		auto it = is.lower_bound(l[j]);
		while (it != is.end() && *it <= r[i]) {
			if (!can[*it].count(y[i]))
				can[*it][y[i]] = ++sz;
			if (it != is.begin() && *prev(it) >= l[i]) {
				g[can[*it][y[i]]].push_back({can[*prev(it)][y[i]], x[*it] - x[*prev(it)]});
				g[can[*prev(it)][y[i]]].push_back({can[*it][y[i]], x[*it] - x[*prev(it)]});
			}
			it = next(it);
		}
	}
	for (int i = 0; i < n; ++i) {
		int last = 0;
		for (auto it = can[i].begin(); it != can[i].end(); ++i) {
			g[i].push_back({it->second, it->first - last});
			g[it->second].push_back({i, it->first - last});
			last = it->first;
		}
	}
	priority_queue<pair<long long, int>, vector<pair<long long, int>>, less<pair<long long, int>>> q;
	vector<long long> dp(1 << 20, -1);
	q.push({0, s});
	dp[s] = 0;
	while (!q.empty()) {
		int v = q.top().second;
		long long C = q.top().first;
		q.pop();
		if (dp[v] < C)
			continue;
		for (auto [to, c] : g[v]) {
			if (dp[to] == -1 || dp[to] > dp[v] + c) {
				dp[to] = dp[v] + c;
				q.push({dp[to], to});	
			}
		}
	}
	return dp[e];
}

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:60:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   60 |   for (auto [to, c] : g[v]) {
      |             ^

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 161 ms 133536 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 152 ms 133436 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 1701 ms 146112 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 1701 ms 146112 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Runtime error 161 ms 133536 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -