Submission #257435

#	Time	Username	Problem	Language	Result	Execution time	Memory
257435		tinjyu	Sky Walking (IOI19_walk)	C++14	10 / 100	139 ms	100728 KiB

walk

#include "walk.h"
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
struct node{
	long long int dis,id;
}t[1000005];
long long int p[1000005],hp[1000005],dis[1000005],m,n,road[1000005],map[1000005][3],pointer[100005][50][2],num[100005],cont,st,cnt;
int connect(int a,int b,int len)
{
	//cout<<a<<" "<<p[a]<<" "<<hp[a]<<" "<<b<<" "<<p[b]<<" "<<hp[b]<<endl;
	cont++;
	map[cont][0]=b;
	map[cont][1]=road[a];
	map[cont][2]=len;
	road[a]=cont;
	cont++;
	map[cont][0]=a;
	map[cont][1]=road[b];
	map[cont][2]=len;
	road[b]=cont;
	return 0;
}
struct cmp{
	bool operator()(const node &a,const node &b)
	{
		return a.dis>b.dis;
	}
};
int dijk()
{
	for(int i=1;i<=cnt;i++)dis[i]=100000000000000;
	dis[st]=0;
	t[1].id=st;
	t[1].dis=0;
	long long int pp=1;
	while(pp>=1)
	{
		pop_heap(t+1,t+pp+1,cmp());
		long long int x=t[pp].id,len=t[pp].dis;
		pp--;
		if(len!=dis[x])
		{
			continue;
		}
		//cout<<x<<" "<<len<<" "<<p[x]<<endl;
		long long int g=road[x];
		while(g!=-1){
			long long int now=map[g][0];
			//cout<<now<<" "<<dis[now]<<" "<<p[now]<<" "<<hp[now]<<endl;
			if(len+map[g][2]<dis[now]){
				dis[now]=len+map[g][2];
				pp++;
				t[pp].id=now;
				t[pp].dis=dis[now];
				push_heap(t+1,t+pp+1,cmp());
			}
			g=map[g][1];
		}
		for(int i=1;i<=num[p[x]];i++)
		{
			long long int now=pointer[p[x]][i][0];
			if(now==x)continue;
			//cout<<now<<" "<<dis[now]<<" "<<p[now]<<" "<<hp[now]<<endl;
			if(len+abs(hp[x]-pointer[p[x]][i][1])<dis[now]){
				dis[now]=len+abs(hp[x]-pointer[p[x]][i][1]);
				pp++;
				t[pp].id=now;
				t[pp].dis=dis[now];
				push_heap(t+1,t+pp+1,cmp());
			}
			g=map[g][1];
		}
		//cout<<endl;

	}
	return 0;
}
long long min_distance(std::vector<int> x, std::vector<int> h, std::vector<int> l, std::vector<int> r, std::vector<int> y, int s, int g) {
	n=x.size();
	m=l.size();
	for(int i=0;i<=n*m;i++)road[i]=-1;
	st=0;
	for(int i=0;i<m;i++){
		cnt++;
		num[l[i]]++;
		p[cnt]=l[i];
		hp[cnt]=y[i];
		pointer[l[i]][num[l[i]]][0]=cnt;
		pointer[l[i]][num[l[i]]][1]=y[i];
		long long int pr=cnt,prex=x[l[i]];
		for(int j=l[i]+1;j<=r[i];j++){
			if(h[j]>=y[i])
			{
				cnt++;
				num[j]++;
				p[cnt]=j;
				hp[cnt]=y[i];
				pointer[j][num[j]][0]=cnt;
				pointer[j][num[j]][1]=y[i];
				connect(cnt,pr,x[j]-prex);
				pr=cnt;
				prex=x[j];
			}
		}
	}
	num[s]++;
	cnt++;
	p[cnt]=s;
	pointer[s][num[s]][0]=cnt;
	st=cnt;

	num[g]++;
	cnt++;
	p[cnt]=g;
	pointer[g][num[g]][0]=cnt;
	dijk();
	if(dis[cnt]>1000000000000)return -1;
	return dis[cnt];
}

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