Submission #293314

#	Time	Username	Problem	Language	Result	Execution time	Memory
293314		AlanChen	Sky Walking (IOI19_walk)	C++14	10 / 100	4133 ms	916872 KiB

walk

#include <bits/stdc++.h>
using namespace std;

template<class A> using v=vector<A>;
template<class A,class B=A> using p=pair<A,B>;
template<class A,class B=less<A>> using pq=priority_queue<A,v<A>,B>;
template<class A> using pqmin=pq<A,greater<A>>;

typedef long long ll;
typedef v<int> vi;
typedef p<int> pi;
typedef string str;

#define f first
#define s second
#define mp make_pair
#define ins insert
#define pb push_back
#define sz(S) (int)S.size()
#define all(S) (S).begin(),(S).end()

#define get4(a,b,c,d,...) d

#define lp3(x,a,b) for(int x=(a);x<(b);x++)
#define lp2(x,a) lp3(x,0,a)
#define lp1(a) lp2(loopvar,a)
#define lp(x...) get4(x,lp3,lp2,lp1,0)(x)

#define trv(x,S) for(auto& x:(S))




#include "walk.h"


const int mx=3000000;
int n,m;
p<ll,pi> brgs[mx];
p<ll,int> blds[mx];


v<p<ll,int>> nodes[mx];//dist,name
v<p<ll,int>> adj[mx];//dist,name
void addedge(int a,int b,ll d) {adj[a].pb(mp(d,b)),adj[b].pb(mp(d,a));}


ll dist[10000000];
pqmin<p<ll,int>> toadd;




long long min_distance(vi x, vi h, vi l, vi r, vi y, int stp, int edp)
{
	n=sz(x);
	m=sz(l);



	lp(i,m) brgs[i]={y[i],{l[i],r[i]}};
	sort(brgs,brgs+m,greater<p<ll,pi>>());

	lp(i,n) blds[i]={h[i],i};
	sort(blds,blds+n,greater<pi>());
	map<int,ll> rc;


	nodes[stp].pb(mp(0,0));
	nodes[edp].pb(mp(0,1));

	int nv=2;
	int pidx=0;
	lp(i,m)
	{
		while(pidx<n&&blds[pidx].f>=y[i]) rc[blds[pidx].s]=blds[pidx].f,pidx++;
		auto it=rc.find(l[i]);
		for(;it->f!=r[i];it++)
		{
			nodes[it->f].pb(mp(y[i],nv));
			auto it2=it;it2++;
			addedge(nv,nv+1,x[it2->f]-x[it->f]);
			nv++;
		}
		nodes[it->f].pb(mp(y[i],nv));
		nv++;
	}
	lp(i,n)
	{
		sort(all(nodes[i]));
		lp(j,1,sz(nodes[i])) if(nodes[i][j].f<=h[i]) addedge(nodes[i][j-1].s,nodes[i][j].s,nodes[i][j].f-nodes[i][j-1].f);
	}


	lp(i,nv) dist[i]=-1;
	toadd.push(mp(0,0));
	while(!toadd.empty())
	{
		auto top=toadd.top();
		toadd.pop();
		if(top.s==1) return top.f;
		if(dist[top.s]==-1)
		{
			dist[top.s]=top.f;
			trv(x,adj[top.s]) if(dist[x.s]==-1) toadd.push(mp(x.f+top.f,x.s));
		}
	}

	return -1;
}

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