oj.uz

Submission #590884

# Submission time Handle Problem Language Result Execution time Memory
590884 2022-07-06T12:47:32 Z 8e7 Sky Walking (IOI19_walk) C++17
24 / 100
 598 ms 437712 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];


vector<int> lft[maxn], rht[maxn];
bool vis[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++) {
		lft[L[i]].push_back(i);	
		rht[R[i]].push_back(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);
	};
	{
		set<pii> se;
		for (int i = 0;i < n;i++) {
			for (int id:lft[i]) {
				se.insert({Y[id], id});
			}
			auto it = se.begin();
			while (it != se.end()) {
				if (it->ff > H[i]) break;	
				seg[i].push_back(*it);
				it = next(it);
			}
			for (int id:rht[i]) {
				se.erase(se.find(make_pair(Y[id], id)));
			}
		}
	}
	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:42:3: note: in expansion of macro 'debug'
   42 |   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:65: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]
   65 |    for (int j = 0;j < seg[i].size();j++) {
      |                   ~~^~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 44904 KB Output is correct
2 Correct 26 ms 44868 KB Output is correct
3 Correct 23 ms 44880 KB Output is correct
4 Correct 24 ms 44884 KB Output is correct
5 Correct 22 ms 44884 KB Output is correct
6 Correct 22 ms 44880 KB Output is correct
7 Correct 21 ms 45012 KB Output is correct
8 Correct 23 ms 44884 KB Output is correct
9 Correct 22 ms 44856 KB Output is correct
10 Correct 28 ms 44976 KB Output is correct
11 Correct 28 ms 44908 KB Output is correct
12 Correct 23 ms 44884 KB Output is correct
13 Correct 21 ms 44884 KB Output is correct
14 Correct 23 ms 44884 KB Output is correct
15 Correct 21 ms 44884 KB Output is correct
16 Correct 22 ms 44888 KB Output is correct
17 Correct 25 ms 44912 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 44884 KB Output is correct
2 Correct 26 ms 44884 KB Output is correct
3 Correct 358 ms 123520 KB Output is correct
4 Correct 386 ms 125600 KB Output is correct
5 Correct 236 ms 114908 KB Output is correct
6 Correct 202 ms 106352 KB Output is correct
7 Correct 228 ms 114980 KB Output is correct
8 Correct 482 ms 142808 KB Output is correct
9 Correct 243 ms 115432 KB Output is correct
10 Correct 456 ms 157524 KB Output is correct
11 Correct 233 ms 87864 KB Output is correct
12 Correct 129 ms 73956 KB Output is correct
13 Correct 377 ms 148388 KB Output is correct
14 Correct 166 ms 71248 KB Output is correct
15 Correct 137 ms 72908 KB Output is correct
16 Correct 140 ms 74208 KB Output is correct
17 Correct 148 ms 73240 KB Output is correct
18 Correct 167 ms 78040 KB Output is correct
19 Correct 27 ms 46220 KB Output is correct
20 Correct 77 ms 58176 KB Output is correct
21 Correct 129 ms 72820 KB Output is correct
22 Correct 124 ms 73164 KB Output is correct
23 Correct 205 ms 81232 KB Output is correct
24 Correct 155 ms 73620 KB Output is correct
25 Correct 133 ms 73640 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 58196 KB Output is correct
2 Runtime error 598 ms 437712 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 67 ms 58196 KB Output is correct
2 Runtime error 598 ms 437712 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 21 ms 44904 KB Output is correct
2 Correct 26 ms 44868 KB Output is correct
3 Correct 23 ms 44880 KB Output is correct
4 Correct 24 ms 44884 KB Output is correct
5 Correct 22 ms 44884 KB Output is correct
6 Correct 22 ms 44880 KB Output is correct
7 Correct 21 ms 45012 KB Output is correct
8 Correct 23 ms 44884 KB Output is correct
9 Correct 22 ms 44856 KB Output is correct
10 Correct 28 ms 44976 KB Output is correct
11 Correct 28 ms 44908 KB Output is correct
12 Correct 23 ms 44884 KB Output is correct
13 Correct 21 ms 44884 KB Output is correct
14 Correct 23 ms 44884 KB Output is correct
15 Correct 21 ms 44884 KB Output is correct
16 Correct 22 ms 44888 KB Output is correct
17 Correct 25 ms 44912 KB Output is correct
18 Correct 22 ms 44884 KB Output is correct
19 Correct 26 ms 44884 KB Output is correct
20 Correct 358 ms 123520 KB Output is correct
21 Correct 386 ms 125600 KB Output is correct
22 Correct 236 ms 114908 KB Output is correct
23 Correct 202 ms 106352 KB Output is correct
24 Correct 228 ms 114980 KB Output is correct
25 Correct 482 ms 142808 KB Output is correct
26 Correct 243 ms 115432 KB Output is correct
27 Correct 456 ms 157524 KB Output is correct
28 Correct 233 ms 87864 KB Output is correct
29 Correct 129 ms 73956 KB Output is correct
30 Correct 377 ms 148388 KB Output is correct
31 Correct 166 ms 71248 KB Output is correct
32 Correct 137 ms 72908 KB Output is correct
33 Correct 140 ms 74208 KB Output is correct
34 Correct 148 ms 73240 KB Output is correct
35 Correct 167 ms 78040 KB Output is correct
36 Correct 27 ms 46220 KB Output is correct
37 Correct 77 ms 58176 KB Output is correct
38 Correct 129 ms 72820 KB Output is correct
39 Correct 124 ms 73164 KB Output is correct
40 Correct 205 ms 81232 KB Output is correct
41 Correct 155 ms 73620 KB Output is correct
42 Correct 133 ms 73640 KB Output is correct
43 Correct 67 ms 58196 KB Output is correct
44 Runtime error 598 ms 437712 KB Execution killed with signal 11
45 Halted 0 ms 0 KB -