제출 #1304151

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1304151		activedeltorre	철로 (IOI14_rail)	C++20	30 / 100	405 ms	98636 KiB

rail

#include "rail.h"
#include <iostream>
#include <vector>
using namespace std;
int d0[5005];
int d1[5005];
int per[5005];
int dist[5005][5005];
void findLocation(int N, int first, int location[], int stype[])
{
    int n=N;
    int minim=-1,st=0,dr=-1,j,z;
    for(int i=0; i<n; i++)
    {
        for(int j=1; j<n; j++)
        {
            dist[i][j]=getDistance(i,j);
            dist[j][i]=dist[i][j];
        }
    }
    for(int i=0;i<n;i++)
    {
        per[i]=-1;
        for(int j=0;j<n;j++)
        {
            if((j!=i) && (per[i]==-1 || dist[i][j]<dist[i][per[i]]))
            {
                per[i]=j;
            }
        }
    }
    vector<int>vec;
    for(int i=1; i<n; i++)
    {
        d0[i]=dist[0][i];
        if(dr==-1 || d0[i]<d0[dr])
        {
            dr=i;
        }
        vec.push_back(i);
    }
    location[0]=first;
    stype[0]=1;
    vec.erase(vec.begin()+dr-1);
    location[dr]=d0[dr]+first;
    stype[dr]=2;
    st=0;
    for(int i=1; i<n; i++)
    {
        minim=-1;
        for(z=0; z<vec.size(); z++)
        {
            j=vec[z];
            if(dist[st][j]+dist[dr][j]==2*dist[j][per[j]]+dist[st][dr])
            {
                if(dist[st][j]<dist[st][per[j]] || per[j]==st)
                {
                    location[j]=location[st]+dist[st][j];
                    stype[j]=2;
                }
                else
                {
                    location[j]=location[dr]-dist[dr][j];
                    stype[j]=1;
                }
                vec.erase(vec.begin()+z);
                z=-1;
            }
            else
            {
                if(minim==-1 || min(dist[st][j],dist[dr][j])<min(dist[st][minim],dist[dr][minim]))
                {
                    minim=j;
                }
            }
        }
        if(minim==-1)
        {
            break;
        }
        if(dist[dr][minim]==dist[minim][per[dr]]+dist[dr][per[dr]])
        {
            location[minim]=location[st]+dist[st][minim];
            stype[minim]=2;
            dr=minim;
            for(int z=0; z<vec.size(); z++)
            {
                if(vec[z]==minim)
                {
                    vec.erase(vec.begin()+z);
                }
            }
        }
        else
        {
            location[minim]=location[dr]-dist[dr][minim];
            stype[minim]=1;
            st=minim;
            for(int z=0; z<vec.size(); z++)
            {
                if(vec[z]==minim)
                {
                    vec.erase(vec.begin()+z);
                }
            }
        }
    }
}

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