Submission #1238500

#	Time	Username	Problem	Language	Result	Execution time	Memory
1238500		dosts	Sky Walking (IOI19_walk)	C++20	0 / 100	4056 ms	697592 KiB

walk

#include "walk.h"
#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")
#define int long long
#define pii pair<int,int>
#define vi vector<int>
#define ff first
#define ss second
#define sp << " " <<
#define all(x) x.begin(),x.end()
#define big(x) ((int)(x.size()))
using namespace std;
const int MOD = 1e9+7, LIM = 5e6+1, inf = 2e18;

map<pii,int> id;
int gg = 0;
int node(int x,int y) {
	if (id.count({x,y})) return id[{x,y}];
	return id[{x,y}] = ++gg;
}
vector<pii> edges[LIM];
vi dist(LIM);
int min_distance(std::vector<signed> x, std::vector<signed> h, std::vector<signed> l, std::vector<signed> r, std::vector<signed> y, signed s, signed g) {
	int n = big(x);
	for (int i = 0;i<n;i++) node(x[i],0),node(x[i],h[i]);
	int m = big(l);
	for (int i = 0;i<m;i++) {
		int px = x[l[i]];
		for (int j = l[i]+1;j<=r[i];j++) {
			if (y[i] > h[j]) continue;
			int a = node(px,y[i]);
			int b = node(x[j],y[i]);
			edges[a].push_back({b,x[j]-px});
			edges[b].push_back({a,x[j]-px});
			px = x[j];
		} 
	}
	for (int i = 0;i<n;i++) {
		auto it = id.lower_bound({x[i],0});
		while (it != id.end() && next(it) != id.end() && next(it)->ff.ff == it->ff.ff) {
			edges[node(it->ff.ff,it->ff.ss)].push_back({node(it->ff.ff,next(it)->ff.ss),next(it)->ff.ss-it->ff.ss});
			edges[node(it->ff.ff,next(it)->ff.ss)].push_back({node(it->ff.ff,it->ff.ss),next(it)->ff.ss-it->ff.ss});
			it = next(it);
		}
	}
	priority_queue<pii,vector<pii>,greater<pii>> pq;
	pq.push({0,node(x[s],0)});
	dist.assign(gg+1,inf);
	dist[node(x[s],0)] = 0;
	while (!pq.empty()) {
		auto [cost,city] = pq.top();
		pq.pop();
		if (dist[city] != cost) continue;
		for (auto it : edges[city]) {
			if (dist[it.ff] > cost+it.ss) {
				dist[it.ff] = cost+it.ss;
				pq.push({cost+it.ss,it.ff});
			}
		}
	}
	return dist[node(x[g],0)];
}

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