Submission #433894

#	Time	Username	Problem	Language	Result	Execution time	Memory
433894		kostia244	Sky Walking (IOI19_walk)	C++17	24 / 100	3961 ms	1048580 KiB

walk

#include "walk.h"
#include<bits/stdc++.h>
#define all(x) begin(x), end(x)
using namespace std;
using ll = long long;

ll min_distance(vector<int> x, vector<int> h, vector<int> l, vector<int> r, vector<int> y, int U, int V) {
	int n = x.size(), m = l.size();
	vector<vector<array<int, 2>>> g;
	vector<vector<int>> on(n+1);
	vector<int> col, lst(m, -1), start(n);
	for(int i = 0; i < m; i++) {
		on[l[i]].push_back(i);
		on[r[i]+1].push_back(-1-i);
	}
	set<array<int, 2>> hv;
	for(int i = 0; i < n; i++) {
		for(auto id : on[i]) {
			if(id < 0) {
				id = -id-1;
				hv.erase({y[id], id});
			} else
				hv.insert({y[id], id});
		}
		start[i] = g.size();
		g.push_back({});//(i, 0)
		col.push_back(i);
		int loh = 0;
		auto it = hv.begin();
		while(it != hv.end() && it->at(0) <= h[i]) {
			int id = it->at(1);
			g.back().push_back({g.size(), y[id]-loh});
			g.push_back({{g.size()-1, y[id]-loh}});
			//cout << g.size()-1 << " " << g.size()-2 << " " << y[id]-loh << endl;
			col.push_back(i);
			//cout << i << " " << id << "uwu\n";
			if(lst[id] != -1) {
				g[lst[id]].push_back({g.size()-1, x[i]-x[col[lst[id]]]});
				g.back().push_back({lst[id], x[i]-x[col[lst[id]]]});
			}
			lst[id] = g.size()-1;
			loh = y[id];
			it++;
		}	
	}
	U = start[U];
	V = start[V];
	priority_queue<array<ll, 2>> pq;
	vector<ll> dist(g.size(), 1ll<<60);
	auto enq = [&](int v, ll d) {
		//if(col[v] > 1) return;///REMOVE
		if(dist[v] <= d) return;
		dist[v] = d;
		pq.push({-dist[v], v});
	};
	//cout << U << " " << V << endl;
	for(enq(U, 0); !pq.empty();) {
		auto [di, v] = pq.top();
		pq.pop();
		di *= -1;
		if(di > dist[v]) continue;
		//cout << v << " at " << dist[v] << " ? " << col[v] << endl;
		if(v == V) return dist[v];
		for(auto [i, w] : g[v]) {
			//cout << v << " -> " << i << " " << w << endl;
			enq(i, di+w);
		}
	}
	//for(int i = 0; i < g.size(); i++) cout << col[i] << " "; cout << endl;
	//for(int i = 0; i < g.size(); i++) cout << dist[i] << " "; cout << endl;
	return -1;
}

Compilation message (stderr)

walk.cpp: In function 'll min_distance(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, int, int)':
walk.cpp:32:30: warning: narrowing conversion of 'g.std::vector<std::vector<std::array<int, 2> > >::size()' from 'std::vector<std::vector<std::array<int, 2> > >::size_type' {aka 'long unsigned int'} to 'int' [-Wnarrowing]
   32 |    g.back().push_back({g.size(), y[id]-loh});
      |                        ~~~~~~^~
walk.cpp:33:26: warning: narrowing conversion of '(g.std::vector<std::vector<std::array<int, 2> > >::size() - 1)' from 'std::vector<std::vector<std::array<int, 2> > >::size_type' {aka 'long unsigned int'} to 'int' [-Wnarrowing]
   33 |    g.push_back({{g.size()-1, y[id]-loh}});
      |                  ~~~~~~~~^~
walk.cpp:38:35: warning: narrowing conversion of '(g.std::vector<std::vector<std::array<int, 2> > >::size() - 1)' from 'std::vector<std::vector<std::array<int, 2> > >::size_type' {aka 'long unsigned int'} to 'int' [-Wnarrowing]
   38 |     g[lst[id]].push_back({g.size()-1, x[i]-x[col[lst[id]]]});
      |                           ~~~~~~~~^~

• Subtask 1: 10 / 10
• Subtask 2: 14 / 14
• Subtask 3: 0 / 15
• Subtask 4: 0 / 18
• Subtask 5: 0 / 43