oj.uz

Submission #430673

# Submission time Handle Problem Language Result Execution time Memory
430673 2021-06-16T18:12:54 Z saleh Sky Walking (IOI19_walk) C++17
24 / 100
 1806 ms 359472 KB 
#include "walk.h"
#include <bits/stdc++.h>

#define int long long
#define ft first
#define sd second

using namespace std;

typedef pair<int, int> pii;

const int MAXN = 100 * 1000 + 23, MAXV = 1000 * 1000 + 23, MAXE = 4000 * 1000 + 23, INF = 1e15;

int n, m, cnt, dis[MAXV];
vector<int> add[MAXN], del[MAXN], pt[MAXN];
set<pii> s;
map<int, int> mp[MAXN];
vector<pii> pts, g[MAXV];

void dij(int v) {/*
	for (int i = 0; i < cnt; i++) {
		cout << "\\" << i << ": " << pts[i].ft << ' ' << pts[i].sd << endl << '\t';
		for (auto j : g[i]) cout << j.ft << ' ' << j.sd << '\t';
		cout << endl;
	}*/
	priority_queue<pii, vector<pii>, greater<pii>> pq;
	pq.push({0, v});
	for (int i = 0; i < cnt; i++) dis[i] = INF;
	dis[v] = 0;
	while (!pq.empty()) {
		pii x = pq.top();
		pq.pop();
		if (x.ft > dis[x.sd]) continue;
		for (auto i : g[x.sd]) if (dis[i.ft] > dis[x.sd] + i.sd) {
			dis[i.ft] = dis[x.sd] + i.sd;
			pq.push({dis[i.ft], i.ft});
		}
	}
}

