oj.uz

Submission #1049607

# Submission time Handle Problem Language Result Execution time Memory
1049607 2024-08-09T02:15:06 Z pcc Ancient Books (IOI17_books) C++17
42 / 100
 2000 ms 311120 KB 
#include "books.h"
#include <bits/stdc++.h>
using namespace std;

#define pii pair<int,int>
#define ll long long
const int mxn = 1e6+10;
const int LEN = mxn*20;
int N;

int nid[LEN],to[LEN],wei[LEN],head[LEN];
int d1[LEN],d2[LEN];
ll ans = 0;
bitset<LEN> vis;
int ecnt,vcnt;
int seg[mxn*4];

void add_edge(int a,int b,int w){
	//cerr<<"ADD_EDGE: "<<a<<' '<<b<<' '<<w<<endl;
	ecnt++;
	nid[ecnt] = head[a];
	head[a] = ecnt;
	to[ecnt] = b;
	wei[ecnt] = w;
	return;
}

void build(int now,int l,int r){
	if(l == r){
		seg[now] = l;
		return;
	}
	seg[now] = vcnt++;
	int mid = (l+r)>>1;
	build(now*2+1,l,mid);
	build(now*2+2,mid+1,r);
	add_edge(seg[now*2+1],seg[now],0);
	add_edge(seg[now*2+2],seg[now],0);
	//cerr<<l<<' '<<r<<"::"<<seg[now]<<":"<<seg[now*2+1]<<' '<<seg[now*2+2]<<endl;
	return;
}

void add(int now,int l,int r,int s,int e,int p){
	if(l>=s&&e>=r){
		//cerr<<l<<' '<<r<<":"<<p<<endl;
		add_edge(seg[now],p,0);
		return;
	}
	int mid = (l+r)>>1;
	if(mid>=s)add(now*2+1,l,mid,s,e,p);
	if(mid<e)add(now*2+2,mid+1,r,s,e,p);
	return;
}

priority_queue<pii,vector<pii>,greater<pii>> pq;
void DIJKSTRA(int dist[]){
	vis.reset();
	for(int i = 0;i<vcnt;i++)pq.push(pii(dist[i],i));
	while(!pq.empty()){
		auto [d,now] = pq.top();
		pq.pop();
		if(vis[now])continue;
		vis[now] = true;
		for(int eid = head[now];eid;eid = nid[eid]){
			int nxt = to[eid],w = wei[eid];
			if(dist[nxt]>dist[now]+w){
				dist[nxt] = dist[now]+w;
				pq.push(pii(dist[nxt],nxt));
			}
		}
	}
	return;
}

long long minimum_walk(std::vector<int> p, int s) {
	N = p.size();
	vcnt = N;
	for(int i = 0;i+1<N;i++){
		add_edge(i,i+1,1);
		add_edge(i+1,i,1);
	}
	build(0,0,N-1);
	for(int i = 0;i<p.size();i++){
		ans += abs(i-p[i]);
		if(vis[i])continue;
		int now = i;
		int lp = i,rp = i;
		do{
			lp = min(lp,now);
			rp = max(rp,now);
			vis[now] = true;
			now = p[now];
		}while(now != i);
		int tar = vcnt++;
		add(0,0,N-1,lp,rp,tar);
		do{
			add_edge(tar,now,0);
			now = p[now];
		}while(now != i);
	}
	fill(d1,d1+LEN,LEN);
	fill(d2,d2+LEN,LEN);
	int tl = s,tr = s;
	for(int i = 0;i<N;i++){
		if(p[i] != i)tl = min(tl,i),tr = max(tr,i);
	}
	//cerr<<tl<<','<<tr<<endl;
	d1[tl] = d2[tr] = 0;
	DIJKSTRA(d1);
	DIJKSTRA(d2);
	//for(int i = 0;i<vcnt;i++)cerr<<d1[i]<<' ';cerr<<endl;
	//for(int i = 0;i<vcnt;i++)cerr<<d2[i]<<' ';cerr<<endl;
	for(int i = 0;i<vcnt;i++)d1[i] += d2[i];
	DIJKSTRA(d1);
	//for(int i = 0;i<vcnt;i++)cerr<<d1[i]<<' ';cerr<<endl;
	return ans+d1[s]*2;
}

Compilation message

