#include "books.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> parent, ranga;
int find(int x){
if(parent[x]==-1) return x;
parent[x] = find(parent[x]);
return parent[x];
}
void join(int a, int b){
a = find(a);
b = find(b);
if(a==b) return;
if(ranga[a]>ranga[b]){
parent[b] = a;
}else if(ranga[b]>ranga[a]){
parent[a] = b;
}else{
parent[b] = a;
ranga[a]++;
}
}
long long minimum_walk(std::vector<int> p, int s) {
int n = p.size();
vector<int> odw(n);
parent.resize(n, -1);
ranga.resize(n);
long long wyn = 0;
queue<int> q;
vector<int> cost(n, 1e9);
for(int i = 0; i < n; i++){
int pt = i;
if(!odw[pt]){
if(p[pt]!=pt){
while(!odw[pt]){
odw[pt] = true;
cost[pt] = 0;
q.push(pt);
wyn+=abs(p[pt]-pt);
join(pt, p[pt]);
pt = p[pt];
}
}else{
odw[pt] = true;
if(pt==s)
cost[s] = 0, q.push(s);
}
}
}
while(q.size()){
int x = q.front();
//cout<<x<<" "<<cost[x]<<'\n';
q.pop();
if(x>0) if(find(x-1)!=find(x))
if(cost[x-1]==1e9){
cost[x-1] = cost[x]+1;
q.push(x-1);
join(x-1, x);
}else{
wyn+=2*(cost[x-1]+cost[x]+1);
join(x-1, x);
}
if(x<n-1) if(find(x+1)!=find(x))
if(cost[x+1]==1e9){
cost[x+1] = cost[x]+1;
q.push(x+1);
join(x+1, x);
}else{
wyn+=2*(cost[x+1]+cost[x]+1);
join(x+1, x);
}
}
return wyn;
}
Compilation message
books.cpp: In function 'long long int minimum_walk(std::vector<int>, int)':
books.cpp:59:13: warning: suggest explicit braces to avoid ambiguous 'else' [-Wdangling-else]
59 | if(x>0) if(find(x-1)!=find(x))
| ^
books.cpp:68:15: warning: suggest explicit braces to avoid ambiguous 'else' [-Wdangling-else]
68 | if(x<n-1) if(find(x+1)!=find(x))
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
212 KB |
Output is correct |
| 5 |
Correct |
1 ms |
296 KB |
Output is correct |
| 6 |
Incorrect |
1 ms |
212 KB |
3rd lines differ - on the 1st token, expected: '8', found: '10' |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
212 KB |
Output is correct |
| 5 |
Correct |
1 ms |
296 KB |
Output is correct |
| 6 |
Incorrect |
1 ms |
212 KB |
3rd lines differ - on the 1st token, expected: '8', found: '10' |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
212 KB |
Output is correct |
| 5 |
Correct |
1 ms |
296 KB |
Output is correct |
| 6 |
Incorrect |
1 ms |
212 KB |
3rd lines differ - on the 1st token, expected: '8', found: '10' |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
308 KB |
3rd lines differ - on the 1st token, expected: '3304', found: '4074' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
212 KB |
Output is correct |
| 5 |
Correct |
1 ms |
296 KB |
Output is correct |
| 6 |
Incorrect |
1 ms |
212 KB |
3rd lines differ - on the 1st token, expected: '8', found: '10' |
| 7 |
Halted |
0 ms |
0 KB |
- |
