제출 #638458

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
638458		ggoh	철로 (IOI14_rail)	C++14	56 / 100	332 ms	98580 KiB

rail

#include "rail.h"
#include<bits/stdc++.h>
using namespace std;
#define sz(v) ((int)(v).size())
typedef long long lint;

int dis[5005][5005],minind[5005];

void findLocation(int n, int first, int location[], int stype[])
{
    location[0]=first;
    stype[0]=1;
    if(n==1)return ;

    for(int i=0;i<n;i++)
    {
        for(int j=i+1;j<n;j++)
        {
            dis[i][j]=getDistance(i,j);
            dis[j][i]=dis[i][j];
        }
    }
    for(int i=0;i<n;i++)
    {
        minind[i]=i;
        for(int j=0;j<n;j++)
        {
            if(i==j)continue;
            if(minind[i]==i || dis[i][minind[i]]>dis[i][j])minind[i]=j;
        }
    }
    int c0,d0;
    d0=minind[0];
    location[d0]=location[0]+dis[0][d0];
    stype[d0]=2;
    c0=minind[d0];
    location[c0]=location[d0]-dis[d0][c0];
    stype[c0]=1;
    for(int i=0;i<n;i++)
    {
        if(i==c0 || i==d0)continue;
        if(dis[c0][i] < dis[d0][i]) // right
        {
            if(minind[i]==c0 || dis[c0][minind[i]]>dis[c0][minind[minind[i]]]) // d type
            {
                location[i]=location[c0]+dis[c0][i];
                stype[i]=2;
            }
            else
            {
                location[i]=location[c0]+dis[c0][minind[i]]-dis[i][minind[i]];
                stype[i]=1;
            }
        }
        else //left
        {
            if(minind[i]==d0 || dis[d0][minind[i]]>dis[d0][minind[minind[i]]]) // c type
            {
                location[i]=location[d0]-dis[d0][i];
                stype[i]=1;
            }
            else
            {
                location[i]=location[d0]-dis[d0][minind[i]]+dis[i][minind[i]];
                stype[i]=2;
            }
        }
    }
    //for(int i=0;i<n;i++)printf("%d %d\n",location[i],stype[i]);
    return ;
}

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