# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
813549 |
2023-08-07T20:04:04 Z |
Wael |
Rail (IOI14_rail) |
C++14 |
|
51 ms |
860 KB |
#include<bits/stdc++.h>
using namespace std;
#include "rail.h"
#define F first
#define S second
typedef int ll;
int const M = 5e3 + 20;
int Dis[M][M] , a , b;
set<ll>TypeC , TypeD;
bool cmp(int x , int y) {
return (Dis[b][x] < Dis[b][y]);
}
void findLocation(int n , int first , int location[], int stype[]) {
int MinDis = 1e9;
location[a] = first;
stype[a] = 1;
TypeC.insert(location[a]);
for(int station = 1 ; station < n ; ++station) {
Dis[a][station] = getDistance(a , station);
if(Dis[a][station] < MinDis) {
b = station;
MinDis = Dis[a][b];
}
}
location[b] = location[a] + Dis[a][b];
stype[b] = 2;
TypeD.insert(location[b]);
vector<ll>rem;
for(int station = 1 ; station < n ; ++station) {
if(station == b) continue;
Dis[b][station] = getDistance(b , station);
rem.push_back(station);
}
sort(rem.begin() , rem.end() , cmp);
int LeftMost = a , RightMost = b;
for(int station : rem) {
if(Dis[a][station] != Dis[a][b] + Dis[b][station]) {
int CurDis = getDistance(RightMost , station);
int Expect = location[RightMost] - CurDis;
auto it = TypeD.lower_bound(Expect);
if(*it - location[a] + *it - Expect == Dis[a][station]) {
location[station] = Expect;
stype[station] = 1;
TypeC.insert(location[station]);
} else {
RightMost = station;
location[RightMost] = location[a] + Dis[a][RightMost];
stype[RightMost] = 2;
TypeD.insert(location[RightMost]);
}
}
else {
if(Dis[b][station] < Dis[a][b]) {
location[station] = location[b] - Dis[b][station];
stype[station] = 1;
TypeC.insert(location[station]);
continue;
}
int CurDis = getDistance(LeftMost , station);
int Expect = location[LeftMost] + CurDis;
auto it = TypeC.upper_bound(Expect); --it;
if(location[b] - *it + Expect - *it == Dis[b][station]) {
location[station] = Expect;
stype[station] = 2;
TypeD.insert(location[station]);
} else {
LeftMost = station;
location[LeftMost] = location[b] - Dis[b][LeftMost];
stype[LeftMost] = 1;
TypeC.insert(location[LeftMost]);
}
}
}
return;
}
/*
2
8
1 5
1 6
1 7
2 8
1 1
1 2
2 3
2 4
*/
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
0 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
0 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
384 KB |
Output is correct |
2 |
Correct |
0 ms |
384 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
380 KB |
Output is correct |
5 |
Correct |
1 ms |
384 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
384 KB |
Output is correct |
8 |
Correct |
1 ms |
384 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
1 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
46 ms |
756 KB |
Output is correct |
2 |
Correct |
46 ms |
860 KB |
Output is correct |
3 |
Correct |
46 ms |
760 KB |
Output is correct |
4 |
Correct |
51 ms |
776 KB |
Output is correct |
5 |
Correct |
46 ms |
760 KB |
Output is correct |
6 |
Correct |
46 ms |
768 KB |
Output is correct |
7 |
Correct |
46 ms |
764 KB |
Output is correct |
8 |
Correct |
49 ms |
780 KB |
Output is correct |
9 |
Correct |
45 ms |
776 KB |
Output is correct |
10 |
Correct |
46 ms |
776 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
45 ms |
716 KB |
Output is correct |
2 |
Correct |
46 ms |
764 KB |
Output is correct |
3 |
Correct |
45 ms |
776 KB |
Output is correct |
4 |
Correct |
46 ms |
764 KB |
Output is correct |
5 |
Correct |
45 ms |
772 KB |
Output is correct |
6 |
Correct |
48 ms |
760 KB |
Output is correct |
7 |
Correct |
46 ms |
780 KB |
Output is correct |
8 |
Correct |
46 ms |
776 KB |
Output is correct |
9 |
Correct |
46 ms |
760 KB |
Output is correct |
10 |
Correct |
45 ms |
760 KB |
Output is correct |
11 |
Correct |
45 ms |
760 KB |
Output is correct |
12 |
Correct |
47 ms |
772 KB |
Output is correct |
13 |
Correct |
45 ms |
776 KB |
Output is correct |
14 |
Correct |
49 ms |
776 KB |
Output is correct |
15 |
Correct |
44 ms |
760 KB |
Output is correct |
16 |
Correct |
46 ms |
772 KB |
Output is correct |
17 |
Correct |
45 ms |
764 KB |
Output is correct |
18 |
Correct |
45 ms |
768 KB |
Output is correct |
19 |
Correct |
46 ms |
764 KB |
Output is correct |
20 |
Correct |
49 ms |
780 KB |
Output is correct |