# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
295343 |
2020-09-09T15:43:04 Z |
arayi |
Rail (IOI14_rail) |
C++17 |
|
205 ms |
41080 KB |
#include <bits/stdc++.h>
#include "rail.h"
#define MP make_pair
#define ad push_back
#define sc second
#define fr first
using namespace std;
const int m = 1e6 + 10;
int n, fr, sm, sc;
int a[5010][5010];
pair<int, int> b[m];
bool col[5010];
int getmn(int aa)
{
int mn = INT_MAX, ret = aa;
for (int i = 0; i < n; i++)
{
if(aa == i) continue;
if(a[aa][i] < mn) mn = a[aa][i], ret = i;
}
return ret;
}
vector <pair<int, int> > fp;
void findLocation(int N, int first, int location[], int stype[])
{
n = N;
fr = first;
for (int i = 1; i < n; i++)
a[0][i] = a[i][0] = getDistance(0, i);
stype[0] = 1, location[0] = fr;
if(n == 1) return;
sm = getmn(0), sc = a[0][sm] + fr;
stype[sm] = 2, location[sm] = sc;
for (int i = 1; i < n; i++)
if(i != sm) a[i][sm] = a[sm][i] = getDistance(i, sm);
for (int i = 1; i < n; i++)
{
if(i == sm) continue;
if(a[0][sm] + a[sm][i] == a[0][i])
{
if(a[sm][i] < a[0][sm]) stype[i] = 1, location[i] = sc - a[i][sm], col[i] = true;
else fp.ad(MP(a[sm][i], i));
}
}
sort(fp.begin(), fp.end());
col[0] = col[sm] = 1;
int ss = 0;
for(auto p : fp)
{
int d = getDistance(ss, p.sc);
int mx = ss;
for (int i = 0; i < n; i++){
if(col[i] && location[i] < d + location[ss] && stype[i] == 1)
{
if(location[mx] < location[i]) mx = i;
}}
if(d - location[mx] + location[ss] + a[mx][sm] == a[sm][p.sc])
{
stype[p.sc] = 2;
location[p.sc] = d + location[ss];
col[p.sc] = 1;
}
else
{
stype[p.sc] = 1;
location[p.sc] = sc - a[sm][p.sc];
col[p.sc] = 1;
ss = p.sc;
}
}
fp.clear();
for (int i = 1; i < n; i++)
{
if(i == sm) continue;
if(a[0][sm] + a[sm][i] != a[0][i])
{
fp.ad(MP(a[sm][i], i));
}
}
sort(fp.begin(), fp.end());
ss = sm;
for(auto p : fp)
{
int d = getDistance(ss, p.sc);
int mx = ss;
for (int i = 0; i < n; i++)
{
if(col[i] && location[i] > location[ss] - d && stype[i] == 2)
{
if(location[mx] > location[i]) mx = i;
}
}
if(d - location[ss] + location[mx] + a[0][mx] == a[0][p.sc])
{
stype[p.sc] = 1;
location[p.sc] = location[ss] - d;
col[p.sc] = 1;
}
else
{
stype[p.sc] = 2;
location[p.sc] = location[0] + a[0][p.sc];
col[p.sc] = 1;
ss = p.sc;
}
}
return;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
768 KB |
Output is correct |
2 |
Correct |
1 ms |
768 KB |
Output is correct |
3 |
Correct |
1 ms |
768 KB |
Output is correct |
4 |
Correct |
1 ms |
768 KB |
Output is correct |
5 |
Correct |
1 ms |
768 KB |
Output is correct |
6 |
Correct |
1 ms |
768 KB |
Output is correct |
7 |
Correct |
1 ms |
768 KB |
Output is correct |
8 |
Correct |
1 ms |
768 KB |
Output is correct |
9 |
Correct |
1 ms |
768 KB |
Output is correct |
10 |
Correct |
1 ms |
768 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
768 KB |
Output is correct |
2 |
Correct |
1 ms |
768 KB |
Output is correct |
3 |
Correct |
1 ms |
768 KB |
Output is correct |
4 |
Correct |
1 ms |
768 KB |
Output is correct |
5 |
Correct |
1 ms |
768 KB |
Output is correct |
6 |
Correct |
1 ms |
768 KB |
Output is correct |
7 |
Correct |
1 ms |
768 KB |
Output is correct |
8 |
Correct |
1 ms |
768 KB |
Output is correct |
9 |
Correct |
1 ms |
768 KB |
Output is correct |
10 |
Correct |
1 ms |
768 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
176 ms |
34680 KB |
Output is correct |
2 |
Correct |
173 ms |
26872 KB |
Output is correct |
3 |
Correct |
185 ms |
40824 KB |
Output is correct |
4 |
Correct |
187 ms |
40828 KB |
Output is correct |
5 |
Correct |
188 ms |
40972 KB |
Output is correct |
6 |
Correct |
187 ms |
40824 KB |
Output is correct |
7 |
Correct |
205 ms |
40844 KB |
Output is correct |
8 |
Correct |
177 ms |
31480 KB |
Output is correct |
9 |
Correct |
180 ms |
32428 KB |
Output is correct |
10 |
Correct |
180 ms |
26488 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
175 ms |
34552 KB |
Output is correct |
2 |
Correct |
171 ms |
26744 KB |
Output is correct |
3 |
Correct |
178 ms |
40840 KB |
Output is correct |
4 |
Correct |
182 ms |
40824 KB |
Output is correct |
5 |
Correct |
185 ms |
40776 KB |
Output is correct |
6 |
Correct |
188 ms |
40824 KB |
Output is correct |
7 |
Correct |
188 ms |
40824 KB |
Output is correct |
8 |
Correct |
179 ms |
31352 KB |
Output is correct |
9 |
Correct |
178 ms |
32248 KB |
Output is correct |
10 |
Correct |
183 ms |
26488 KB |
Output is correct |
11 |
Correct |
192 ms |
35192 KB |
Output is correct |
12 |
Correct |
189 ms |
36856 KB |
Output is correct |
13 |
Correct |
185 ms |
40824 KB |
Output is correct |
14 |
Correct |
180 ms |
41080 KB |
Output is correct |
15 |
Correct |
187 ms |
40824 KB |
Output is correct |
16 |
Correct |
187 ms |
40824 KB |
Output is correct |
17 |
Correct |
197 ms |
40824 KB |
Output is correct |
18 |
Correct |
179 ms |
40840 KB |
Output is correct |
19 |
Correct |
187 ms |
40952 KB |
Output is correct |
20 |
Correct |
179 ms |
26744 KB |
Output is correct |