long long min_distance(vector<int32_t> x, vector<int32_t> h, vector<int32_t> l, vector<int32_t> r, vector<int32_t> y, int32_t ss, int32_t gg) {
	int tmp = 0;
	n = x.size();
	m = l.size();
	for (int i = 0; i < m; i++) add[l[i]].push_back(i), del[r[i]].push_back(i);
	for (int j = 0; j < n; j++) {
		for (auto i : add[j]) s.insert({y[i], i});
		if (ss == j && s.size() && s.begin() -> ft <= h[j]) {
			ss = -cnt;
			tmp += s.begin() -> ft;
		} else if (ss == j) return -1;
		if (gg == j && s.size() && s.begin() -> ft <= h[j]) {
			gg = -cnt;
			tmp += s.begin() -> ft;
		} else if (gg == j) return -1;
		pii prev = {-1, -1};
		for (auto i : s) {
			if (i.ft > h[j]) break;
			pts.push_back({i.sd, j});
			mp[i.sd][j] = cnt++;
			pt[i.sd].push_back(j);
			if (prev.sd != -1) g[cnt - 1].push_back({cnt - 2, i.ft - prev.ft}), g[cnt - 2].push_back({cnt - 1, i.ft - prev.ft});
			prev = i;
		}
		for (auto i : del[j]) s.erase({y[i], i});
	}
	ss = -ss;
	gg = -gg;
	for (int i = 0; i < m; i++) for (int j = 1; j < (int)pt[i].size(); j++)
		g[mp[i][pt[i][j - 1]]].push_back({mp[i][pt[i][j]], x[pt[i][j]] - x[pt[i][j - 1]]}), g[mp[i][pt[i][j]]].push_back({mp[i][pt[i][j - 1]], x[pt[i][j]] - x[pt[i][j - 1]]});
	dij(ss);
	return (dis[gg] == INF? -1: dis[gg] + tmp);
}/*
int32_t main() { cout << min_distance({0, 3, 5, 7, 10, 12, 14},
{8, 7, 9, 7, 6, 6, 9},
{0, 0, 0, 2, 2, 3, 4},
{1, 2, 6, 3, 6, 4, 6},
{1, 6, 8, 1, 7, 2, 5},
1, 5); }*/

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 35508 KB Output is correct
2 Correct 24 ms 35532 KB Output is correct
3 Correct 25 ms 35536 KB Output is correct
4 Correct 25 ms 35532 KB Output is correct
5 Correct 26 ms 35664 KB Output is correct
6 Correct 25 ms 35532 KB Output is correct
7 Correct 27 ms 35708 KB Output is correct
8 Correct 25 ms 35640 KB Output is correct
9 Correct 29 ms 35540 KB Output is correct
10 Correct 26 ms 35612 KB Output is correct
11 Correct 24 ms 35540 KB Output is correct
12 Correct 24 ms 35556 KB Output is correct
13 Correct 24 ms 35520 KB Output is correct
14 Correct 25 ms 35532 KB Output is correct
15 Correct 22 ms 35536 KB Output is correct
16 Correct 29 ms 35532 KB Output is correct
17 Correct 26 ms 35648 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 35428 KB Output is correct
2 Correct 25 ms 35472 KB Output is correct
3 Correct 1436 ms 190256 KB Output is correct
4 Correct 1073 ms 187648 KB Output is correct
5 Correct 763 ms 164156 KB Output is correct
6 Correct 730 ms 147380 KB Output is correct
7 Correct 758 ms 164340 KB Output is correct
8 Correct 1806 ms 234864 KB Output is correct
9 Correct 847 ms 166348 KB Output is correct
10 Correct 1517 ms 253296 KB Output is correct
11 Correct 636 ms 114824 KB Output is correct
12 Correct 357 ms 83368 KB Output is correct
13 Correct 1243 ms 225240 KB Output is correct
14 Correct 184 ms 56844 KB Output is correct
15 Correct 402 ms 80532 KB Output is correct
16 Correct 430 ms 83756 KB Output is correct
17 Correct 387 ms 82288 KB Output is correct
18 Correct 515 ms 92460 KB Output is correct
19 Correct 33 ms 37576 KB Output is correct
20 Correct 133 ms 56932 KB Output is correct
21 Correct 414 ms 80248 KB Output is correct
22 Correct 398 ms 82508 KB Output is correct
23 Correct 537 ms 93428 KB Output is correct
24 Correct 474 ms 82860 KB Output is correct
25 Correct 399 ms 82096 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 179 ms 60724 KB Output is correct
2 Runtime error 1522 ms 359472 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 179 ms 60724 KB Output is correct
2 Runtime error 1522 ms 359472 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 35508 KB Output is correct
2 Correct 24 ms 35532 KB Output is correct
3 Correct 25 ms 35536 KB Output is correct
4 Correct 25 ms 35532 KB Output is correct
5 Correct 26 ms 35664 KB Output is correct
6 Correct 25 ms 35532 KB Output is correct
7 Correct 27 ms 35708 KB Output is correct
8 Correct 25 ms 35640 KB Output is correct
9 Correct 29 ms 35540 KB Output is correct
10 Correct 26 ms 35612 KB Output is correct
11 Correct 24 ms 35540 KB Output is correct
12 Correct 24 ms 35556 KB Output is correct
13 Correct 24 ms 35520 KB Output is correct
14 Correct 25 ms 35532 KB Output is correct
15 Correct 22 ms 35536 KB Output is correct
16 Correct 29 ms 35532 KB Output is correct
17 Correct 26 ms 35648 KB Output is correct
18 Correct 24 ms 35428 KB Output is correct
19 Correct 25 ms 35472 KB Output is correct
20 Correct 1436 ms 190256 KB Output is correct
21 Correct 1073 ms 187648 KB Output is correct
22 Correct 763 ms 164156 KB Output is correct
23 Correct 730 ms 147380 KB Output is correct
24 Correct 758 ms 164340 KB Output is correct
25 Correct 1806 ms 234864 KB Output is correct
26 Correct 847 ms 166348 KB Output is correct
27 Correct 1517 ms 253296 KB Output is correct
28 Correct 636 ms 114824 KB Output is correct
29 Correct 357 ms 83368 KB Output is correct
30 Correct 1243 ms 225240 KB Output is correct
31 Correct 184 ms 56844 KB Output is correct
32 Correct 402 ms 80532 KB Output is correct
33 Correct 430 ms 83756 KB Output is correct
34 Correct 387 ms 82288 KB Output is correct
35 Correct 515 ms 92460 KB Output is correct
36 Correct 33 ms 37576 KB Output is correct
37 Correct 133 ms 56932 KB Output is correct
38 Correct 414 ms 80248 KB Output is correct
39 Correct 398 ms 82508 KB Output is correct
40 Correct 537 ms 93428 KB Output is correct
41 Correct 474 ms 82860 KB Output is correct
42 Correct 399 ms 82096 KB Output is correct
43 Correct 179 ms 60724 KB Output is correct
44 Runtime error 1522 ms 359472 KB Execution killed with signal 6
45 Halted 0 ms 0 KB -