books.cpp: In function 'long long int minimum_walk(std::vector<int>, int)':
books.cpp:83:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |  for(int i = 0;i<p.size();i++){
      |                ~^~~~~~~~~

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 166708 KB Output is correct
2 Correct 53 ms 166484 KB Output is correct
3 Correct 51 ms 166704 KB Output is correct
4 Correct 50 ms 166480 KB Output is correct
5 Correct 52 ms 166656 KB Output is correct
6 Correct 52 ms 166480 KB Output is correct
7 Correct 56 ms 166620 KB Output is correct
8 Correct 48 ms 166484 KB Output is correct
9 Correct 49 ms 166668 KB Output is correct
10 Correct 50 ms 166480 KB Output is correct
11 Correct 50 ms 166636 KB Output is correct
12 Correct 52 ms 166488 KB Output is correct
13 Correct 55 ms 166484 KB Output is correct
14 Correct 49 ms 166660 KB Output is correct
15 Correct 49 ms 166480 KB Output is correct
16 Correct 50 ms 166484 KB Output is correct
17 Correct 52 ms 166684 KB Output is correct
18 Correct 55 ms 166596 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 166708 KB Output is correct
2 Correct 53 ms 166484 KB Output is correct
3 Correct 51 ms 166704 KB Output is correct
4 Correct 50 ms 166480 KB Output is correct
5 Correct 52 ms 166656 KB Output is correct
6 Correct 52 ms 166480 KB Output is correct
7 Correct 56 ms 166620 KB Output is correct
8 Correct 48 ms 166484 KB Output is correct
9 Correct 49 ms 166668 KB Output is correct
10 Correct 50 ms 166480 KB Output is correct
11 Correct 50 ms 166636 KB Output is correct
12 Correct 52 ms 166488 KB Output is correct
13 Correct 55 ms 166484 KB Output is correct
14 Correct 49 ms 166660 KB Output is correct
15 Correct 49 ms 166480 KB Output is correct
16 Correct 50 ms 166484 KB Output is correct
17 Correct 52 ms 166684 KB Output is correct
18 Correct 55 ms 166596 KB Output is correct
19 Correct 52 ms 166736 KB Output is correct
20 Correct 53 ms 166772 KB Output is correct
21 Correct 50 ms 166664 KB Output is correct
22 Correct 53 ms 166736 KB Output is correct
23 Correct 50 ms 166736 KB Output is correct
24 Correct 50 ms 166676 KB Output is correct
25 Correct 50 ms 166736 KB Output is correct
26 Correct 52 ms 166740 KB Output is correct
27 Correct 51 ms 166736 KB Output is correct
28 Correct 51 ms 166736 KB Output is correct
29 Correct 51 ms 166704 KB Output is correct

Subtask #3
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 166708 KB Output is correct
2 Correct 53 ms 166484 KB Output is correct
3 Correct 51 ms 166704 KB Output is correct
4 Correct 50 ms 166480 KB Output is correct
5 Correct 52 ms 166656 KB Output is correct
6 Correct 52 ms 166480 KB Output is correct
7 Correct 56 ms 166620 KB Output is correct
8 Correct 48 ms 166484 KB Output is correct
9 Correct 49 ms 166668 KB Output is correct
10 Correct 50 ms 166480 KB Output is correct
11 Correct 50 ms 166636 KB Output is correct
12 Correct 52 ms 166488 KB Output is correct
13 Correct 55 ms 166484 KB Output is correct
14 Correct 49 ms 166660 KB Output is correct
15 Correct 49 ms 166480 KB Output is correct
16 Correct 50 ms 166484 KB Output is correct
17 Correct 52 ms 166684 KB Output is correct
18 Correct 55 ms 166596 KB Output is correct
19 Correct 52 ms 166736 KB Output is correct
20 Correct 53 ms 166772 KB Output is correct
21 Correct 50 ms 166664 KB Output is correct
22 Correct 53 ms 166736 KB Output is correct
23 Correct 50 ms 166736 KB Output is correct
24 Correct 50 ms 166676 KB Output is correct
25 Correct 50 ms 166736 KB Output is correct
26 Correct 52 ms 166740 KB Output is correct
27 Correct 51 ms 166736 KB Output is correct
28 Correct 51 ms 166736 KB Output is correct
29 Correct 51 ms 166704 KB Output is correct
30 Correct 1533 ms 284848 KB Output is correct
31 Correct 1672 ms 284828 KB Output is correct
32 Correct 1770 ms 300464 KB Output is correct
33 Correct 1480 ms 297644 KB Output is correct
34 Correct 1523 ms 297548 KB Output is correct
35 Correct 1382 ms 296156 KB Output is correct
36 Correct 1229 ms 292688 KB Output is correct
37 Correct 1087 ms 270520 KB Output is correct
38 Correct 1004 ms 271328 KB Output is correct
39 Correct 979 ms 271288 KB Output is correct
40 Correct 1063 ms 271320 KB Output is correct
41 Correct 1312 ms 287684 KB Output is correct
42 Correct 1237 ms 287924 KB Output is correct
43 Execution timed out 2025 ms 311120 KB Time limit exceeded
44 Halted 0 ms 0 KB -

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 166740 KB Output is correct
2 Correct 41 ms 166740 KB Output is correct
3 Correct 37 ms 166736 KB Output is correct
4 Correct 36 ms 166740 KB Output is correct
5 Correct 36 ms 166720 KB Output is correct
6 Correct 37 ms 166740 KB Output is correct
7 Correct 41 ms 166792 KB Output is correct
8 Correct 37 ms 166572 KB Output is correct
9 Correct 37 ms 166596 KB Output is correct
10 Correct 36 ms 166740 KB Output is correct
11 Correct 37 ms 166560 KB Output is correct
12 Correct 42 ms 166736 KB Output is correct
13 Correct 36 ms 166692 KB Output is correct
14 Correct 38 ms 166736 KB Output is correct
15 Correct 42 ms 166588 KB Output is correct
16 Correct 37 ms 166736 KB Output is correct
17 Correct 37 ms 166740 KB Output is correct
18 Correct 40 ms 166640 KB Output is correct
19 Correct 36 ms 166740 KB Output is correct
20 Correct 42 ms 166736 KB Output is correct

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 166708 KB Output is correct
2 Correct 53 ms 166484 KB Output is correct
3 Correct 51 ms 166704 KB Output is correct
4 Correct 50 ms 166480 KB Output is correct
5 Correct 52 ms 166656 KB Output is correct
6 Correct 52 ms 166480 KB Output is correct
7 Correct 56 ms 166620 KB Output is correct
8 Correct 48 ms 166484 KB Output is correct
9 Correct 49 ms 166668 KB Output is correct
10 Correct 50 ms 166480 KB Output is correct
11 Correct 50 ms 166636 KB Output is correct
12 Correct 52 ms 166488 KB Output is correct
13 Correct 55 ms 166484 KB Output is correct
14 Correct 49 ms 166660 KB Output is correct
15 Correct 49 ms 166480 KB Output is correct
16 Correct 50 ms 166484 KB Output is correct
17 Correct 52 ms 166684 KB Output is correct
18 Correct 55 ms 166596 KB Output is correct
19 Correct 52 ms 166736 KB Output is correct
20 Correct 53 ms 166772 KB Output is correct
21 Correct 50 ms 166664 KB Output is correct
22 Correct 53 ms 166736 KB Output is correct
23 Correct 50 ms 166736 KB Output is correct
24 Correct 50 ms 166676 KB Output is correct
25 Correct 50 ms 166736 KB Output is correct
26 Correct 52 ms 166740 KB Output is correct
27 Correct 51 ms 166736 KB Output is correct
28 Correct 51 ms 166736 KB Output is correct
29 Correct 51 ms 166704 KB Output is correct
30 Correct 1533 ms 284848 KB Output is correct
31 Correct 1672 ms 284828 KB Output is correct
32 Correct 1770 ms 300464 KB Output is correct
33 Correct 1480 ms 297644 KB Output is correct
34 Correct 1523 ms 297548 KB Output is correct
35 Correct 1382 ms 296156 KB Output is correct
36 Correct 1229 ms 292688 KB Output is correct
37 Correct 1087 ms 270520 KB Output is correct
38 Correct 1004 ms 271328 KB Output is correct
39 Correct 979 ms 271288 KB Output is correct
40 Correct 1063 ms 271320 KB Output is correct
41 Correct 1312 ms 287684 KB Output is correct
42 Correct 1237 ms 287924 KB Output is correct
43 Execution timed out 2025 ms 311120 KB Time limit exceeded
44 Halted 0 ms 0 KB -