Submission #290363

#	Time	Username	Problem	Language	Result	Execution time	Memory
290363		AaronNaidu	Rail (IOI14_rail)	C++14	30 / 100	391 ms	98552 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];
int minDists[5001];
bool doneWith[5001];
vector<int> goesTo[5001];
queue<int> q;

void processQueue(int location[], int sType[]) {
    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];
                }
            }
        }
    }
}

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++)
    {
        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;
            }
        }
    }
    for (int i = 0; i < n; i++)
    {
        goesTo[closest[i]].push_back(i);
    }
    int numLeft = n-1;
    q.push(0);
    processQueue(location, sType);
    int otherIndex = closest[0];
    for (int i = 0; i < n; i++)
    {
        if (!doneWith[i])
        {
            if (queries[i][0] < queries[i][otherIndex])
            {
                if (queries[i][0] < queries[closest[i]][0])
                {
                    sType[i] = 2;
                    location[i] = location[0] + queries[i][0];
                }
                else
                {
                    sType[i] = 1;
                    location[i] = location[0] + queries[i][0] - 2*minDists[i];
                }
                
            }
            else
            {
                if (queries[i][otherIndex] < queries[closest[i]][otherIndex])
                {
                    sType[i] = 1;
                    location[i] = location[otherIndex] - queries[i][otherIndex];
                }
                else
                {
                    sType[i] = 2;
                    location[i] = location[otherIndex] - queries[i][otherIndex] + 2*minDists[i];
                }
            }
        }
    }
}

Compilation message (stderr)

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

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