#include "books.h"
#include <bits/stdc++.h>
using namespace std;
int vis[1000001],l[1000001];
vector <pair <int, pair <int, int>>> e;
vector <int> ve[1000001];
int f(int i){
return (l[i]==i?i:l[i]=f(l[i]));
}
int unite(int i, int j){
i=f(i);
j=f(j);
if (i==j)
return 0;
l[j]=i;
return 1;
}
long long minimum_walk(vector <int> p, int s){
int x=0,n=p.size();
iota(l,l+n,0);
long long d=0;
for (int i=0;i<n;i++){
if (!vis[i]){
int x=i;
while (true){
vis[x]=1;
ve[i].push_back(x);
d+=abs(x-p[x]);
x=p[x];
if (x==i)
break;
}
}
}
for (int i=0;i<n;i++)
sort(ve[i].begin(),ve[i].end());
for (int i=0;i<n;i++)
for (int j=0;j<n;j++){
if (i==j||ve[i].empty()||ve[j].empty())
continue;
if (ve[i].size()==1&&i!=s)
continue;
if (ve[j].size()==1&&j!=s)
continue;
int mn=1e9;
for (int k:ve[j]){
if (k>=ve[i][0]&&k<=ve[i].back()){
mn=0;
break;
}
mn=min(mn,abs(k-ve[i][0]));
mn=min(mn,abs(k-ve[i].back()));
}
e.push_back({mn,{i,j}});
}
sort(e.begin(),e.end());
for (auto [i,j]:e)
x+=i*unite(j.first,j.second);
return x*2+d;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
25176 KB |
Output is correct |
| 2 |
Correct |
5 ms |
25180 KB |
Output is correct |
| 3 |
Correct |
6 ms |
25180 KB |
Output is correct |
| 4 |
Correct |
5 ms |
25180 KB |
Output is correct |
| 5 |
Correct |
5 ms |
25180 KB |
Output is correct |
| 6 |
Correct |
5 ms |
25180 KB |
Output is correct |
| 7 |
Correct |
5 ms |
25180 KB |
Output is correct |
| 8 |
Correct |
5 ms |
25180 KB |
Output is correct |
| 9 |
Correct |
5 ms |
25180 KB |
Output is correct |
| 10 |
Correct |
5 ms |
25180 KB |
Output is correct |
| 11 |
Correct |
6 ms |
25180 KB |
Output is correct |
| 12 |
Correct |
5 ms |
25176 KB |
Output is correct |
| 13 |
Correct |
5 ms |
25180 KB |
Output is correct |
| 14 |
Correct |
6 ms |
25192 KB |
Output is correct |
| 15 |
Correct |
6 ms |
25180 KB |
Output is correct |
| 16 |
Correct |
6 ms |
25180 KB |
Output is correct |
| 17 |
Correct |
6 ms |
25256 KB |
Output is correct |
| 18 |
Correct |
6 ms |
25180 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
25176 KB |
Output is correct |
| 2 |
Correct |
5 ms |
25180 KB |
Output is correct |
| 3 |
Correct |
6 ms |
25180 KB |
Output is correct |
| 4 |
Correct |
5 ms |
25180 KB |
Output is correct |
| 5 |
Correct |
5 ms |
25180 KB |
Output is correct |
| 6 |
Correct |
5 ms |
25180 KB |
Output is correct |
| 7 |
Correct |
5 ms |
25180 KB |
Output is correct |
| 8 |
Correct |
5 ms |
25180 KB |
Output is correct |
| 9 |
Correct |
5 ms |
25180 KB |
Output is correct |
| 10 |
Correct |
5 ms |
25180 KB |
Output is correct |
| 11 |
Correct |
6 ms |
25180 KB |
Output is correct |
| 12 |
Correct |
5 ms |
25176 KB |
Output is correct |
| 13 |
Correct |
5 ms |
25180 KB |
Output is correct |
| 14 |
Correct |
6 ms |
25192 KB |
Output is correct |
| 15 |
Correct |
6 ms |
25180 KB |
Output is correct |
| 16 |
Correct |
6 ms |
25180 KB |
Output is correct |
| 17 |
Correct |
6 ms |
25256 KB |
Output is correct |
| 18 |
Correct |
6 ms |
25180 KB |
Output is correct |
| 19 |
Correct |
6 ms |
25180 KB |
Output is correct |
| 20 |
Correct |
6 ms |
25240 KB |
Output is correct |
| 21 |
Correct |
7 ms |
25180 KB |
Output is correct |
| 22 |
Correct |
11 ms |
26200 KB |
Output is correct |
| 23 |
Correct |
13 ms |
25948 KB |
Output is correct |
| 24 |
Correct |
12 ms |
25948 KB |
Output is correct |
| 25 |
Correct |
12 ms |
26196 KB |
Output is correct |
| 26 |
Correct |
8 ms |
25436 KB |
Output is correct |
| 27 |
Correct |
8 ms |
25436 KB |
Output is correct |
| 28 |
Correct |
8 ms |
25180 KB |
Output is correct |
| 29 |
Correct |
12 ms |
26028 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
25176 KB |
Output is correct |
| 2 |
Correct |
5 ms |
25180 KB |
Output is correct |
| 3 |
Correct |
6 ms |
25180 KB |
Output is correct |
| 4 |
Correct |
5 ms |
25180 KB |
Output is correct |
| 5 |
Correct |
5 ms |
25180 KB |
Output is correct |
| 6 |
Correct |
5 ms |
25180 KB |
Output is correct |
| 7 |
Correct |
5 ms |
25180 KB |
Output is correct |
| 8 |
Correct |
5 ms |
25180 KB |
Output is correct |
| 9 |
Correct |
5 ms |
25180 KB |
Output is correct |
| 10 |
Correct |
5 ms |
25180 KB |
Output is correct |
| 11 |
Correct |
6 ms |
25180 KB |
Output is correct |
| 12 |
Correct |
5 ms |
25176 KB |
Output is correct |
| 13 |
Correct |
5 ms |
25180 KB |
Output is correct |
| 14 |
Correct |
6 ms |
25192 KB |
Output is correct |
| 15 |
Correct |
6 ms |
25180 KB |
Output is correct |
| 16 |
Correct |
6 ms |
25180 KB |
Output is correct |
| 17 |
Correct |
6 ms |
25256 KB |
Output is correct |
| 18 |
Correct |
6 ms |
25180 KB |
Output is correct |
| 19 |
Correct |
6 ms |
25180 KB |
Output is correct |
| 20 |
Correct |
6 ms |
25240 KB |
Output is correct |
| 21 |
Correct |
7 ms |
25180 KB |
Output is correct |
| 22 |
Correct |
11 ms |
26200 KB |
Output is correct |
| 23 |
Correct |
13 ms |
25948 KB |
Output is correct |
| 24 |
Correct |
12 ms |
25948 KB |
Output is correct |
| 25 |
Correct |
12 ms |
26196 KB |
Output is correct |
| 26 |
Correct |
8 ms |
25436 KB |
Output is correct |
| 27 |
Correct |
8 ms |
25436 KB |
Output is correct |
| 28 |
Correct |
8 ms |
25180 KB |
Output is correct |
| 29 |
Correct |
12 ms |
26028 KB |
Output is correct |
| 30 |
Execution timed out |
2060 ms |
51140 KB |
Time limit exceeded |
| 31 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
26200 KB |
3rd lines differ - on the 1st token, expected: '3304', found: '2744' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
25176 KB |
Output is correct |
| 2 |
Correct |
5 ms |
25180 KB |
Output is correct |
| 3 |
Correct |
6 ms |
25180 KB |
Output is correct |
| 4 |
Correct |
5 ms |
25180 KB |
Output is correct |
| 5 |
Correct |
5 ms |
25180 KB |
Output is correct |
| 6 |
Correct |
5 ms |
25180 KB |
Output is correct |
| 7 |
Correct |
5 ms |
25180 KB |
Output is correct |
| 8 |
Correct |
5 ms |
25180 KB |
Output is correct |
| 9 |
Correct |
5 ms |
25180 KB |
Output is correct |
| 10 |
Correct |
5 ms |
25180 KB |
Output is correct |
| 11 |
Correct |
6 ms |
25180 KB |
Output is correct |
| 12 |
Correct |
5 ms |
25176 KB |
Output is correct |
| 13 |
Correct |
5 ms |
25180 KB |
Output is correct |
| 14 |
Correct |
6 ms |
25192 KB |
Output is correct |
| 15 |
Correct |
6 ms |
25180 KB |
Output is correct |
| 16 |
Correct |
6 ms |
25180 KB |
Output is correct |
| 17 |
Correct |
6 ms |
25256 KB |
Output is correct |
| 18 |
Correct |
6 ms |
25180 KB |
Output is correct |
| 19 |
Correct |
6 ms |
25180 KB |
Output is correct |
| 20 |
Correct |
6 ms |
25240 KB |
Output is correct |
| 21 |
Correct |
7 ms |
25180 KB |
Output is correct |
| 22 |
Correct |
11 ms |
26200 KB |
Output is correct |
| 23 |
Correct |
13 ms |
25948 KB |
Output is correct |
| 24 |
Correct |
12 ms |
25948 KB |
Output is correct |
| 25 |
Correct |
12 ms |
26196 KB |
Output is correct |
| 26 |
Correct |
8 ms |
25436 KB |
Output is correct |
| 27 |
Correct |
8 ms |
25436 KB |
Output is correct |
| 28 |
Correct |
8 ms |
25180 KB |
Output is correct |
| 29 |
Correct |
12 ms |
26028 KB |
Output is correct |
| 30 |
Execution timed out |
2060 ms |
51140 KB |
Time limit exceeded |
| 31 |
Halted |
0 ms |
0 KB |
- |
