Submission #133604

#	Time	Username	Problem	Language	Result	Execution time	Memory
133604		tinjyu	Crocodile's Underground City (IOI11_crocodile)	C++14	100 / 100	736 ms	72184 KiB

crocodile

#include "crocodile.h"
#include <iostream>
using namespace std;
long long int headnow[1000005],e=0,tag[1000005],head[1000005],ans[1000005][4],n,m,map[2000005][3],road[1000005];
int travel_plan(int N, int M, int r[][2], int l[], int k, int p[])
{
    n=N;
    m=M;
    for(int i=0;i<n;i++)road[i]=-1;
    for(int i=0;i<m;i++)
    {
        int x=r[i][0],y=r[i][1];
        map[i*2][0]=y;
        map[i*2][1]=road[x];
        map[i*2][2]=l[i];
        road[x]=i*2;
        map[i*2+1][0]=x;
        map[i*2+1][1]=road[y];
        map[i*2+1][2]=l[i];
        road[y]=i*2+1;
    }
    for(int i=0;i<n;i++)
    {
        ans[i][0]=999999999999999;
        ans[i][1]=999999999999999;
    }
    e=k;
    for(int i=0;i<k;i++)
    {
        ans[p[i]][0]=0;
        ans[p[i]][1]=0;
        tag[p[i]]=1;
        head[i+1]=p[i];
        headnow[p[i]]=i;
    }
    while(e>0)
    {
    	
        int x=head[1];
		swap(head[1],head[e]);
        e--;
        headnow[head[e]]=1;
        int pe=1;
        while(pe*2<=e)
        {
            if(ans[head[pe]][1]>ans[head[pe*2]][1] || ans[head[pe]][1]>ans[head[pe*2+1]][1])
            {
                if(ans[head[pe*2+1]][1]<ans[head[pe*2]][1] && pe*2+1<=e)
                {
                	
                	headnow[head[pe]]=pe*2+1;
                	headnow[head[pe*2+1]]=pe;
                    swap(head[pe],head[pe*2+1]);
                    pe=pe*2+1;
                }
                else
                {
                	headnow[head[pe]]=pe*2;
                	headnow[head[pe*2]]=pe;
                    swap(head[pe],head[pe*2]);
                    pe=pe*2;
                }
            }
            else break;
        }
        int g=road[x];
        while(g!=-1)
        {
            	int now=map[g][0];
                long long int tmp=ans[x][1]+map[g][2];
                long long int t=ans[now][1];
                if(tmp<ans[now][0])
                {
                	if(x==ans[now][2])ans[now][0]=tmp;
                	else
                	{
                		ans[now][1]=ans[now][0];
                		ans[now][0]=tmp;
                		ans[now][3]=ans[now][2];
                		ans[now][2]=x;
					}
				}
				else if(tmp<ans[now][1])
				{
					ans[now][1]=tmp;
					ans[now][3]=x;
				}
                if(ans[now][1]<t && tag[now]==0)
                {
                    tag[now]=1;
                    e++;
                    head[e]=now;
                    int pe=e;
                    while(pe>1)
                    {
                        if(ans[head[pe]][1]<ans[head[pe/2]][1])
                        {
                        	headnow[head[pe]]=pe/2;
                        	headnow[head[pe/2]]=pe;
                            swap(head[pe],head[pe/2]);
                            pe/=2;
                        }
                        else break;
                    }
                }
                else if(ans[now][1]<t)
                {
                	int pe=headnow[now];
                    while(pe>1)
                    {
                        if(ans[head[pe]][1]<ans[head[pe/2]][1])
                        {
                        	headnow[head[pe]]=pe/2;
                        	headnow[head[pe/2]]=pe;
                            swap(head[pe],head[pe/2]);
                            pe/=2;
                        }
                        else break;
                    }
				}
            g=map[g][1];
        }
        tag[x]=0;
    }
    return ans[0][1];
}

• Subtask 1: 46 / 46
• Subtask 2: 43 / 43
• Subtask 3: 11 / 11