oj.uz

Submission #257889

# Submission time Handle Problem Language Result Execution time Memory
257889 2020-08-05T01:36:01 Z tinjyu Sky Walking (IOI19_walk) C++14
24 / 100
 1105 ms 932388 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];
long long 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();
	//cout<<m<<endl;
	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((long long int)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 0 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 512 KB Output is correct
4 Correct 1 ms 512 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 0 ms 512 KB Output is correct
12 Correct 1 ms 512 KB Output is correct
13 Correct 1 ms 512 KB Output is correct
14 Correct 1 ms 512 KB Output is correct
15 Correct 0 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
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 387 ms 179588 KB Output is correct
4 Correct 402 ms 180728 KB Output is correct
5 Correct 227 ms 166264 KB Output is correct
6 Correct 226 ms 157176 KB Output is correct
7 Correct 257 ms 168184 KB Output is correct
8 Correct 477 ms 207864 KB Output is correct
9 Correct 257 ms 168184 KB Output is correct
10 Correct 468 ms 225248 KB Output is correct
11 Correct 236 ms 131576 KB Output is correct
12 Correct 185 ms 112504 KB Output is correct
13 Correct 429 ms 206504 KB Output is correct
14 Correct 171 ms 110844 KB Output is correct
15 Correct 165 ms 111736 KB Output is correct
16 Correct 159 ms 113144 KB Output is correct
17 Correct 178 ms 111984 KB Output is correct
18 Correct 159 ms 118008 KB Output is correct
19 Correct 45 ms 80248 KB Output is correct
20 Correct 92 ms 94712 KB Output is correct
21 Correct 153 ms 110824 KB Output is correct
22 Correct 173 ms 111784 KB Output is correct
23 Correct 179 ms 119544 KB Output is correct
24 Correct 157 ms 112120 KB Output is correct
25 Correct 157 ms 111992 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 94840 KB Output is correct
2 Runtime error 1105 ms 932388 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 90 ms 94840 KB Output is correct
2 Runtime error 1105 ms 932388 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 0 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 512 KB Output is correct
4 Correct 1 ms 512 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 0 ms 512 KB Output is correct
12 Correct 1 ms 512 KB Output is correct
13 Correct 1 ms 512 KB Output is correct
14 Correct 1 ms 512 KB Output is correct
15 Correct 0 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 1 ms 384 KB Output is correct
20 Correct 387 ms 179588 KB Output is correct
21 Correct 402 ms 180728 KB Output is correct
22 Correct 227 ms 166264 KB Output is correct
23 Correct 226 ms 157176 KB Output is correct
24 Correct 257 ms 168184 KB Output is correct
25 Correct 477 ms 207864 KB Output is correct
26 Correct 257 ms 168184 KB Output is correct
27 Correct 468 ms 225248 KB Output is correct
28 Correct 236 ms 131576 KB Output is correct
29 Correct 185 ms 112504 KB Output is correct
30 Correct 429 ms 206504 KB Output is correct
31 Correct 171 ms 110844 KB Output is correct
32 Correct 165 ms 111736 KB Output is correct
33 Correct 159 ms 113144 KB Output is correct
34 Correct 178 ms 111984 KB Output is correct
35 Correct 159 ms 118008 KB Output is correct
36 Correct 45 ms 80248 KB Output is correct
37 Correct 92 ms 94712 KB Output is correct
38 Correct 153 ms 110824 KB Output is correct
39 Correct 173 ms 111784 KB Output is correct
40 Correct 179 ms 119544 KB Output is correct
41 Correct 157 ms 112120 KB Output is correct
42 Correct 157 ms 111992 KB Output is correct
43 Correct 90 ms 94840 KB Output is correct
44 Runtime error 1105 ms 932388 KB Execution killed with signal 11 (could be triggered by violating memory limits)
45 Halted 0 ms 0 KB -