Submission #93538

#	Time	Username	Problem	Language	Result	Execution time	Memory
93538		Bodo171	Rail (IOI14_rail)	C++14	56 / 100	448 ms	760 KiB

rail

#include "rail.h"
#include <iostream>
const int nmax=5005;
int d[nmax],from[nmax];
bool viz[nmax];
int n,i,j,lst,val,mn,wh;
int get_oth(int c)
{
    return (c^(3));
}
void findLocation(int N, int first, int location[], int stype[])
{
    n=N;viz[0]=1;
    location[0]=first;stype[0]=1;
    lst=0;
    for(i=1;i<n;i++)
        d[i]=(1<<30);
    for(int steps=1;steps<n;steps++)
    {
        for(i=0;i<n;i++)
            if(!viz[i])
        {
            val=getDistance(lst,i);
            if(val<d[i])
            {
                d[i]=val;
                from[i]=lst;
            }
        }
        mn=(1<<30);
        for(i=0;i<n;i++)
            if((!viz[i])&&d[i]<mn)
               mn=d[i],wh=i;
        lst=wh;
        stype[lst]=get_oth(stype[from[lst]]);
        if(stype[from[lst]]==1) location[lst]=location[from[lst]]+mn;
        else location[lst]=location[from[lst]]-mn;
        viz[lst]=1;
    }
}

• Subtask 1: 8 / 8
• Subtask 2: 22 / 22
• Subtask 3: 26 / 26
• Subtask 4: 0 / 44