답안 #1049607

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1049607	2024-08-09T02:15:06 Z	pcc	고대 책들 (IOI17_books)	C++17	42 / 100	2000 ms	311120 KB

books

#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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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	-