Submission #1016840

#	Time	Username	Problem	Language	Result	Execution time	Memory
1016840		simona1230	Rail (IOI14_rail)	C++17	56 / 100	247 ms	98640 KiB

rail

#include<bits/stdc++.h>
#include "rail.h"
using namespace std;

int l[5001],t[5001];
int d[5001][5001];
int n;
vector<pair<int,int> > v;
int val[5001],clos[5001];
void findLocation(int N, int first, int location[], int stype[])
{
    n=N;
    for(int i=0;i<n;i++)
        val[i]=1e9;

    for(int i=0; i<N; i++)
    {
        for(int j=i+1; j<N; j++)
        {
            d[i][j]=d[j][i]=getDistance(i,j);
        }
    }

    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            if(i==j)continue;

            if(d[i][j]<val[i])
            {
                val[i]=d[i][j];
                clos[i]=j;
            }
        }
    }
    //    cout<<vr[i]<<" "<<minn[i]<<endl;


    l[0]=first;
    t[0]=1;

    int minn=1e9,vr1=0;
    for(int i=1; i<n; i++)
    {
        if(d[i][0]<minn)
        {
            minn=d[i][0];
            vr1=i;
        }
    }

    int vr2=0;
    minn=1e9;
    for(int i=0; i<n; i++)
    {
        if(vr1!=i&&d[vr1][i]<minn)
        {
            minn=d[vr1][i];
            vr2=i;
        }
    }
    swap(vr1,vr2);

    l[vr2]=l[0]+d[0][vr2];
    l[vr1]=l[vr2]-d[vr1][vr2];
    t[vr1]=1;
    t[vr2]=2;
    v.push_back({vr1,vr2});

    for(int i=0; i<n; i++)
    {
        for(int j=i+1; j<n; j++)
        {
            if(clos[i]!=j||clos[j]!=i||i==vr1||j==vr1)continue;

            if(d[vr1][i]<d[vr2][i])
            {
                //cout<<"right"<<endl;
                if(d[vr1][i]<d[vr1][j])
                {
                    t[j]=1;
                    t[i]=2;
                    l[i]=l[vr1]+d[vr1][i];
                    l[j]=l[i]-d[i][j];
                    v.push_back({j,i});
                }
                else
                {
                    t[i]=1;
                    t[j]=2;
                    l[j]=l[vr1]+d[vr1][j];
                    l[i]=l[j]-d[i][j];
                    v.push_back({i,j});
                }
            }
            else
            {
                //cout<<"left"<<endl;
                if(d[vr2][i]>d[vr2][j])
                {
                    t[j]=1;
                    t[i]=2;
                    l[j]=l[vr2]-d[vr2][j];
                    l[i]=l[j]+d[i][j];
                    v.push_back({j,i});
                }
                else
                {
                    t[i]=1;
                    t[j]=2;
                    l[i]=l[vr2]-d[vr2][i];
                    l[j]=l[i]+d[i][j];
                    v.push_back({i,j});
                }
            }
        }
    }

    for(int i=0;i<n;i++)
    {
        if(t[i])continue;
        int nb=clos[i];
        if(t[nb]==1)
        {
            t[i]=2;
            l[i]=l[nb]+d[i][nb];
        }
        else
        {
            t[i]=1;
            l[i]=l[nb]-d[i][nb];
        }
    }

    for(int i=0; i<n; i++)
    {
        location[i]=l[i],stype[i]=t[i];
        //cout<<t[i]<<" "<<l[i]<<endl;
    }
}

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