oj.uz

Submission #146918

# Submission time Handle Problem Language Result Execution time Memory
146918 2019-08-26T15:09:14 Z tincamatei Sky Walking (IOI19_walk) C++14
24 / 100
 654 ms 179312 KB 
#include "walk.h"
#include <bits/stdc++.h>

const int MAX_N = 100000;
const int MAX_M = 100000;
const int MAX_NODES = 11 * MAX_N;
const long long INF = 1LL << 60;

using namespace std;


int lastid;
vector<pair<int, int> > graph[MAX_NODES];
int baseId[MAX_NODES];
vector<int> eventI[MAX_N], eventE[MAX_N];
vector<int> x, h;

priority_queue<pair<long long, int> > coada;
long long dist[MAX_NODES];

struct Skywalk {
	int l, r, h;
	int lastnode;
} skywalk[MAX_M];

struct CmpSkywalk {
	bool operator() (int a, int b) {
		return skywalk[a].h < skywalk[b].h || (skywalk[a].h == skywalk[b].h && a < b);
	}
};

set<int, CmpSkywalk> segs;

void addEdge(int a, int b, int c) {
	graph[a].push_back({b, c});
	graph[b].push_back({a, c});
}

long long runDijkstra(int s, int g) {
	for(int i = 0; i < lastid; ++i)
		dist[i] = INF;
	
	dist[s] = 0;
	coada.push({0, s});

	while(!coada.empty()) {
		long long cost = -coada.top().first;
		int nod = coada.top().second;
		coada.pop();

		if(cost == dist[nod]) {
			for(auto it: graph[nod]) {
				if(cost + it.second < dist[it.first]) {
					dist[it.first] = cost + it.second;
					coada.push({-dist[it.first], it.first});
				}
			}
		}
	}

	if(dist[g] != INF)
		return dist[g];
	return -1;
}

