# |
제출 시각 |
아이디 |
문제 |
언어 |
결과 |
실행 시간 |
메모리 |
842615 |
2023-09-03T06:20:47 Z |
WLZ |
철로 (IOI14_rail) |
C++17 |
|
92 ms |
102688 KB |
#include <bits/stdc++.h>
#include "rail.h"
const int C = 1;
const int D = 2;
const int M = 1e6 + 5;
using namespace std;
void findLocation(int n, int first, int location[], int stype[]) {
for (int i = 0; i < n; i++) {
stype[i] = 0;
}
vector<int> rev(M, -1);
location[0] = first;
stype[0] = C;
rev[first] = 0;
vector<vector<int>> dist(n, vector<int>(n, 0));
vector<int> order(n - 1);
for (int i = 1; i < n; i++) {
dist[i][0] = dist[0][i] = getDistance(0, i);
order[i - 1] = i;
}
sort(order.begin(), order.end(), [&](const int& a, const int& b) {
return dist[0][a] < dist[0][b];
});
int c = order[0];
location[c] = first + dist[0][c];
stype[c] = D;
rev[location[c]] = c;
int j = c;
for (int i = 1; i < n - 1; i++) {
int z = order[i];
dist[c][z] = dist[z][c] = getDistance(c, z);
if (dist[0][c] + dist[c][z] != dist[0][z]) {
dist[j][z] = dist[z][j] = getDistance(j, z);
int k = (dist[0][j] + dist[j][z] - dist[0][z]) >> 1;
int extra = location[j] - k;
extra = rev[extra];
if (extra != -1 && stype[extra] == D) {
location[z] = location[j] - dist[j][z];
stype[z] = C;
} else {
location[z] = location[0] + dist[0][z];
stype[z] = D;
j = z;
}
rev[location[z]] = z;
}
}
int i = 0;
order.clear();
for (int i = 0; i < n; i++) {
if (i != c) {
order.emplace_back(i);
}
}
sort(order.begin(), order.end(), [&](const int& a, const int& b) {
return dist[c][a] < dist[c][b];
});
i = 0;
for (j = 0; j < n - 1; j++) {
int z = order[j];
if (dist[0][z] == dist[0][c] + dist[c][z] && dist[0][c] < dist[c][z]) {
dist[i][z] = dist[z][i] = getDistance(i, z);
int k = (dist[c][i] + dist[i][z] - dist[c][z]) >> 1;
int extra = location[i] + k;
extra = rev[extra];
if (stype[extra] == C) {
location[z] = location[i] + dist[i][z];
stype[z] = D;
} else {
location[z] = location[c] - dist[c][z];
stype[z] = C;
i = z;
}
rev[location[z]] = z;
}
}
for (i = 1; i < n - 1; i++) {
if (stype[i] == 0) {
stype[i] = C;
location[i] = location[c] - dist[c][i];
}
}
return;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
4444 KB |
Output is correct |
2 |
Correct |
1 ms |
4696 KB |
Output is correct |
3 |
Correct |
1 ms |
4364 KB |
Output is correct |
4 |
Correct |
1 ms |
4696 KB |
Output is correct |
5 |
Correct |
1 ms |
4444 KB |
Output is correct |
6 |
Correct |
1 ms |
4444 KB |
Output is correct |
7 |
Correct |
2 ms |
4444 KB |
Output is correct |
8 |
Correct |
2 ms |
4444 KB |
Output is correct |
9 |
Correct |
2 ms |
4444 KB |
Output is correct |
10 |
Correct |
1 ms |
4444 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
4444 KB |
Output is correct |
2 |
Correct |
1 ms |
4444 KB |
Output is correct |
3 |
Correct |
1 ms |
4360 KB |
Output is correct |
4 |
Correct |
1 ms |
4444 KB |
Output is correct |
5 |
Correct |
1 ms |
4444 KB |
Output is correct |
6 |
Correct |
1 ms |
4444 KB |
Output is correct |
7 |
Correct |
1 ms |
4444 KB |
Output is correct |
8 |
Correct |
1 ms |
4444 KB |
Output is correct |
9 |
Correct |
1 ms |
4444 KB |
Output is correct |
10 |
Correct |
2 ms |
4444 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
81 ms |
102624 KB |
Output is correct |
2 |
Correct |
79 ms |
102536 KB |
Output is correct |
3 |
Correct |
79 ms |
102488 KB |
Output is correct |
4 |
Correct |
80 ms |
102540 KB |
Output is correct |
5 |
Correct |
79 ms |
102536 KB |
Output is correct |
6 |
Correct |
86 ms |
102492 KB |
Output is correct |
7 |
Correct |
80 ms |
102476 KB |
Output is correct |
8 |
Correct |
80 ms |
102524 KB |
Output is correct |
9 |
Correct |
80 ms |
102484 KB |
Output is correct |
10 |
Correct |
80 ms |
102476 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
85 ms |
102524 KB |
Output is correct |
2 |
Correct |
82 ms |
102448 KB |
Output is correct |
3 |
Correct |
81 ms |
102540 KB |
Output is correct |
4 |
Correct |
80 ms |
102492 KB |
Output is correct |
5 |
Correct |
83 ms |
102688 KB |
Output is correct |
6 |
Correct |
82 ms |
102524 KB |
Output is correct |
7 |
Correct |
80 ms |
102532 KB |
Output is correct |
8 |
Correct |
80 ms |
102400 KB |
Output is correct |
9 |
Correct |
81 ms |
102532 KB |
Output is correct |
10 |
Correct |
92 ms |
102540 KB |
Output is correct |
11 |
Correct |
80 ms |
102484 KB |
Output is correct |
12 |
Correct |
80 ms |
102536 KB |
Output is correct |
13 |
Correct |
84 ms |
102476 KB |
Output is correct |
14 |
Correct |
90 ms |
102516 KB |
Output is correct |
15 |
Correct |
81 ms |
102524 KB |
Output is correct |
16 |
Correct |
82 ms |
102484 KB |
Output is correct |
17 |
Correct |
80 ms |
102444 KB |
Output is correct |
18 |
Correct |
80 ms |
102512 KB |
Output is correct |
19 |
Correct |
85 ms |
102608 KB |
Output is correct |
20 |
Correct |
84 ms |
102428 KB |
Output is correct |