Submission #139165

#	Time	Username	Problem	Language	Result	Execution time	Memory
139165		ibrahim001	Rail (IOI14_rail)	C++14	30 / 100	600 ms	98576 KiB

rail

#include "rail.h"
#include <bits/stdc++.h>
#define intt long long
#define pb push_back
#define F first
#define S second
#define endl '\n'
#define pb push_back
#define pii pair<int,int>
using namespace std;
const int inf = 1e9;
int i,j;
int dis[5005][5005];
bool l[5005];
bool used[5005];
void findLocation(int N, int first, int location[], int stype[])
{
    location[0]=first;
    stype[0]=1;
    if ( N == 1 )
        return;
    int n=N;
    for ( i = 0; i < n; i++ )
    {
        for ( j = i+1; j < n; j++ )
        {
            dis[i][j] = dis[j][i] = getDistance(i,j);
        }
    }
    int best,minn=inf;
    for ( i = 1; i < n; i++ )
    {
        if ( dis[0][i] < minn )
        {
            minn = dis[i][0];
            best=i;
        }
    }
    location[best] = location[0]+minn;
    stype[best] = 2;
    for ( i = 1; i < n; i++ )
    {
        if ( i == best )
            continue;
        if ( dis[i][best] < dis[i][0] )
        {
            if ( dis[i][best] < dis[best][0] )
            {
                location[i] = location[best]-dis[best][0];
                stype[i] = 1;
                continue;
            }
            l[i] = true;
        }
    }
    vector<pii>v;
    for ( i = 1; i < n; i++ )
    {
        if ( !l[i] || used[i] || i == best )
            continue;
        v.pb({dis[best][i],i});
    }
    if ( !v.empty() )
    {
        sort(v.begin(),v.end());
        int last = v[0].S;
        location[last]=location[best]-dis[best][last];
        stype[last]=1;
        bool flag=false;
        for ( pii i : v )
        {
            if ( !flag )
            {
                flag= true;
                continue;
            }
            if ( dis[best][i.S] == dis[best][last]+dis[last][i.S] )
            {
                stype[i.S] = 2;
                location[i.S]=location[last]+dis[last][i.S];
            }
            else
            {
                last = i.S;
                location[i.S] = location[best]-dis[best][i.S];
                stype[i.S]=1;
            }
        }

    }
    v.clear();
    for ( i = 1; i < n; i++ )
    {
        if ( !l[i] && i != best && !used[i] )
        {
            v.pb({dis[i][0],i});
        }
    }
    if ( !v.empty() )
    {
        sort(v.begin(),v.end());
        int last = v[0].S;
        location[last]=location[0]+dis[last][0];
        stype[last] = 2;
        bool flag = false;
        for ( pii i : v )
        {
            if ( !flag )
            {
                flag = true;
                continue;
            }
            if ( dis[i.S][0] == dis[i.S][last]+dis[last][i.S] )
            {
                location[i.S] = location[last]-dis[last][i.S];
                stype[i.S]=1;
            }
            else
            {
                last = i.S;
                location[i.S] = location[0]+dis[i.S][0];
                stype[i.S] = 2;
            }
        }
    }
}

Compilation message (stderr)

rail.cpp: In function 'void findLocation(int, int, int*, int*)':
rail.cpp:39:18: warning: 'best' may be used uninitialized in this function [-Wmaybe-uninitialized]
     location[best] = location[0]+minn;
                  ^

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