Submission #293279

#	Time	Username	Problem	Language	Result	Execution time	Memory
293279		AlanChen	Sky Walking (IOI19_walk)	C++14	0 / 100	59 ms	5608 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=100;
int n,m;

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[1000000];
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);


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

	int nv=2;
	lp(i,m) lp(j,l[i],r[i]+1) {
		nodes[j].pb(mp(y[i],nv));
		if(j>l[i]) addedge(nv,nv-1,x[j]-x[j-1]);
		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: 0 / 10
• Subtask 2: 0 / 14
• Subtask 3: 0 / 15
• Subtask 4: 0 / 18
• Subtask 5: 0 / 43