oj.uz

Submission #257888

# Submission time Handle Problem Language Result Execution time Memory
257888 2020-08-05T01:32:34 Z tinjyu Sky Walking (IOI19_walk) C++14
10 / 100
 4000 ms 624196 KB 
#include "walk.h"
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
struct node{
	long long int dis,id;
}t[10000005];
struct Node{
	long long int id,h;
}tmp[3000005],temp[1000005];
int l[1000005],r[1000005],y[1000005],p[10000005],hp[10000005],m,n,road[10000005],map[30000005][3],cntp,pointer[100005],data[30000005][3],num[100005],cont,st,cnt,le[1000005],ri[1000005];
long long int dis[1000005];
int connect(int a,int b,long long int len)
{
	//cout<<a<<" "<<b<<" "<<len<<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];
		}
		//cout<<endl;
	}
	return 0;
}
bool cmp2(Node a,Node b)
{
	return a.h<b.h;
}
int qs(int s,int e)
{
	if(s>=e)return 0;
	long long int pp=s,qq=e,mid=y[(s+e)/2];
	while(pp<=qq)
	{
		while(y[pp]<mid)pp++;
		while(y[qq]>mid)qq--;
		if(pp<=qq)
		{
			swap(l[pp],l[qq]);
			swap(r[pp],r[qq]);
			swap(y[pp],y[qq]);
			pp++;
			qq--;
		}
	}
	qs(s,qq);
	qs(pp,e);
	return 0;
}
long long min_distance(std::vector<int> x, std::vector<int> h, std::vector<int> lef, std::vector<int> rig, std::vector<int> tmpy, int s, int g) {
	n=x.size();
	m=lef.size();

	for(int i=0;i<m;i++)
	{
		l[i]=lef[i];
		r[i]=rig[i];
		y[i]=tmpy[i];
	}
	qs(0,m-1);
	for(int i=0;i<n;i++)
	{
		temp[i].id=i;
		temp[i].h=h[i];
	}
	for(int i=0;i<=min(10000000,n*m);i++)road[i]=-1;
	for(int i=0;i<n;i++)pointer[i]=-1;
	
	sort(temp,temp+n,cmp2);
	st=0;
	long long int xp=0;
	le[0]=-1;
	for(int i=1;i<n;i++)
	{
		le[i]=i-1;
	}
	ri[n-1]=n;
	for(int i=0;i<n-1;i++)
	{
		ri[i]=i+1;
	}
	for(int i=0;i<m;i++){
		while(y[i]>temp[xp].h)
		{
		//cout<<xp<<endl;
			if(le[temp[xp].id]!=-1)ri[le[temp[xp].id]]=ri[temp[xp].id];
			if(ri[temp[xp].id]!=-1)le[ri[temp[xp].id]]=le[temp[xp].id];
			xp++;
		}
		//cout<<i<<" "<<xp<<" "<<y[i]<<" "<<l[i]<<" "<<r[i]<<endl;
		cnt++;
		num[l[i]]++;
		p[cnt]=l[i];
		hp[cnt]=y[i];
		cntp++;
		data[cntp][0]=cnt;
		data[cntp][1]=y[i];
		data[cntp][2]=pointer[l[i]];
		pointer[l[i]]=cntp;
		long long int pr=cnt,prex=x[l[i]];
		for(int j=ri[l[i]];j<=r[i] && j!=-1 ;j=ri[j]){
			//cout<<j<<" ";
			cnt++;
			cntp++;
			data[cntp][0]=cnt;
			data[cntp][1]=y[i];
			data[cntp][2]=pointer[j];
			pointer[j]=cntp;
			connect(cnt,pr,x[j]-prex);
			pr=cnt;
			prex=x[j];
		}
		//cout<<i<<" "<<m<<endl;
	}
	

	cnt++;
	st=cnt;
	cntp++;
	data[cntp][0]=cnt;
	data[cntp][1]=0;
	data[cntp][2]=pointer[s];
	pointer[s]=cntp;
	
	cnt++;
	cntp++;
	data[cntp][0]=cnt;
	data[cntp][1]=0;
	data[cntp][2]=pointer[g];
	pointer[g]=cntp;
	for(int i=0;i<n;i++)
	{
		long long int g=pointer[i],tmpcount=0;
		while(g!=-1)
		{
			tmpcount++;
			tmp[tmpcount].id=data[g][0];
			tmp[tmpcount].h=data[g][1];
			g=data[g][2];
		}
		sort(tmp+1,tmp+tmpcount+1,cmp2);
		//for(int j=1;j<=tmpcount;j++)cout<<tmp[j].id<<" "<<tmp[j].h<<"  ";
		//cout<<endl;
		for(int j=1;j<tmpcount;j++)
		{
			connect(tmp[j].id,tmp[j+1].id,tmp[j+1].h-tmp[j].h);

		}
		//cout<<endl;
	}
	dijk();
	if(dis[cnt]==100000000000000)return -1;
	return dis[cnt];
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 512 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 1 ms 512 KB Output is correct
6 Correct 1 ms 512 KB Output is correct
7 Correct 1 ms 512 KB Output is correct
8 Correct 1 ms 512 KB Output is correct
9 Correct 1 ms 512 KB Output is correct
10 Correct 1 ms 512 KB Output is correct
11 Correct 1 ms 512 KB Output is correct
12 Correct 1 ms 512 KB Output is correct
13 Correct 0 ms 512 KB Output is correct
14 Correct 1 ms 512 KB Output is correct
15 Correct 1 ms 384 KB Output is correct
16 Correct 1 ms 512 KB Output is correct
17 Correct 1 ms 512 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 315 ms 95224 KB Output is correct
4 Correct 310 ms 99268 KB Output is correct
5 Execution timed out 4046 ms 54024 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 49272 KB Output is correct
2 Runtime error 1057 ms 624196 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 49272 KB Output is correct
2 Runtime error 1057 ms 624196 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 512 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 1 ms 512 KB Output is correct
6 Correct 1 ms 512 KB Output is correct
7 Correct 1 ms 512 KB Output is correct
8 Correct 1 ms 512 KB Output is correct
9 Correct 1 ms 512 KB Output is correct
10 Correct 1 ms 512 KB Output is correct
11 Correct 1 ms 512 KB Output is correct
12 Correct 1 ms 512 KB Output is correct
13 Correct 0 ms 512 KB Output is correct
14 Correct 1 ms 512 KB Output is correct
15 Correct 1 ms 384 KB Output is correct
16 Correct 1 ms 512 KB Output is correct
17 Correct 1 ms 512 KB Output is correct
18 Correct 1 ms 384 KB Output is correct
19 Correct 0 ms 384 KB Output is correct
20 Correct 315 ms 95224 KB Output is correct
21 Correct 310 ms 99268 KB Output is correct
22 Execution timed out 4046 ms 54024 KB Time limit exceeded
23 Halted 0 ms 0 KB -