oj.uz

Submission #590881

# Submission time Handle Problem Language Result Execution time Memory
590881 2022-07-06T12:42:07 Z 8e7 Sky Walking (IOI19_walk) C++17
10 / 100
 2001 ms 1048576 KB 
//Challenge: Accepted
#include "walk.h"
#include <bits/stdc++.h>
using namespace std;
#ifdef zisk
void debug(){cout << endl;}
template<class T, class ... U> void debug(T a, U ... b){cout << a << " ", debug(b...);}
template<class T> void pary(T l, T r) {
	while (l != r)cout << *l << " ", l++;
	cout << endl;
}
#else
#define debug(...) 0
#define pary(...) 0
#endif
#define ll long long
#define maxn 100005
#define maxv 1200005
#define pii pair<ll, ll>
#define ff first
#define ss second
const ll inf = 1LL<<60;
vector<pii> adj[maxv];
ll dis[maxv];
int prv[maxn], px[maxn];
vector<pii> seg[maxn];
bool on[maxn];
long long min_distance(vector<int> X, vector<int> H, vector<int> L, vector<int> R, vector<int> Y, int st, int ed) {
	int n = X.size(), m = L.size();
	for (int i = 0;i < m;i++) {
		for (int j = L[i];j <= R[i];j++) {
			seg[j].push_back({Y[i], i});
		}
	}
	for (int i = 0;i < n;i++) sort(seg[i].begin(), seg[i].end());
	auto addedge = [&] (int u, int v, int w){
		adj[u].push_back({v, w});
		adj[v].push_back({u, w});
		debug(u, v, w);
	};
	int term = maxv - 1;
	{
		int cur = 1;
		for (int i = 0;i < n;i++) {
			for (int j = 0;j < seg[i].size();j++) {
				int id = seg[i][j].ss;
				int y = Y[id], node = cur++;

				if (i == st && y <= H[i]) addedge(node, 0, y);
				if (i == ed && y <= H[i]) addedge(node, term, y);
				if (on[id]) {
					addedge(node, prv[id], X[i] - px[id]);
				} else {
					on[id] = 1;
				}
				if (j && y <= H[i]) addedge(node, node-1, y - seg[i][j-1].ff);
				prv[id] = node;
				px[id] = X[i];
			}
		}
	}
	for (int i = 0;i < maxv;i++) dis[i] = inf;	
	dis[0] = 0;	
	priority_queue<pii, vector<pii>, greater<pii> > pq;
	pq.push({0, 0});
	while (pq.size()) {
		auto [d, cur] = pq.top();
		pq.pop();
		if (d != dis[cur]) continue;
		for (auto [v, w]:adj[cur]) {
			if (d + w < dis[v]) {
				dis[v] = d + w;
				pq.push({dis[v], v});
			}
		}
	}
	if (dis[term] == inf) return -1;
	return dis[term];
}

Compilation message

walk.cpp: In lambda function:
walk.cpp:13:20: warning: statement has no effect [-Wunused-value]
   13 | #define debug(...) 0
      |                    ^
walk.cpp:39:3: note: in expansion of macro 'debug'
   39 |   debug(u, v, w);
      |   ^~~~~
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:45:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |    for (int j = 0;j < seg[i].size();j++) {
      |                   ~~^~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 40160 KB Output is correct
2 Correct 19 ms 40168 KB Output is correct
3 Correct 22 ms 40188 KB Output is correct
4 Correct 19 ms 40148 KB Output is correct
5 Correct 19 ms 40276 KB Output is correct
6 Correct 19 ms 40192 KB Output is correct
7 Correct 18 ms 40268 KB Output is correct
8 Correct 19 ms 40188 KB Output is correct
9 Correct 21 ms 40168 KB Output is correct
10 Correct 19 ms 40276 KB Output is correct
11 Correct 19 ms 40188 KB Output is correct
12 Correct 18 ms 40188 KB Output is correct
13 Correct 18 ms 40276 KB Output is correct
14 Correct 19 ms 40220 KB Output is correct
15 Correct 19 ms 40168 KB Output is correct
16 Correct 23 ms 40140 KB Output is correct
17 Correct 19 ms 40256 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 40148 KB Output is correct
2 Correct 21 ms 40252 KB Output is correct
3 Correct 374 ms 124824 KB Output is correct
4 Correct 396 ms 124400 KB Output is correct
5 Runtime error 2001 ms 1048576 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 52864 KB Output is correct
2 Runtime error 757 ms 463800 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 52864 KB Output is correct
2 Runtime error 757 ms 463800 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 40160 KB Output is correct
2 Correct 19 ms 40168 KB Output is correct
3 Correct 22 ms 40188 KB Output is correct
4 Correct 19 ms 40148 KB Output is correct
5 Correct 19 ms 40276 KB Output is correct
6 Correct 19 ms 40192 KB Output is correct
7 Correct 18 ms 40268 KB Output is correct
8 Correct 19 ms 40188 KB Output is correct
9 Correct 21 ms 40168 KB Output is correct
10 Correct 19 ms 40276 KB Output is correct
11 Correct 19 ms 40188 KB Output is correct
12 Correct 18 ms 40188 KB Output is correct
13 Correct 18 ms 40276 KB Output is correct
14 Correct 19 ms 40220 KB Output is correct
15 Correct 19 ms 40168 KB Output is correct
16 Correct 23 ms 40140 KB Output is correct
17 Correct 19 ms 40256 KB Output is correct
18 Correct 19 ms 40148 KB Output is correct
19 Correct 21 ms 40252 KB Output is correct
20 Correct 374 ms 124824 KB Output is correct
21 Correct 396 ms 124400 KB Output is correct
22 Runtime error 2001 ms 1048576 KB Execution killed with signal 11
23 Halted 0 ms 0 KB -