oj.uz

Submission #431349

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

vector<pair<int, int>> g[1 << 21];
vector<long long> dp(1 << 21, -1);

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];
	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) {
		int j = add[i].second;
		while (now.size() && now.back().first >= add[i].first) {
			is.insert(now.back().second);
			now.pop_back();
		}
		auto it = is.lower_bound(l[j]);
		while (it != is.end() && *it <= r[j]) {
			if (it == is.end()) break;
			if (!can[*it].count(y[j]))
				can[*it][y[j]] = ++sz;
			if (it != is.begin() && *prev(it) >= l[j]) {
				g[can[*it][y[j]]].push_back({can[*prev(it)][y[j]], x[*it] - x[*prev(it)]});
				g[can[*prev(it)][y[j]]].push_back({can[*it][y[j]], x[*it] - x[*prev(it)]});
			}
			it = next(it);
		}
	}
	for (int i = 0; i < n; ++i) {
		int last = 0, pos = i;

		for (auto it = can[i].begin(); it != can[i].end(); ++it) {
			g[pos].push_back({it->second, it->first - last});
			g[it->second].push_back({pos, it->first - last});
			last = it->first;
			pos = it->second;
		}
	}
	priority_queue<pair<long long, int>, vector<pair<long long, int>>, less<pair<long long, int>>> q;
	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:64:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   64 |   for (auto [to, c] : g[v]) {
      |             ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 65928 KB Output is correct
2 Correct 36 ms 65928 KB Output is correct
3 Correct 37 ms 65964 KB Output is correct
4 Correct 38 ms 65916 KB Output is correct
5 Correct 54 ms 66088 KB Output is correct
6 Correct 50 ms 66028 KB Output is correct
7 Correct 46 ms 65920 KB Output is correct
8 Correct 40 ms 65912 KB Output is correct
9 Correct 43 ms 65964 KB Output is correct
10 Correct 65 ms 65988 KB Output is correct
11 Correct 38 ms 65884 KB Output is correct
12 Correct 47 ms 65884 KB Output is correct
13 Correct 40 ms 65900 KB Output is correct
14 Correct 39 ms 65956 KB Output is correct
15 Correct 38 ms 65952 KB Output is correct
16 Correct 37 ms 65864 KB Output is correct
17 Correct 56 ms 66044 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 65860 KB Output is correct
2 Correct 43 ms 65852 KB Output is correct
3 Execution timed out 4089 ms 157520 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4074 ms 76608 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4074 ms 76608 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 65928 KB Output is correct
2 Correct 36 ms 65928 KB Output is correct
3 Correct 37 ms 65964 KB Output is correct
4 Correct 38 ms 65916 KB Output is correct
5 Correct 54 ms 66088 KB Output is correct
6 Correct 50 ms 66028 KB Output is correct
7 Correct 46 ms 65920 KB Output is correct
8 Correct 40 ms 65912 KB Output is correct
9 Correct 43 ms 65964 KB Output is correct
10 Correct 65 ms 65988 KB Output is correct
11 Correct 38 ms 65884 KB Output is correct
12 Correct 47 ms 65884 KB Output is correct
13 Correct 40 ms 65900 KB Output is correct
14 Correct 39 ms 65956 KB Output is correct
15 Correct 38 ms 65952 KB Output is correct
16 Correct 37 ms 65864 KB Output is correct
17 Correct 56 ms 66044 KB Output is correct
18 Correct 45 ms 65860 KB Output is correct
19 Correct 43 ms 65852 KB Output is correct
20 Execution timed out 4089 ms 157520 KB Time limit exceeded
21 Halted 0 ms 0 KB -