Submission #290391

#	Time	Username	Problem	Language	Result	Execution time	Memory
290391		AaronNaidu	Rail (IOI14_rail)	C++14	30 / 100	423 ms	117880 KiB

rail

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

int distFrom0[6001];
int distFromMin[6001];
int queries[6001][6001];
int closest[6001];
int minDists[6001];
bool doneWith[6001];


void findLocation(int n, int first, int location[], int sType[]) {
    location[0] = first;
    sType[0] = 1;
    doneWith[0] = true;
    if (n == 1)
    {
        return;
    }
    for (int i = 0; i < n; i++)
    {
        for (int j = i+1; j < n; j++)
        {
            queries[i][j] = getDistance(i,j);
            queries[j][i] = queries[i][j];
        }
    }
    for (int i = 0; i < n; i++)
    {
        minDists[i] = 1000000007;
        for (int j = 0; j < n; j++)
        {
            if (j != i and queries[i][j] < minDists[i])
            {
                minDists[i] = queries[i][j];
                closest[i] = j;
            }
        }
    }
    int otherIndex = closest[0];
    sType[otherIndex] = 2;
    location[otherIndex] = first + queries[0][otherIndex]; 
    doneWith[otherIndex] = true;
    for (int i = 0; i < n; i++)
    {
        if (!doneWith[i])
        {
            if (queries[i][0] < queries[i][otherIndex])
            {
                if (closest[i] == 0 or queries[i][0] < queries[closest[i]][0])
                {
                    sType[i] = 2;
                    location[i] = location[0] + queries[i][0];
                    //cout << "Used1\n";
                }
                else
                {
                    sType[i] = 1;
                    location[i] = location[0] + queries[i][0] - 2*minDists[i];
                    //cout << "Used2\n";
                }
                
            }
            else
            {
                if (closest[i] == otherIndex or queries[i][otherIndex] < queries[closest[i]][otherIndex])
                {
                    sType[i] = 1;
                    location[i] = location[otherIndex] - queries[i][otherIndex];
                    //cout << "Used3\n";
                }
                else
                {
                    sType[i] = 2;
                    location[i] = location[otherIndex] - queries[i][otherIndex] + 2*minDists[i];
                    //cout << "Used4\n";
                }
            }
        }
    }
}

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