#include "rail.h"
#include <bits/stdc++.h>
using namespace std;
int N, minx = 10000000, minid, A[100009], T[100009], dp[5009][5009];
vector<pair<int, int>> vec1, vec2;
int getDist(int u, int v) {
if (u == v) return 0;
if (u > v) swap(u, v);
if (dp[u][v] >= 1) return dp[u][v];
int E = getDistance(u, v);
dp[u][v] = E;
return E;
}
void solve_1() {
int pos = 0; vector<int> E; E.push_back(0);
for (int i = 0; i < vec1.size(); i++) {
if (vec1[i].first < minx) {
T[vec1[i].second] = 1;
A[vec1[i].second] = A[minid] - vec1[i].first;
}
else {
int Z1 = getDist(minid, vec1[i].second);
int Z2 = getDist(minid, pos);
int Z3 = getDist(pos, vec1[i].second);
int Z = A[pos] + Z3;
for (int j = 0; j < E.size(); j++) {
if (abs(A[minid] - A[E[j]]) + abs(A[E[j]] - Z) == Z1) {
A[vec1[i].second] = Z;
T[vec1[i].second] = 2;
break;
}
}
if (T[vec1[i].second] == 0) {
A[vec1[i].second] = A[minid] - Z1;
T[vec1[i].second] = 1;
pos = vec1[i].second;
E.push_back(vec1[i].second);
}
}
}
}
void solve_2() {
int pos = minid; vector<int> E; E.push_back(minid);
for (int i = 0; i < vec2.size(); i++) {
int Z1 = getDist(0, vec2[i].second);
int Z2 = getDist(0, pos);
int Z3 = getDist(pos, vec2[i].second);
int Z = A[pos] - Z3;
for (int j = 0; j < E.size(); j++) {
if (abs(A[0] - A[E[j]]) + abs(A[E[j]] - Z) == Z1) {
A[vec2[i].second] = Z;
T[vec2[i].second] = 1;
break;
}
}
if (T[vec2[i].second] == 0) {
A[vec2[i].second] = A[0] + Z1;
T[vec2[i].second] = 2;
pos = vec2[i].second;
E.push_back(vec2[i].second);
}
}
}
void findLocation(int n, int first, int location[], int stype[]) {
N = n; A[0] = first; T[0] = 1;
for (int i = 1; i < N; i++) {
int E = getDist(0, i);
if (minx > E) { minx = E; minid = i; }
}
A[minid] = A[0] + minx; T[minid] = 2;
int minv = 10000000; for (int i = 0; i < N; i++) { if (i == minid) continue; minv = min(minv, getDist(minid, i)); }
for (int i = 0; i < N; i++) {
if (i == 0 || i == minid) continue;
int V1 = getDist(0, i) - (minx - minv);
int V2 = getDist(minid, i);
if (V1 > V2) vec1.push_back(make_pair(V2, i));
else vec2.push_back(make_pair(V1 + (minx - minv), i));
}
sort(vec1.begin(), vec1.end());
sort(vec2.begin(), vec2.end());
//cout << endl;
//cout << "Base value:" << endl;
//cout << minx << " " << minid << endl;
//cout << endl;
//cout << "Value of vec1:" << endl;
//for (int i = 0; i < vec1.size(); i++) cout << "(" << vec1[i].first << ", " << vec1[i].second << ")" << endl;
//cout << endl;
//cout << "Value of vec2:" << endl;
//for (int i = 0; i < vec2.size(); i++) cout << "(" << vec2[i].first << ", " << vec2[i].second << ")" << endl;
//cout << endl;
solve_1();
solve_2();
for (int i = 0; i < N; i++) {
//cout << "(" << A[i] << ", " << T[i] << ")" << endl;
location[i] = A[i]; stype[i] = T[i];
}
}
Compilation message
rail.cpp: In function 'void solve_1()':
rail.cpp:20:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < vec1.size(); i++) {
~~^~~~~~~~~~~~~
rail.cpp:31:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int j = 0; j < E.size(); j++) {
~~^~~~~~~~~~
rail.cpp:27:8: warning: unused variable 'Z2' [-Wunused-variable]
int Z2 = getDist(minid, pos);
^~
rail.cpp: In function 'void solve_2()':
rail.cpp:50:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < vec2.size(); i++) {
~~^~~~~~~~~~~~~
rail.cpp:56:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int j = 0; j < E.size(); j++) {
~~^~~~~~~~~~
rail.cpp:52:7: warning: unused variable 'Z2' [-Wunused-variable]
int Z2 = getDist(0, pos);
^~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
640 KB |
Output is correct |
2 |
Correct |
2 ms |
640 KB |
Output is correct |
3 |
Correct |
2 ms |
640 KB |
Output is correct |
4 |
Correct |
2 ms |
640 KB |
Output is correct |
5 |
Correct |
2 ms |
640 KB |
Output is correct |
6 |
Correct |
3 ms |
640 KB |
Output is correct |
7 |
Correct |
2 ms |
640 KB |
Output is correct |
8 |
Correct |
2 ms |
640 KB |
Output is correct |
9 |
Correct |
2 ms |
640 KB |
Output is correct |
10 |
Correct |
2 ms |
768 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
640 KB |
Output is correct |
2 |
Correct |
2 ms |
640 KB |
Output is correct |
3 |
Correct |
3 ms |
640 KB |
Output is correct |
4 |
Correct |
2 ms |
640 KB |
Output is correct |
5 |
Correct |
2 ms |
640 KB |
Output is correct |
6 |
Correct |
2 ms |
640 KB |
Output is correct |
7 |
Correct |
2 ms |
640 KB |
Output is correct |
8 |
Correct |
2 ms |
640 KB |
Output is correct |
9 |
Correct |
2 ms |
640 KB |
Output is correct |
10 |
Correct |
3 ms |
768 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
108 ms |
19924 KB |
Output is correct |
2 |
Correct |
96 ms |
18808 KB |
Output is correct |
3 |
Correct |
96 ms |
22484 KB |
Output is correct |
4 |
Correct |
102 ms |
20856 KB |
Output is correct |
5 |
Correct |
102 ms |
22100 KB |
Output is correct |
6 |
Correct |
113 ms |
24312 KB |
Output is correct |
7 |
Correct |
112 ms |
28352 KB |
Output is correct |
8 |
Correct |
114 ms |
30364 KB |
Output is correct |
9 |
Correct |
155 ms |
19584 KB |
Output is correct |
10 |
Correct |
111 ms |
32116 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
100 ms |
19960 KB |
Output is correct |
2 |
Correct |
95 ms |
18768 KB |
Output is correct |
3 |
Correct |
101 ms |
22520 KB |
Output is correct |
4 |
Correct |
95 ms |
20856 KB |
Output is correct |
5 |
Correct |
105 ms |
22264 KB |
Output is correct |
6 |
Correct |
112 ms |
24440 KB |
Output is correct |
7 |
Correct |
118 ms |
28424 KB |
Output is correct |
8 |
Correct |
107 ms |
30328 KB |
Output is correct |
9 |
Correct |
100 ms |
19576 KB |
Output is correct |
10 |
Correct |
112 ms |
31992 KB |
Output is correct |
11 |
Correct |
107 ms |
29572 KB |
Output is correct |
12 |
Correct |
98 ms |
20236 KB |
Output is correct |
13 |
Correct |
104 ms |
26792 KB |
Output is correct |
14 |
Correct |
101 ms |
23164 KB |
Output is correct |
15 |
Correct |
105 ms |
26204 KB |
Output is correct |
16 |
Correct |
103 ms |
24100 KB |
Output is correct |
17 |
Correct |
103 ms |
23436 KB |
Output is correct |
18 |
Correct |
105 ms |
28072 KB |
Output is correct |
19 |
Correct |
109 ms |
27336 KB |
Output is correct |
20 |
Correct |
99 ms |
18692 KB |
Output is correct |