Submission #257429

#	Time	Username	Problem	Language	Result	Execution time	Memory
257429		tinjyu	Sky Walking (IOI19_walk)	C++14	0 / 100	110 ms	84856 KiB

walk

    #include "walk.h"
    #include <iostream>
    #include <algorithm>
    #include <cmath>
    using namespace std;
    struct node{
    	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]=1000000000000;
    	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();
    	return dis[cnt];
    }

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