Submission #335064

#	Time	Username	Problem	Language	Result	Execution time	Memory
335064		daniel920712	Rail (IOI14_rail)	C++14	8 / 100	3085 ms	197256 KiB

rail

#include "rail.h"
#include <stdio.h>
#include <stdlib.h>
#include <queue>
#include <utility>
using namespace std;
priority_queue < pair < pair < int , int > , int > , vector < pair < pair < int , int > , int > > , greater < pair < pair < int , int > , int > > > all;
int dis[5005][5005]={0};
bool have[5005];
void findLocation(int N, int first, int location[], int stype[])
{
    int x,y,z,i,j;
    location[0]=first;
    stype[0]=1;
    all.push(make_pair(make_pair(0,0),-1));
    for(i=0;i<N;i++) for(j=0;j<N;j++) dis[i][j]=getDistance(i,j);

    while(!all.empty())
    {
        x=all.top().first.first;
        y=all.top().first.second;
        z=all.top().second;
        all.pop();
        if(have[x]) continue;
        have[x]=1;
        if(z!=-1)
        {
            if(stype[z]==1)
            {
                stype[x]=2;
                location[x]=location[z]+dis[z][x];
            }
            else
            {
                stype[x]=1;
                location[x]=location[z]-dis[z][x];
            }
        }
        for(i=0;i<N;i++) all.push(make_pair(make_pair(i,y+dis[x][i]),x));

    }

}

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