Submission #289668

#	Time	Username	Problem	Language	Result	Execution time	Memory
289668		amiratou	Sky Walking (IOI19_walk)	C++14	24 / 100	1322 ms	236624 KiB

walk

#include "walk.h"
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define sz(x) (int)x.size()
#define pb push_back
typedef long long ll;
typedef pair<ll,ll> ii;
const int MX = (int)(1e5+5);
const ll INF = (ll)(1e18);

vector<ii> adj[MX],VEC[1200005];
ll dist[1200005];

ll min_distance(vector<int> x, vector<int> h, vector<int> l, vector<int> r, vector<int> y, int s, int g) {
	int n=sz(x);
	int idx=n;
	vector<pair<ii,int > >vec;
	for (int i = 0; i < n; ++i)
		vec.pb({{h[i],1},i});
	for (int i = 0; i < sz(l); ++i)
		vec.pb({{y[i],0},i});
	sort(vec.begin(),vec.end(),greater<pair<ii,int> > ());
	set<int> alive;
	for (int i = 0; i < sz(vec); ++i)
	{
		if(vec[i].fi.se)alive.insert(vec[i].se);
		else{
			auto it=alive.find(l[vec[i].se]);
			vector<ii> G;
			while(it!=alive.end() && (*it)<=r[vec[i].se]){
				adj[*it].pb({vec[i].fi.fi,idx});
				G.pb({idx,x[*it]}),idx++;
				it++;
			}
			for (int j = 0; j < sz(G)-1; ++j)
			{
				//cerr<<G[j].fi<<","<<G[j+1].fi<<" w : "<<G[j+1].se-G[j].se<<"\n";
				VEC[G[j].fi].pb({G[j+1].fi,G[j+1].se-G[j].se});
				VEC[G[j+1].fi].pb({G[j].fi,G[j+1].se-G[j].se});
			}

		}
	}
	for (int i = 0; i < n; ++i)
	{
		adj[i].pb({0,i});
		for (int j = sz(adj[i])-1; j >= 1; j--)
		{
			//cerr<<adj[i][j].se<<","<<adj[i][j-1].se<<" w : "<<adj[i][j-1].fi-adj[i][j].fi<<"\n";
			VEC[adj[i][j].se].pb({adj[i][j-1].se,adj[i][j-1].fi-adj[i][j].fi});
			VEC[adj[i][j-1].se].pb({adj[i][j].se,adj[i][j-1].fi-adj[i][j].fi});
		}
	}
	priority_queue<ii,vector<ii>,greater<ii> > pq;
	for (int i = 0; i < idx; ++i)
		dist[i]=INF;
	dist[s]=0;
	pq.push({0,s});
	while(!pq.empty()){
		ii f=pq.top();
		pq.pop();
		if(dist[f.se]!=f.fi)continue;
		for(auto it:VEC[f.se])
			if(dist[it.fi]>(f.fi+it.se)){
				dist[it.fi]=f.fi+it.se;
				pq.push({dist[it.fi],it.fi});
			}
	}
	if(dist[g]==INF)return -1;
	return dist[g];	
}

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