# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
813217 | Wael | 철로 (IOI14_rail) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
using namespace std;
#include "grader.h"
#define F first
#define S second
typedef int ll;
int const M = 5e3 + 20;
int Dis[M][M] , mn[M] , closer[M] , cur , n;
bool vis[M];
set<ll>TypeC , TypeD;
bool cmp(int a , int b) {
return (Dis[0][a] < Dis[0][b]);
}
void findLocation(int n , int first , int location[], int stype[]) {
int a = 0 , b , MinDis = 1e9;
location[a] = first;
stype[a] = 1;
TypeC.insert(location[a]);
for(int station = 1 ; station < n ; ++station) {
//Dis[a][station] = getDistance(a , station);
if(Dis[a][station] < MinDis) {
b = station;
MinDis = Dis[a][b];
}
}
location[b] = location[a] + Dis[a][b];
stype[b] = 2;
TypeD.insert(location[b]);
MinDis = 1e9;
for(int i = 0 ; i < n ; ++i) {
if(i == b) continue;
if(Dis[b][i] < MinDis) {
MinDis = Dis[b][i];
a = i;
}
}
location[a] = location[b] - Dis[a][b];
stype[a] = 1;
TypeC.insert(location[a]);
vector<ll>rem;
for(int station = 1 ; station < n ; ++station) {
if(station == b || station == a) continue;
rem.push_back(station);
}
sort(rem.begin() , rem.end() , cmp);
int LeftMost = a , RightMost = b;
for(auto station : rem) {
if(Dis[a][station] < Dis[b][station]) {
int CurDis = getDistance(RightMost , station);
int Expect = location[RightMost] - CurDis;
auto it = TypeD.lower_bound(Expect);
if(*it - location[a] + *it - Expect == Dis[a][station] && Expect > location[b]) {
location[station] = Expect;
stype[station] = 1;
TypeC.insert(location[station]);
} else {
RightMost = station;
location[RightMost] = location[a] + Dis[a][RightMost];
stype[RightMost] = 2;
TypeD.insert(location[RightMost]);
}
}
else {
int CurDis = getDistance(LeftMost , station);
int Expect = location[LeftMost] + CurDis;
auto it = TypeC.lower_bound(Expect); --it;
if(stype[station] == 2) assert(Dis[a][closer[station]] < Dis[a][station]);
if(location[b] - *it + Expect - *it == Dis[b][station] && Expect < location[a]) {
location[station] = Expect;
stype[station] = 2;
TypeD.insert(location[station]);
} else {
if(stype[station] != 1) return;
LeftMost = station;
location[LeftMost] = location[b] - Dis[b][LeftMost];
stype[LeftMost] = 1;
TypeC.insert(location[LeftMost]);
}
}
}
return;
}