Submission #590884

#	Time	Username	Problem	Language	Result	Execution time	Memory
590884		8e7	Sky Walking (IOI19_walk)	C++17	24 / 100	598 ms	437712 KiB

walk

//Challenge: Accepted
#include "walk.h"
#include <bits/stdc++.h>
using namespace std;
#ifdef zisk
void debug(){cout << endl;}
template<class T, class ... U> void debug(T a, U ... b){cout << a << " ", debug(b...);}
template<class T> void pary(T l, T r) {
	while (l != r)cout << *l << " ", l++;
	cout << endl;
}
#else
#define debug(...) 0
#define pary(...) 0
#endif
#define ll long long
#define maxn 100005
#define maxv 1200005
#define pii pair<ll, ll>
#define ff first
#define ss second
const ll inf = 1LL<<60;
vector<pii> adj[maxv];
ll dis[maxv];
int prv[maxn], px[maxn];
vector<pii> seg[maxn];
bool on[maxn];


vector<int> lft[maxn], rht[maxn];
bool vis[maxn];
long long min_distance(vector<int> X, vector<int> H, vector<int> L, vector<int> R, vector<int> Y, int st, int ed) {
	int n = X.size(), m = L.size();
	for (int i = 0;i < m;i++) {
		lft[L[i]].push_back(i);	
		rht[R[i]].push_back(i);	
	}
	for (int i = 0;i < n;i++) sort(seg[i].begin(), seg[i].end());
	auto addedge = [&] (int u, int v, int w){
		adj[u].push_back({v, w});
		adj[v].push_back({u, w});
		debug(u, v, w);
	};
	{
		set<pii> se;
		for (int i = 0;i < n;i++) {
			for (int id:lft[i]) {
				se.insert({Y[id], id});
			}
			auto it = se.begin();
			while (it != se.end()) {
				if (it->ff > H[i]) break;	
				seg[i].push_back(*it);
				it = next(it);
			}
			for (int id:rht[i]) {
				se.erase(se.find(make_pair(Y[id], id)));
			}
		}
	}
	int term = maxv - 1;
	{
		int cur = 1;
		for (int i = 0;i < n;i++) {
			for (int j = 0;j < seg[i].size();j++) {
				int id = seg[i][j].ss;
				int y = Y[id], node = cur++;

				if (i == st && y <= H[i]) addedge(node, 0, y);
				if (i == ed && y <= H[i]) addedge(node, term, y);
				if (on[id]) {
					addedge(node, prv[id], X[i] - px[id]);
				} else {
					on[id] = 1;
				}
				if (j && y <= H[i]) addedge(node, node-1, y - seg[i][j-1].ff);
				prv[id] = node;
				px[id] = X[i];
			}
		}
	}
	for (int i = 0;i < maxv;i++) dis[i] = inf;	
	dis[0] = 0;	
	priority_queue<pii, vector<pii>, greater<pii> > pq;
	pq.push({0, 0});
	while (pq.size()) {
		auto [d, cur] = pq.top();
		pq.pop();
		if (d != dis[cur]) continue;
		for (auto [v, w]:adj[cur]) {
			if (d + w < dis[v]) {
				dis[v] = d + w;
				pq.push({dis[v], v});
			}
		}
	}
	if (dis[term] == inf) return -1;
	return dis[term];
}

Compilation message (stderr)

walk.cpp: In lambda function:
walk.cpp:13:20: warning: statement has no effect [-Wunused-value]
   13 | #define debug(...) 0
      |                    ^
walk.cpp:42:3: note: in expansion of macro 'debug'
   42 |   debug(u, v, w);
      |   ^~~~~
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:65:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |    for (int j = 0;j < seg[i].size();j++) {
      |                   ~~^~~~~~~~~~~~~~~

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