Submission #812874

#	Time	Username	Problem	Language	Result	Execution time	Memory
812874		fatemetmhr	Sky Walking (IOI19_walk)	C++17	0 / 100	630 ms	218924 KiB

walk

#include "walk.h"
#include <bits/stdc++.h>

using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());


typedef long long ll;

#define mp     make_pair
#define all(x) x.begin(), x.end()
#define pb     push_back
#define fi     first
#define se     second

const int maxn5 = 2e6 + 10;

ll dis[maxn5];
set <pair<ll, int>> have;
map <int, int> av, last;
vector <pair<int, ll>> adj[maxn5];
pair <int, int> ver[maxn5], per[maxn5];
vector <int> req[maxn5];

long long min_distance(vector<int> x, vector<int> h, vector<int> l, vector<int> r, vector<int> y, int s, int g){
	int n = x.size();
	int m = l.size();
	int ind = 0, pt = 0;
	for(int i = 0; i < m; i++){
		per[i] = {l[i], i};
	}
	sort(per, per + m);
	int ss, tt;
	for(int i = 0; i < n; i++){
		if(i == s)
			ss = pt;
		if(i == g)
			tt = pt;
		int id = pt;
		ver[pt++] = {x[i], 0};
		for(auto u : req[i]) if(av.find(y[u]) != av.end() && last[y[u]] == u)
			av.erase(av.find(y[u]));
		while(ind < m && per[ind].fi == i){
			req[r[per[ind].se] + 1].pb(per[ind].se);
			//cout << "pt " << pt << ' ' << r[per[ind].se] << endl;
			if(av.find(y[per[ind].se]) != av.end()){
				adj[pt].pb({av[y[per[ind].se]], 0});
				adj[av[y[per[ind].se]]].pb({pt, 0});
				//cout << "here we ssaw " << av[y[per[ind].se]] << ' ' << y[per[ind].se] << ' ' << i << ' ' << pt << endl;
			}
			last[y[per[ind].se]] = per[ind].se;
			av[y[per[ind].se]] = pt;
			ver[pt] = {x[i], y[per[ind].se]};

			pt++;
			ind++;
		}
		//cout << "hmmm " << i << ' ' << id << endl;
		for(auto it = av.begin(); it != av.end() && (it ->fi) <= h[i]; it++){
			ll len = (it ->fi) - ver[id].se;
			int v = av[it -> fi];
			adj[pt].pb({v, x[i] - ver[v].fi});
			adj[v].pb({pt, x[i] - ver[v].fi});
			av[it -> fi] = pt;
			adj[id].pb({pt, len});
			adj[pt].pb({id, len});
			id = pt;
			ver[pt++] = {x[i], it ->fi};
		}
	}

	memset(dis, -1, sizeof dis);
	dis[ss] = 0;
	have.insert({0, ss});
	/*
	cout << "with " << ss << ' ' << tt << endl;
	for(int i = 0; i < pt; i++){
		cout << "*** " << i << ' ' << ver[i].fi << ' ' << ver[i].se << endl;
		for(auto [u, len] : adj[i])
			cout << u << ' ' << len << endl;
	}
	*/
	while(have.size()){
		int v = have.begin() -> se;

		//cout << "ok " << v << ' ' << ver[v].fi << ' ' << ver[v].se << endl;
		have.erase(have.begin());
		for(auto [u, len] : adj[v]) if(dis[v] + len < dis[u] || dis[u] == -1){
			have.erase({dis[u], u});
			//cout << "here " << v << ' ' << u << ' ' << len << endl;
			dis[u] = dis[v] + len;
			have.insert({dis[u], u});
		}
	}
	return dis[tt];
}

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:96:15: warning: 'tt' may be used uninitialized in this function [-Wmaybe-uninitialized]
   96 |  return dis[tt];
      |               ^

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