#include "books.h"
#include <bits/stdc++.h>
#define MAXN 1000007
using namespace std;
bool vi[MAXN];
int a[MAXN],mik[MAXN],mak[MAXN],cnt;
long long d[1007][1007];
long long md[MAXN];
long long MST(int s)
{
for(int i=1;i<=cnt;i++) {vi[i]=false; md[i]=MAXN;}
md[s]=0;
long long t=0;
for(int x=0;x<cnt;x++)
{
pair<long long,int> mi=make_pair(MAXN,0);
for(int i=1;i<=cnt;i++) if(!vi[i]) mi=min(make_pair(md[i],i),mi);
int u=mi.second;
t+=mi.first;
vi[u]=true;
for(int i=1;i<=cnt;i++) if(!vi[i]) md[i]=min(md[i],d[u][i]);
}
return t;
}
long long minimum_walk(std::vector<int> p, int s)
{
long long sk=0;
for(int i=0;i<p.size();i++) if(!vi[i])
{
if(p[i]==i) continue;
int prev=i;
++cnt;
mik[cnt]=mak[cnt]=i;
while(!vi[i])
{
a[i]=cnt;
mik[cnt]=min(mik[cnt],i);
mak[cnt]=max(mak[cnt],i);
vi[i]=true;
i=p[i];
sk+=abs((long long)i-prev);
prev=i;
}
}
if(p[s]==s) {a[s]=++cnt; mak[cnt]=mik[cnt]=s;}
for(int i=1;i<=cnt;i++) for(int j=0;j<=cnt;j++) d[i][j]=MAXN;
for(int i=1;i<=cnt;i++) for(int j=0;j<p.size();j++)
{
if(j>=mik[i] && j<=mak[i]) d[i][a[j]]=0;
else d[i][a[j]]=min(d[i][a[j]],max((long long)mik[i]-j,(long long)j-mak[i]));
}
return sk+2LL*MST(a[s]);
}
Compilation message
books.cpp: In function 'long long int minimum_walk(std::vector<int>, int)':
books.cpp:28:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
28 | for(int i=0;i<p.size();i++) if(!vi[i])
| ~^~~~~~~~~
books.cpp:47:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
47 | for(int i=1;i<=cnt;i++) for(int j=0;j<p.size();j++)
| ~^~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Correct |
1 ms |
512 KB |
Output is correct |
| 3 |
Correct |
0 ms |
384 KB |
Output is correct |
| 4 |
Correct |
0 ms |
384 KB |
Output is correct |
| 5 |
Correct |
0 ms |
384 KB |
Output is correct |
| 6 |
Correct |
1 ms |
384 KB |
Output is correct |
| 7 |
Correct |
0 ms |
384 KB |
Output is correct |
| 8 |
Correct |
0 ms |
384 KB |
Output is correct |
| 9 |
Correct |
0 ms |
384 KB |
Output is correct |
| 10 |
Correct |
1 ms |
384 KB |
Output is correct |
| 11 |
Correct |
0 ms |
384 KB |
Output is correct |
| 12 |
Correct |
1 ms |
384 KB |
Output is correct |
| 13 |
Correct |
1 ms |
384 KB |
Output is correct |
| 14 |
Correct |
1 ms |
384 KB |
Output is correct |
| 15 |
Correct |
1 ms |
384 KB |
Output is correct |
| 16 |
Correct |
1 ms |
384 KB |
Output is correct |
| 17 |
Correct |
0 ms |
384 KB |
Output is correct |
| 18 |
Correct |
1 ms |
384 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Correct |
1 ms |
512 KB |
Output is correct |
| 3 |
Correct |
0 ms |
384 KB |
Output is correct |
| 4 |
Correct |
0 ms |
384 KB |
Output is correct |
| 5 |
Correct |
0 ms |
384 KB |
Output is correct |
| 6 |
Correct |
1 ms |
384 KB |
Output is correct |
| 7 |
Correct |
0 ms |
384 KB |
Output is correct |
| 8 |
Correct |
0 ms |
384 KB |
Output is correct |
| 9 |
Correct |
0 ms |
384 KB |
Output is correct |
| 10 |
Correct |
1 ms |
384 KB |
Output is correct |
| 11 |
Correct |
0 ms |
384 KB |
Output is correct |
| 12 |
Correct |
1 ms |
384 KB |
Output is correct |
| 13 |
Correct |
1 ms |
384 KB |
Output is correct |
| 14 |
Correct |
1 ms |
384 KB |
Output is correct |
| 15 |
Correct |
1 ms |
384 KB |
Output is correct |
| 16 |
Correct |
1 ms |
384 KB |
Output is correct |
| 17 |
Correct |
0 ms |
384 KB |
Output is correct |
| 18 |
Correct |
1 ms |
384 KB |
Output is correct |
| 19 |
Correct |
1 ms |
384 KB |
Output is correct |
| 20 |
Correct |
1 ms |
384 KB |
Output is correct |
| 21 |
Correct |
1 ms |
384 KB |
Output is correct |
| 22 |
Correct |
2 ms |
1408 KB |
Output is correct |
| 23 |
Correct |
2 ms |
1536 KB |
Output is correct |
| 24 |
Correct |
2 ms |
1440 KB |
Output is correct |
| 25 |
Correct |
2 ms |
1536 KB |
Output is correct |
| 26 |
Correct |
2 ms |
896 KB |
Output is correct |
| 27 |
Correct |
1 ms |
768 KB |
Output is correct |
| 28 |
Correct |
1 ms |
512 KB |
Output is correct |
| 29 |
Correct |
2 ms |
1536 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Correct |
1 ms |
512 KB |
Output is correct |
| 3 |
Correct |
0 ms |
384 KB |
Output is correct |
| 4 |
Correct |
0 ms |
384 KB |
Output is correct |
| 5 |
Correct |
0 ms |
384 KB |
Output is correct |
| 6 |
Correct |
1 ms |
384 KB |
Output is correct |
| 7 |
Correct |
0 ms |
384 KB |
Output is correct |
| 8 |
Correct |
0 ms |
384 KB |
Output is correct |
| 9 |
Correct |
0 ms |
384 KB |
Output is correct |
| 10 |
Correct |
1 ms |
384 KB |
Output is correct |
| 11 |
Correct |
0 ms |
384 KB |
Output is correct |
| 12 |
Correct |
1 ms |
384 KB |
Output is correct |
| 13 |
Correct |
1 ms |
384 KB |
Output is correct |
| 14 |
Correct |
1 ms |
384 KB |
Output is correct |
| 15 |
Correct |
1 ms |
384 KB |
Output is correct |
| 16 |
Correct |
1 ms |
384 KB |
Output is correct |
| 17 |
Correct |
0 ms |
384 KB |
Output is correct |
| 18 |
Correct |
1 ms |
384 KB |
Output is correct |
| 19 |
Correct |
1 ms |
384 KB |
Output is correct |
| 20 |
Correct |
1 ms |
384 KB |
Output is correct |
| 21 |
Correct |
1 ms |
384 KB |
Output is correct |
| 22 |
Correct |
2 ms |
1408 KB |
Output is correct |
| 23 |
Correct |
2 ms |
1536 KB |
Output is correct |
| 24 |
Correct |
2 ms |
1440 KB |
Output is correct |
| 25 |
Correct |
2 ms |
1536 KB |
Output is correct |
| 26 |
Correct |
2 ms |
896 KB |
Output is correct |
| 27 |
Correct |
1 ms |
768 KB |
Output is correct |
| 28 |
Correct |
1 ms |
512 KB |
Output is correct |
| 29 |
Correct |
2 ms |
1536 KB |
Output is correct |
| 30 |
Correct |
283 ms |
19960 KB |
Output is correct |
| 31 |
Correct |
307 ms |
19832 KB |
Output is correct |
| 32 |
Correct |
158 ms |
14968 KB |
Output is correct |
| 33 |
Runtime error |
708 ms |
65172 KB |
Execution killed with signal 11 |
| 34 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
2 ms |
1408 KB |
3rd lines differ - on the 1st token, expected: '3304', found: '3324' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Correct |
1 ms |
512 KB |
Output is correct |
| 3 |
Correct |
0 ms |
384 KB |
Output is correct |
| 4 |
Correct |
0 ms |
384 KB |
Output is correct |
| 5 |
Correct |
0 ms |
384 KB |
Output is correct |
| 6 |
Correct |
1 ms |
384 KB |
Output is correct |
| 7 |
Correct |
0 ms |
384 KB |
Output is correct |
| 8 |
Correct |
0 ms |
384 KB |
Output is correct |
| 9 |
Correct |
0 ms |
384 KB |
Output is correct |
| 10 |
Correct |
1 ms |
384 KB |
Output is correct |
| 11 |
Correct |
0 ms |
384 KB |
Output is correct |
| 12 |
Correct |
1 ms |
384 KB |
Output is correct |
| 13 |
Correct |
1 ms |
384 KB |
Output is correct |
| 14 |
Correct |
1 ms |
384 KB |
Output is correct |
| 15 |
Correct |
1 ms |
384 KB |
Output is correct |
| 16 |
Correct |
1 ms |
384 KB |
Output is correct |
| 17 |
Correct |
0 ms |
384 KB |
Output is correct |
| 18 |
Correct |
1 ms |
384 KB |
Output is correct |
| 19 |
Correct |
1 ms |
384 KB |
Output is correct |
| 20 |
Correct |
1 ms |
384 KB |
Output is correct |
| 21 |
Correct |
1 ms |
384 KB |
Output is correct |
| 22 |
Correct |
2 ms |
1408 KB |
Output is correct |
| 23 |
Correct |
2 ms |
1536 KB |
Output is correct |
| 24 |
Correct |
2 ms |
1440 KB |
Output is correct |
| 25 |
Correct |
2 ms |
1536 KB |
Output is correct |
| 26 |
Correct |
2 ms |
896 KB |
Output is correct |
| 27 |
Correct |
1 ms |
768 KB |
Output is correct |
| 28 |
Correct |
1 ms |
512 KB |
Output is correct |
| 29 |
Correct |
2 ms |
1536 KB |
Output is correct |
| 30 |
Correct |
283 ms |
19960 KB |
Output is correct |
| 31 |
Correct |
307 ms |
19832 KB |
Output is correct |
| 32 |
Correct |
158 ms |
14968 KB |
Output is correct |
| 33 |
Runtime error |
708 ms |
65172 KB |
Execution killed with signal 11 |
| 34 |
Halted |
0 ms |
0 KB |
- |
