Submission #1046041

#	Time	Username	Problem	Language	Result	Execution time	Memory
1046041		idas	Sky Walking (IOI19_walk)	C++17	10 / 100	56 ms	57860 KiB

walk

#include "walk.h"
#include "bits/stdc++.h"
#define FOR(i, begin, end) for(int i=(begin); i<(end); i++)
#define sz(x) ((int)((x).size()))
#define pb push_back
#define s second
#define f first

using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef tuple<int, int, int> tiii;

const int N=2e5+10;
int n, m, id, hgt[N], gr[N];
ll dist[20*N];
vector<pii> ins[N];
vector<pii> ad[N];
bool v[20*N];

long long min_distance(vector<int> x, vector<int> h, vector<int> l, vector<int> r, vector<int> y, int str, int g) {
	n=sz(x); m=sz(l);

	vector<pii> buildings;
	FOR(i, 0, n) {
		buildings.pb({h[i],i});
	}
	sort(buildings.begin(), buildings.end());
	reverse(buildings.begin(), buildings.end());

	set<pii> xs;
	FOR(i, 0, n) xs.insert({x[i],i});

	vector<pii> walks;
	FOR(i, 0, m) {
		walks.pb({y[i],i});
	}
	sort(walks.begin(), walks.end());

	id=n;
	for(auto[y, i] : walks) {
		while(!buildings.empty() && buildings.back().f<y) {
			int in=buildings.back().s;
			xs.erase({x[in],in});
			buildings.pop_back();
		}

		auto it=xs.lower_bound({x[l[i]],0});
		while(it==xs.end()) {}
		// assert((it->f)==x[l[i]]);

		int prv=-1, pos=0;
		while(true) {
			if(prv!=-1) {
				int w=(it->f)-pos;
				ad[prv].pb({id,w});
				ad[id].pb({prv,w});
			}

			prv=id; pos=it->f; hgt[id]=y; gr[id]=it->s;
			ins[it->s].pb({y,id++});

			if(it->s==r[i]) break;
			++it;
		}
	}

	FOR(i, 0, n) {
		hgt[i]=0; gr[i]=i;
		ins[i].pb({0,i});
		sort(ins[i].begin(), ins[i].end());
	}

	FOR(i, 0, 20*N) dist[i]=-1;

	priority_queue<pii, vector<pii>, greater<pii>> q;
	dist[str]=0; q.push({dist[str],str});
	while(!q.empty()) {
		int id=q.top().s; q.pop();

		if(!v[id]) v[id]=true;
		else continue;

		int i=lower_bound(ins[gr[id]].begin(), ins[gr[id]].end(), pii{hgt[id],id})-ins[gr[id]].begin();

		if(i+1<ins[gr[id]].size()) {
			int upper=ins[gr[id]][i+1].s, add=hgt[upper]-hgt[id];
			if(dist[upper]==-1 || dist[upper]>dist[id]+add) {
				dist[upper]=dist[id]+add;
				q.push({dist[upper],upper});
			}
		}
		if(i-1>=0) {
			int lower=ins[gr[id]][i-1].s, add=hgt[id]-hgt[lower];

			if(dist[lower]==-1 || dist[lower]>dist[id]+add) {
				dist[lower]=dist[id]+add;
				q.push({dist[lower],lower});
			}
		}

		for(auto [idx, w] : ad[id]) {
			if(dist[idx]==-1 || dist[idx]>dist[id]+w) {
				dist[idx]=dist[id]+w;
				q.push({dist[idx],idx});
			}
		}
	}

	return dist[g];
}
/*
7 7
0 8
3 7
5 9
7 7
10 6
12 6
14 9
0 1 1
0 2 6
0 6 8
2 3 1
2 6 7
3 4 2
4 6 5
0 6

3 5
0 3
3 3
5 2
0 1 2
0 1 1
1 2 1
1 2 2
0 1 3
2 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:87:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |   if(i+1<ins[gr[id]].size()) {
      |      ~~~^~~~~~~~~~~~~~~~~~~

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