| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 805655 | prvocislo | Rail (IOI14_rail) | C++17 | 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.
#pragma once
#include <algorithm>
#include <deque>
#include <iostream>
#include <map>
#include <string>
#include <vector>
#include "grader.h"
typedef long long ll;
using namespace std;
const int C = 1, D = 2, inf = 1e9 + 5;
map<pair<int, int>, int> m;
int getd(int i, int j)
{
if (i == j) return inf; // takto je to proste najlepsie idk preco
if (m.count({ i, j })) return m[{i, j}];
return m[{i, j}] = m[{j, i}] = getDistance(i, j);
}
void findLocation(int n, int p0, int ansl[], int anstyp[])
{
int pc = 0;
ansl[pc] = p0, anstyp[pc] = C;
vector<int> dc(n, 0);
for (int i = 0; i < n; i++) dc[i] = getd(0, i);
int pd = min_element(dc.begin(), dc.end()) - dc.begin(); // najdeme najblizsie D k tomu C
ansl[pd] = p0 + dc[pd], anstyp[pd] = D;
vector<int> dd(n, 0);
for (int i = 0; i < n; i++) dd[i] = getd(pd, i);
int distc = *min_element(dd.begin(), dd.end()); // vzdialenost tohto Dcka k najblizsiemu Ccku
vector<pair<int, int> > left; // tie ktore su nalavo od toho Ccka + ich vzdialenosti od Dcka
vector<pair<int, int> > right; // tie ktore su napravo od toho Dcka + ich vzdialenosti od toho Ccka
for (int i = 0; i < n; i++) if (i != pc && i != pd)
{
if (dd[i] < dd[pc] && dc[i] == dd[pc] + dd[i]) // je to nejake Ccko medzi tymi dvoma
{
ansl[i] = ansl[pd] - dd[i], anstyp[i] = C;
}
else if (dc[i] + dd[pc] - (dd[pc] - distc) * 2 == dd[i]) // je to napravo od toho Dcka
{
right.push_back({ dc[i], i });
}
else if (dd[i] + dc[pd] == dc[i])
{
left.push_back({ dd[i], i });
}
}
// ideme vyriesit tie nalavo
sort(left.begin(), left.end());
vector<int> ci;
for (int i = 0; i < left.size(); i++)
{
bool isc = false;
int x = left[i].second;
int cx = ansl[pd] - left[i].first, dx;
if (!i) isc = true;
else
{
int d2 = getd(ci.back(), x);
dx = ansl[ci.back()] + d2;
if (d2 + dd[ci.back()] > dd[x]) isc = true;
else isc = false;
}
if (isc) ansl[x] = cx, anstyp[x] = C, ci.push_back(x);
else ansl[x] = dx, anstyp[x] = D;
}
// ideme vyriesit tie napravo
sort(right.begin(), right.end());
vector<int> di;
for (int i = 0; i < right.size(); i++)
{
bool isd = false;
int x = right[i].second;
int dx = ansl[pc] + right[i].first, cx;
if (!i) isd = true;
else
{
int d2 = getd(di.back(), x);
cx = ansl[di.back()] - d2;
if (d2 + dc[di.back()] > dc[x]) isd = true;
else isd = false;
}
if (isd) ansl[x] = dx, anstyp[x] = D, di.push_back(x);
else ansl[x] = cx, anstyp[x] = C;
}
}