oj.uz

Submission #146907

# Submission time Handle Problem Language Result Execution time Memory
146907 2019-08-26T14:50:52 Z tincamatei Sky Walking (IOI19_walk) C++14
0 / 100
 657 ms 103676 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;
	}
};

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].lastnode = base;
			skywalk[*it].l = i;
			it++;
		}

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

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

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 30840 KB Output is correct
2 Correct 30 ms 30840 KB Output is correct
3 Incorrect 30 ms 30840 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 30840 KB Output is correct
2 Correct 30 ms 30844 KB Output is correct
3 Correct 488 ms 77360 KB Output is correct
4 Correct 524 ms 88476 KB Output is correct
5 Correct 319 ms 79844 KB Output is correct
6 Correct 300 ms 75256 KB Output is correct
7 Correct 314 ms 79864 KB Output is correct
8 Correct 606 ms 88452 KB Output is correct
9 Correct 367 ms 79660 KB Output is correct
10 Correct 657 ms 103676 KB Output is correct
11 Correct 304 ms 61508 KB Output is correct
12 Correct 240 ms 61176 KB Output is correct
13 Correct 569 ms 98660 KB Output is correct
14 Correct 224 ms 57332 KB Output is correct
15 Incorrect 237 ms 59000 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 75 ms 36856 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 75 ms 36856 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 30840 KB Output is correct
2 Correct 30 ms 30840 KB Output is correct
3 Incorrect 30 ms 30840 KB Output isn't correct
4 Halted 0 ms 0 KB -