| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 290230 | AaronNaidu | Rail (IOI14_rail) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
int distFrom0[5001];
int distFromMin[5001];
int queries[5001][5001];
int closest[5001];
bool doneWith[5001];
vector<int> goesTo[5001];
int getDistance(int i ,int j) {
cout << "Distance " << i << " " << j << "\n";
int x;
cin >> x;
return x;
}
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];
}
}
}
}
}