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 "rail.h"
#include <bits/stdc++.h>
using namespace std;
int dp[5000][5000];
int tot = 0;
int get(int a,int b){
if(a == b)
return 0;
if(dp[a][b] || dp[b][a])
return max(dp[a][b],dp[b][a]);
tot--;
assert(tot >= 0);
return dp[a][b] = getDistance(a,b);
}
void findLocation(int n, int first, int location[], int stype[]){
tot = n * (n-1)/2;
for(int i = 0;i<n;i++){
stype[i] = 0;
for(int j = 0;j<n;j++){
dp[i][j] = 0;
}
}
location[0] = first;
stype[0] = 1;
if(n == 1)return;
vector<int> ord0;
for(int i = 0;i<n;i++){
if(i != 0){
ord0.push_back(i);
}
}
sort(ord0.begin(),ord0.end(),[&](int a,int b){
return get(0,a) < get(0,b);
});
int posD = ord0[0];
location[posD] = location[0] + get(0,posD);
stype[posD] = 2;
vector<int> v;
v.push_back(0);
int tmp = -1;
for(int i = 1;i<ord0.size();i++){
if(get(0,ord0[i]) != get(posD,ord0[i]) + get(0,posD))continue;
if(get(posD,ord0[i]) < get(0,posD)){
tmp = ord0[i];
stype[ord0[i]] = 1;
location[ord0[i]] = location[posD] - get(posD,ord0[i]);
continue;
}
int candpos = location[v.back()] + get(v.back(),ord0[i]);
int closest = -1;
for(auto u:v){
if(location[u] < candpos){
if(closest == -1 || location[closest] < location[u]){
closest = u;
}
}
}
assert(closest != -1);
if(get(posD,ord0[i]) != get(posD,closest) + get(closest,ord0[i])){
v.push_back(ord0[i]);
stype[ord0[i]] = 1;
location[ord0[i]] = location[posD] - get(posD,ord0[i]);
}
else{
stype[ord0[i]] = 2;
location[ord0[i]] = candpos;
}
}
// for(int i = 0;i<n;i++){
// if(stype[i]){
// cout << i << endl;
// cout << stype[i] << ' ' << location[i] << endl;
// }
// }
vector<int> ordD;
for(int i = 0;i<n;i++){
if(i != posD){
ordD.push_back(i);
}
}
sort(ordD.begin(),ordD.end(),[&](int a,int b){
return get(posD,a) < get(posD,b);
});
v.clear();
v.push_back(posD);
if(tmp == -1)
tmp = 0;
for(int i = 1;i<ordD.size();i++){
if(ordD[i] == tmp)continue;
// cout << ordD[i] << endl;
// cout << get(tmp,ordD[i]) << endl;
// cout << get(posD,ordD[i]) << endl;
if(get(posD,ordD[i]) != get(tmp,ordD[i]) + get(tmp,posD))continue;
// cout << "HEY" << endl;
assert(stype[ordD[i]] == 0);
int candpos = location[v.back()] - get(v.back(),ordD[i]);
int closest = -1;
for(auto u:v){
if(location[u] > candpos){
if(closest == -1 || location[closest] > location[u]){
closest = u;
}
}
}
assert(closest != -1);
if(get(tmp,ordD[i]) != get(tmp,closest) + get(closest,ordD[i])){
v.push_back(ordD[i]);
stype[ordD[i]] = 2;
location[ordD[i]] = location[tmp] + get(tmp,ordD[i]);
}
else{
stype[ordD[i]] = 1;
location[ordD[i]] = candpos;
}
}
// for(int i = 0;i<n;i++){
// if(stype[i]){
// cout << i << endl;
// cout << stype[i] << ' ' << location[i] << endl;
// }
// }
}
Compilation message (stderr)
rail.cpp: In function 'void findLocation(int, int, int*, int*)':
rail.cpp:41:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
41 | for(int i = 1;i<ord0.size();i++){
| ~^~~~~~~~~~~~
rail.cpp:88:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
88 | for(int i = 1;i<ordD.size();i++){
| ~^~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |