Submission #133521

#	Time	Username	Problem	Language	Result	Execution time	Memory
133521		tinjyu	Crocodile's Underground City (IOI11_crocodile)	C++14	46 / 100	6 ms	1016 KiB

crocodile

#include "crocodile.h"
#include <iostream>
using namespace std;
long long int e=0,tag[1000005],head[1000005],ans[1000005][2],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];
    }
    while(e>0)
    {
        int x=head[1];
		swap(head[1],head[e]);
        e--;
        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)
                {
                    swap(head[pe],head[pe*2+1]);
                    pe=pe*2+1;
                }
                else
                {
                    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];
                if(tmp<ans[now][0])
                {
                    ans[now][1]=ans[now][0];
                    ans[now][0]=tmp;
                }
                else if(tmp<ans[now][1])
                {
                    ans[now][1]=tmp;
                }
                if(ans[now][1]!=999999999999999 && 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])
                        {
                            swap(head[pe],head[pe/2]);
                            pe/=2;
                        }
                        else break;
                    }
                }
            g=map[g][1];
        }
    }
    return ans[0][1];
}

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