Submission #295018

#	Time	Username	Problem	Language	Result	Execution time	Memory
295018		egekabas	Sky Walking (IOI19_walk)	C++14	0 / 100	4086 ms	46180 KiB

walk

#include "walk.h"
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<ull, ull> pull;
typedef pair<int, int> pii;
typedef pair<ld, ld> pld;
struct sky{
	int id, l, r, y;
};
bool cmp(sky a, sky b){
	if(a.y == b.y)
		return a.l < b.l;
	return a.y < b.y;
} 
vector<int> godown[100009];
vector<int> goup[100009];
vector<ll> dis[100009];
long long min_distance(vector<int> x, vector<int> h, vector<int> l, vector<int> r, vector<int> y, int s, int g){
	vector<sky> tmp;
	for(int i = 0; i < l.size(); ++i)
		tmp.pb({i, l[i], r[i], y[i]});
	sort(all(tmp), cmp);
	vector<sky> top;
	for(auto u : tmp){
		if(top.size() && top.back().y == u.y && top.back().r == u.l)
			top.back().r = u.r;
		else
			top.pb(u);
	}
	vector<pii> add;
	vector<pii> era;
	for(int i = 0; i < top.size(); ++i){
		top[i].id = i;
		add.pb({x[top[i].l], i});
		era.pb({x[top[i].r]+1, i});
	}
	sort(all(add), greater<pii>());
	sort(all(era), greater<pii>());
	set<pii> st;
	for(int i = 0; i < x.size(); ++i){
		while(add.size() && add.back().ff <= x[i]){
			st.insert({top[add.back().ss].y, add.back().ss});
			add.pop_back();
		}
		while(era.size() && era.back().ff <= x[i]){
			st.erase({top[era.back().ss].y, era.back().ss});
			era.pop_back();
		}
		for(auto u : st){
			if(u.ff > h[i]) break;
			godown[u.ss].pb(i);
			goup[i].pb(u.ss);
		}
		/*cout << i << '\n';
		for(auto u : goup[i])
			cout << top[u].l << ' ' << top[u].r << '\n';*/
		sort(all(goup[i]));
		dis[i].resize(goup[i].size()+1, 1e18);
	}
	
	priority_queue<pair<ll, pll>, vector<pair<ll, pll>>, greater<pair<ll, pll>>> pq;
	dis[s][0] = 0;
	pq.push({0, {s, 0}});
	while(pq.size()){
		ll d = pq.top().ff;
		ll id = pq.top().ss.ff;
		ll lev = pq.top().ss.ss;
		pq.pop();
		if(dis[id][lev] < d)
			continue;
		for(ll i = 0; i < dis[id].size(); ++i){
			ll nd = d;
			ll dissurf = 0;
			if(lev != 0)
				dissurf = top[goup[id][lev-1]].y;
			if(i == 0)
				nd += dissurf;
			else
				nd += abs(dissurf-top[goup[id][i-1]].y);
			if(nd < dis[id][i]){
				dis[id][i] = nd;
				pq.push({nd, {id, i}});
			}
		}
		if(lev == 0) continue;
		for(auto u : godown[goup[id][lev-1]]){
			ll nd = d + abs(x[id]-x[u]);
			ll nl = lower_bound(all(goup[u]), goup[id][lev-1])-goup[u].begin()+1;
			if(nd < dis[u][nl]){
				dis[u][nl] = nd;
				pq.push({nd, {u, nl}});
			}
		}
	}
	return dis[g][0];
}

Compilation message (stderr)

walk.cpp: In function 'long long int min_distance(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, int, int)':
walk.cpp:29:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |  for(int i = 0; i < l.size(); ++i)
      |                 ~~^~~~~~~~~~
walk.cpp:41:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<sky>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |  for(int i = 0; i < top.size(); ++i){
      |                 ~~^~~~~~~~~~~~
walk.cpp:49:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |  for(int i = 0; i < x.size(); ++i){
      |                 ~~^~~~~~~~~~
walk.cpp:80:19: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |   for(ll i = 0; i < dis[id].size(); ++i){
      |                 ~~^~~~~~~~~~~~~~~~

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