Submission #290231

#	Time	Username	Problem	Language	Result	Execution time	Memory
290231		AaronNaidu	Rail (IOI14_rail)	C++14	30 / 100	408 ms	98616 KiB

rail

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

int distFrom0[5001];
int distFromMin[5001];
int queries[5001][5001];
int closest[5001];
bool doneWith[5001];
vector<int> goesTo[5001];

void findLocation(int n, int first, int location[], int sType[]) {
    location[0] = first;
    sType[0] = 1;
    doneWith[0] = true;
    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++)
    {
        int minDist = 1000000007;
        int minIndex = -1;
        for (int j = 0; j < n; j++)
        {
            if (j != i and queries[i][j] < minDist)
            {
                minDist = queries[i][j];
                closest[i] = j;
            }
        }
    }
    for (int i = 0; i < n; i++)
    {
        goesTo[closest[i]].push_back(i);
    }
    int numDone = n-1;
    queue<int> q;
    q.push(0);
    while (!q.empty())
    {
        int x = q.front();
        q.pop();
        if (!doneWith[closest[x]])
        {
            q.push(closest[x]);
            doneWith[closest[x]] = true;
            if (sType[x] == 1)
            {
                sType[closest[x]] = 2;
                location[closest[x]] = location[x] + queries[x][closest[x]];
            }
            else
            {
                sType[closest[x]] = 1;
                location[closest[x]] = location[x] - queries[x][closest[x]];
            }
        }
        for (auto i : goesTo[x])
        {
            if (!doneWith[i])
            {
                q.push(i);
                doneWith[i] = true;
                if (sType[x] == 1)
                {
                    sType[i] = 2;
                    location[i] = location[x] + queries[x][i];
                }
                else
                {
                    sType[i] = 1;
                    location[i] = location[x] - queries[x][i];
                }
            }
        }
    }
}

Compilation message (stderr)

rail.cpp: In function 'void findLocation(int, int, int*, int*)':
rail.cpp:27:13: warning: unused variable 'minIndex' [-Wunused-variable]
   27 |         int minIndex = -1;
      |             ^~~~~~~~
rail.cpp:41:9: warning: unused variable 'numDone' [-Wunused-variable]
   41 |     int numDone = n-1;
      |         ^~~~~~~

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