| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 49563 |
2018-05-31T10:01:35 Z |
khsoo01 |
Rail (IOI14_rail) |
C++11 |
|
131 ms |
32252 KB |
#include "rail.h"
#include<bits/stdc++.h>
using namespace std;
int d[5005][5005];
map<int,int> inv;
int getd (int I, int J) {
if(I == J) return 0;
if(I > J) swap(I, J);
if(!d[I][J]) d[I][J] = getDistance(I, J);
return d[I][J];
}
void solve (int L[], int S[], vector<int> &X, int P, int Q) {
sort(X.begin(), X.end(),
[&](int A, int B) {
return getd(P, A) < getd(P, B);
});
int D = 1 - 2 * (S[P] == 1);
for(auto &T : X) {
int V = (getd(Q, T) + getd(P, Q) - getd(P, T)) / 2;
int C = L[Q] + D * V;
if(inv[C] == S[Q]) {
L[T] = C + D * (getd(P, T) - abs(L[P] - C));
S[T] = S[P];
}
else {
L[T] = L[P] - D * getd(P, T);
S[T] = S[Q];
Q = T;
}
inv[L[T]] = S[T];
}
}
void findLocation(int N, int F, int L[], int S[])
{
L[0] = F;
S[0] = 1;
inv[L[0]] = 1;
if(N == 1) return;
int I = 1;
for(int i=2;i<N;i++) {
if(getd(0, I) > getd(0, i)) I = i;
}
L[I] = L[0] + getd(0, I);
S[I] = 2;
inv[L[I]] = 2;
vector<int> X, Y;
for(int i=1;i<N;i++) {
if(i == I) continue;
if(getd(I, i) + getd(I, 0) == getd(0, i)) {
if(getd(I, 0) > getd(I, i)) {
L[i] = L[0] + getd(I, 0) - getd(I, i);
S[i] = 1;
inv[L[i]] = 1;
}
else X.push_back(i);
}
else Y.push_back(i);
}
solve(L, S, X, I, 0);
solve(L, S, Y, 0, I);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
636 KB |
Output is correct |
| 2 |
Correct |
3 ms |
772 KB |
Output is correct |
| 3 |
Correct |
3 ms |
820 KB |
Output is correct |
| 4 |
Correct |
3 ms |
820 KB |
Output is correct |
| 5 |
Correct |
2 ms |
820 KB |
Output is correct |
| 6 |
Correct |
3 ms |
820 KB |
Output is correct |
| 7 |
Correct |
2 ms |
820 KB |
Output is correct |
| 8 |
Correct |
3 ms |
924 KB |
Output is correct |
| 9 |
Correct |
3 ms |
924 KB |
Output is correct |
| 10 |
Correct |
2 ms |
940 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
940 KB |
Output is correct |
| 2 |
Correct |
2 ms |
940 KB |
Output is correct |
| 3 |
Correct |
3 ms |
940 KB |
Output is correct |
| 4 |
Correct |
3 ms |
940 KB |
Output is correct |
| 5 |
Correct |
3 ms |
940 KB |
Output is correct |
| 6 |
Correct |
2 ms |
940 KB |
Output is correct |
| 7 |
Correct |
2 ms |
940 KB |
Output is correct |
| 8 |
Correct |
2 ms |
940 KB |
Output is correct |
| 9 |
Correct |
3 ms |
940 KB |
Output is correct |
| 10 |
Correct |
3 ms |
1020 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
113 ms |
20348 KB |
Output is correct |
| 2 |
Correct |
112 ms |
20348 KB |
Output is correct |
| 3 |
Correct |
124 ms |
22880 KB |
Output is correct |
| 4 |
Correct |
113 ms |
22880 KB |
Output is correct |
| 5 |
Correct |
120 ms |
22880 KB |
Output is correct |
| 6 |
Correct |
119 ms |
24572 KB |
Output is correct |
| 7 |
Correct |
124 ms |
28520 KB |
Output is correct |
| 8 |
Correct |
131 ms |
30844 KB |
Output is correct |
| 9 |
Correct |
111 ms |
30844 KB |
Output is correct |
| 10 |
Correct |
130 ms |
32252 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
119 ms |
32252 KB |
Output is correct |
| 2 |
Correct |
113 ms |
32252 KB |
Output is correct |
| 3 |
Correct |
112 ms |
32252 KB |
Output is correct |
| 4 |
Correct |
112 ms |
32252 KB |
Output is correct |
| 5 |
Correct |
110 ms |
32252 KB |
Output is correct |
| 6 |
Correct |
116 ms |
32252 KB |
Output is correct |
| 7 |
Correct |
115 ms |
32252 KB |
Output is correct |
| 8 |
Correct |
116 ms |
32252 KB |
Output is correct |
| 9 |
Correct |
113 ms |
32252 KB |
Output is correct |
| 10 |
Correct |
121 ms |
32252 KB |
Output is correct |
| 11 |
Correct |
124 ms |
32252 KB |
Output is correct |
| 12 |
Correct |
117 ms |
32252 KB |
Output is correct |
| 13 |
Correct |
130 ms |
32252 KB |
Output is correct |
| 14 |
Correct |
110 ms |
32252 KB |
Output is correct |
| 15 |
Correct |
122 ms |
32252 KB |
Output is correct |
| 16 |
Correct |
123 ms |
32252 KB |
Output is correct |
| 17 |
Correct |
113 ms |
32252 KB |
Output is correct |
| 18 |
Correct |
118 ms |
32252 KB |
Output is correct |
| 19 |
Correct |
116 ms |
32252 KB |
Output is correct |
| 20 |
Correct |
110 ms |
32252 KB |
Output is correct |