long long min_distance(std::vector<int> _x, std::vector<int> _h, std::vector<int> l, std::vector<int> r, std::vector<int> y, int s, int g) {
	x = _x;
	h = _h;
	int N = x.size();
	int M = l.size();

	for(int i = 0; i < M; ++i) {
		skywalk[i] = {l[i], r[i], y[i], -1};
		eventI[l[i]].push_back(i);
		eventE[r[i]].push_back(i);
	}

	for(int i = 0; i < N; ++i) {
		int base = lastid++, lasth = 0;
		baseId[i] = base;
		for(auto it: eventI[i])
			segs.insert(it);
		
		set<int>::iterator it = segs.begin();
		while(it != segs.end() && skywalk[*it].h <= h[i]) {
			int nod = lastid++;
			addEdge(nod, base, skywalk[*it].h - lasth);
			base = nod;
			lasth = skywalk[*it].h;

			if(skywalk[*it].lastnode != -1) {
				addEdge(base, skywalk[*it].lastnode, x[i] - x[skywalk[*it].l]);
				skywalk[*it].l = i;
			}
			skywalk[*it].lastnode = base;
			it++;
		}

		for(auto it: eventE[i])
			segs.erase(it);
	}

	return runDijkstra(baseId[s], baseId[g]);
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 30840 KB Output is correct
2 Correct 30 ms 30840 KB Output is correct
3 Correct 30 ms 30840 KB Output is correct
4 Correct 31 ms 30840 KB Output is correct
5 Correct 31 ms 30840 KB Output is correct
6 Correct 31 ms 30836 KB Output is correct
7 Correct 31 ms 30968 KB Output is correct
8 Correct 31 ms 30840 KB Output is correct
9 Correct 31 ms 30840 KB Output is correct
10 Correct 31 ms 30968 KB Output is correct
11 Correct 30 ms 30840 KB Output is correct
12 Correct 34 ms 30968 KB Output is correct
13 Correct 31 ms 30840 KB Output is correct
14 Correct 34 ms 30836 KB Output is correct
15 Correct 30 ms 30840 KB Output is correct
16 Correct 30 ms 30840 KB Output is correct
17 Correct 31 ms 30968 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 30840 KB Output is correct
2 Correct 31 ms 30840 KB Output is correct
3 Correct 515 ms 75428 KB Output is correct
4 Correct 501 ms 84600 KB Output is correct
5 Correct 308 ms 76248 KB Output is correct
6 Correct 290 ms 71684 KB Output is correct
7 Correct 308 ms 76280 KB Output is correct
8 Correct 611 ms 86296 KB Output is correct
9 Correct 348 ms 75896 KB Output is correct
10 Correct 654 ms 99832 KB Output is correct
11 Correct 298 ms 58696 KB Output is correct
12 Correct 234 ms 57080 KB Output is correct
13 Correct 550 ms 94584 KB Output is correct
14 Correct 225 ms 53624 KB Output is correct
15 Correct 234 ms 55568 KB Output is correct
16 Correct 229 ms 59256 KB Output is correct
17 Correct 242 ms 58160 KB Output is correct
18 Correct 298 ms 57324 KB Output is correct
19 Correct 38 ms 32120 KB Output is correct
20 Correct 110 ms 43896 KB Output is correct
21 Correct 231 ms 57080 KB Output is correct
22 Correct 213 ms 60280 KB Output is correct
23 Correct 343 ms 65988 KB Output is correct
24 Correct 232 ms 59612 KB Output is correct
25 Correct 221 ms 58232 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 115 ms 40176 KB Output is correct
2 Runtime error 478 ms 179312 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 115 ms 40176 KB Output is correct
2 Runtime error 478 ms 179312 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 30840 KB Output is correct
2 Correct 30 ms 30840 KB Output is correct
3 Correct 30 ms 30840 KB Output is correct
4 Correct 31 ms 30840 KB Output is correct
5 Correct 31 ms 30840 KB Output is correct
6 Correct 31 ms 30836 KB Output is correct
7 Correct 31 ms 30968 KB Output is correct
8 Correct 31 ms 30840 KB Output is correct
9 Correct 31 ms 30840 KB Output is correct
10 Correct 31 ms 30968 KB Output is correct
11 Correct 30 ms 30840 KB Output is correct
12 Correct 34 ms 30968 KB Output is correct
13 Correct 31 ms 30840 KB Output is correct
14 Correct 34 ms 30836 KB Output is correct
15 Correct 30 ms 30840 KB Output is correct
16 Correct 30 ms 30840 KB Output is correct
17 Correct 31 ms 30968 KB Output is correct
18 Correct 30 ms 30840 KB Output is correct
19 Correct 31 ms 30840 KB Output is correct
20 Correct 515 ms 75428 KB Output is correct
21 Correct 501 ms 84600 KB Output is correct
22 Correct 308 ms 76248 KB Output is correct
23 Correct 290 ms 71684 KB Output is correct
24 Correct 308 ms 76280 KB Output is correct
25 Correct 611 ms 86296 KB Output is correct
26 Correct 348 ms 75896 KB Output is correct
27 Correct 654 ms 99832 KB Output is correct
28 Correct 298 ms 58696 KB Output is correct
29 Correct 234 ms 57080 KB Output is correct
30 Correct 550 ms 94584 KB Output is correct
31 Correct 225 ms 53624 KB Output is correct
32 Correct 234 ms 55568 KB Output is correct
33 Correct 229 ms 59256 KB Output is correct
34 Correct 242 ms 58160 KB Output is correct
35 Correct 298 ms 57324 KB Output is correct
36 Correct 38 ms 32120 KB Output is correct
37 Correct 110 ms 43896 KB Output is correct
38 Correct 231 ms 57080 KB Output is correct
39 Correct 213 ms 60280 KB Output is correct
40 Correct 343 ms 65988 KB Output is correct
41 Correct 232 ms 59612 KB Output is correct
42 Correct 221 ms 58232 KB Output is correct
43 Correct 115 ms 40176 KB Output is correct
44 Runtime error 478 ms 179312 KB Execution killed with signal 11 (could be triggered by violating memory limits)
45 Halted 0 ms 0 KB -