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>
#include "rail.h"
using namespace std;
const int MAXN = 5010;
typedef pair<int,int> pii;
int n;
int dist[MAXN][MAXN];
vector< pii > sweep;
int getDist(int A, int B)
{
if( dist[A][B] == -1 )
dist[A][B] = dist[B][A] = getDistance( A , B );
return dist[A][B];
}
void findLocation(int N, int first, int location[], int stype[])
{
int L = 0;
memset( dist , -1 , sizeof(dist) );
stype[L] = 1;
location[L] = first;
for(int i = 1 ; i < N ; i++)
sweep.push_back( { getDist( 0 , i ) , i } );
sort( sweep.begin() , sweep.end() );
int R = sweep[0].second;
stype[R] = 2;
location[R] = first + getDist( L , R );
for(int i = 1 ; i < sweep.size() ; i++)
{
int cur = sweep[i].second;
int distL = getDist( L , cur );
int distR = getDist( R , cur );
if( distL == distR + getDist( L , R ) )
{
stype[cur] = 1;
location[cur] = location[R] - distR;
if( location[cur] < location[L] ) L = cur;
}
else
{
stype[cur] = 2;
location[cur] = location[L] + distL;
if( location[R] < location[cur] ) cur = R;
}
}
}
Compilation message (stderr)
rail.cpp: In function 'void findLocation(int, int, int*, int*)':
rail.cpp:42:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 1 ; i < sweep.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... |