oj.uz

Submission #146917

# Submission time Handle Problem Language Result Execution time Memory
146917 2019-08-26T15:07:55 Z tincamatei Sky Walking (IOI19_walk) C++14
0 / 100
 96 ms 39928 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;
		set<int>::iterator it = segs.begin();
		for(auto it: eventI[i])
			segs.insert(it);
		
		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
0 / 10.0

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

Subtask #2
0 / 14.0

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

Subtask #3
0 / 15.0

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

Subtask #4
0 / 18.0

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

Subtask #5
0 / 43.0

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