oj.uz

답안 #384860

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
384860 2021-04-02T13:46:17 Z kshitij_sodani 고대 책들 (IOI17_books) C++14
12 / 100
 39 ms 55404 KB 
//#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
typedef long long llo;
#define mp make_pair
#define pb push_back
#define a first 
#define b second
#define endl '\n'


#include "books.h"
llo ans=0;
llo n;
vector<llo> adj[1000001];
llo vis[1000001];
pair<llo,llo> cot[1000001];
llo par[1000001];
llo find(llo no){
	if(par[no]==no){
		return no;
	}
	par[no]=find(par[no]);
	return par[no];
}
vector<llo> ss;
void dfs(int no){
	vis[no]=1;
	ss.pb(no);
	for(auto j:adj[no]){
		if(vis[j]==0){
			dfs(j);
		}
	}
}


vector<llo> adj2[1000001];
llo ind[1000001];
pair<llo,llo> pp;
vector<pair<llo,llo>> tt;

llo dp[1001][1001];
pair<llo,llo> rr[1000001];
void dfs2(int no,int par=-1){
	pp.a=min(pp.a,tt[no].a);
	pp.b=max(pp.b,tt[no].b);
	vis[no]=1;
	for(auto j:adj2[no]){
		if(vis[j]==0){
			dfs(j);
		}
	}
}

long long minimum_walk(std::vector<int> p, int s) {
	while(p.size()){
		if(p.back()+1==p.size()){
			p.pop_back();
		}
		else{
			break;
		}
	}


	n=p.size();
//cout<<p.size()<<":"<<endl;
	if(n==0){
		return 0;
	}
	for(int i=0;i<n;i++){
		adj[i].pb(p[i]);
	}
	//llo co=0;
	llo ans=0;
	
	for(int i=0;i<n;i++){
		if(vis[i]==0){
			ss.clear();
			dfs(i);
			/*if(ss.size()==0){
				continue;
			}*/
			llo mi=ss[0];
			llo ma=ss[0];
			for(auto j:ss){
				mi=min(mi,j);
				ma=max(ma,j);
			}
			for(auto j:ss){
				cot[j]={mi,ma};
			}
			for(auto j:ss){
				ind[j]=tt.size();
			}
			tt.pb({mi,ma});
			//co++;
			
			for(int j=0;j+1<ss.size();j++){
				ans+=abs(ss[j]-ss[j+1]);
			}
		/*	for(auto j:ss){
				cout<<j<<",,";
			}
			cout<<endl;*/
			ans+=(abs(ss[0]-ss.back()));
		}
	}
	for(int i=0;i<tt.size();i++){
		for(int j=0;j<n;j++){
			if(ind[j]!=i){
				if(j>=tt[i].a and j<=tt[i].b){
					adj2[i].pb(ind[j]);
				}
			}
		}
	}
	for(int j=0;j<tt.size();j++){
		for(int i=0;i<tt.size();i++){
			vis[i]=0;
		}
		pp=tt[j];
		dfs2(j);
		for(int i=0;i<n;i++){
			if(ind[i]==j){
				rr[i]=pp;
			}
		}
		//cout<<pp.a<<","<<pp.b<<endl;
	}
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			dp[i][j]=-1;
		}
	}
	dp[rr[s].a][rr[s].b]=0;
	/*for(int i=0;i<n;i++){
		cout<<rr[i].a<<"<"<<rr[i].b<<endl;
	}*/
//	solve(rr[s].a,rr[s].b);
	for(llo ii=0;ii<n;ii++){
		for(llo i=0;i+ii<n;i++){
			llo j=i+ii;
			if(dp[i][j]==-1){
				continue;
			}
			if(i>0){
				pair<llo,llo> ac={rr[i-1].a,max(rr[i-1].b,j)};
				if(dp[ac.a][ac.b]==-1){
					dp[ac.a][ac.b]=dp[i][j]+2;
				}
				dp[ac.a][ac.b]=min(dp[ac.a][ac.b],dp[i][j]+2);
			}
			if(j<n-1){
				pair<llo,llo> ac={min(rr[j+1].a,i),rr[j+1].b};
				if(dp[ac.a][ac.b]==-1){
					dp[ac.a][ac.b]=dp[i][j]+2;
				}
				dp[ac.a][ac.b]=min(dp[ac.a][ac.b],dp[i][j]+2);




			}
		}
	}
	/*for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			cout<<dp[i][j]<<",";
		}
		cout<<endl;

	}
*/







	//ans+=2*(co-1);

	return ans+dp[0][n-1];
}

Compilation message

books.cpp: In function 'long long int minimum_walk(std::vector<int>, int)':
books.cpp:58:16: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |   if(p.back()+1==p.size()){
      |      ~~~~~~~~~~^~~~~~~~~~
books.cpp:100:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |    for(int j=0;j+1<ss.size();j++){
      |                ~~~^~~~~~~~~~
books.cpp:110:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  110 |  for(int i=0;i<tt.size();i++){
      |              ~^~~~~~~~~~
books.cpp:119:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  119 |  for(int j=0;j<tt.size();j++){
      |              ~^~~~~~~~~~
books.cpp:120:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  120 |   for(int i=0;i<tt.size();i++){
      |               ~^~~~~~~~~~

Subtask #1
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 32 ms 47340 KB Output is correct
2 Correct 30 ms 47340 KB Output is correct
3 Correct 30 ms 47340 KB Output is correct
4 Correct 31 ms 47468 KB Output is correct
5 Correct 35 ms 47340 KB Output is correct
6 Correct 31 ms 47340 KB Output is correct
7 Correct 30 ms 47340 KB Output is correct
8 Correct 30 ms 47340 KB Output is correct
9 Correct 30 ms 47340 KB Output is correct
10 Correct 31 ms 47340 KB Output is correct
11 Correct 30 ms 47340 KB Output is correct
12 Correct 31 ms 47340 KB Output is correct
13 Correct 31 ms 47340 KB Output is correct
14 Correct 30 ms 47340 KB Output is correct
15 Correct 30 ms 47340 KB Output is correct
16 Correct 31 ms 47340 KB Output is correct
17 Correct 35 ms 47340 KB Output is correct
18 Correct 34 ms 47344 KB Output is correct

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 32 ms 47340 KB Output is correct
2 Correct 30 ms 47340 KB Output is correct
3 Correct 30 ms 47340 KB Output is correct
4 Correct 31 ms 47468 KB Output is correct
5 Correct 35 ms 47340 KB Output is correct
6 Correct 31 ms 47340 KB Output is correct
7 Correct 30 ms 47340 KB Output is correct
8 Correct 30 ms 47340 KB Output is correct
9 Correct 30 ms 47340 KB Output is correct
10 Correct 31 ms 47340 KB Output is correct
11 Correct 30 ms 47340 KB Output is correct
12 Correct 31 ms 47340 KB Output is correct
13 Correct 31 ms 47340 KB Output is correct
14 Correct 30 ms 47340 KB Output is correct
15 Correct 30 ms 47340 KB Output is correct
16 Correct 31 ms 47340 KB Output is correct
17 Correct 35 ms 47340 KB Output is correct
18 Correct 34 ms 47344 KB Output is correct
19 Incorrect 35 ms 55404 KB 3rd lines differ - on the 1st token, expected: '338572', found: '338576'
20 Halted 0 ms 0 KB -

Subtask #3
0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Correct 32 ms 47340 KB Output is correct
2 Correct 30 ms 47340 KB Output is correct
3 Correct 30 ms 47340 KB Output is correct
4 Correct 31 ms 47468 KB Output is correct
5 Correct 35 ms 47340 KB Output is correct
6 Correct 31 ms 47340 KB Output is correct
7 Correct 30 ms 47340 KB Output is correct
8 Correct 30 ms 47340 KB Output is correct
9 Correct 30 ms 47340 KB Output is correct
10 Correct 31 ms 47340 KB Output is correct
11 Correct 30 ms 47340 KB Output is correct
12 Correct 31 ms 47340 KB Output is correct
13 Correct 31 ms 47340 KB Output is correct
14 Correct 30 ms 47340 KB Output is correct
15 Correct 30 ms 47340 KB Output is correct
16 Correct 31 ms 47340 KB Output is correct
17 Correct 35 ms 47340 KB Output is correct
18 Correct 34 ms 47344 KB Output is correct
19 Incorrect 35 ms 55404 KB 3rd lines differ - on the 1st token, expected: '338572', found: '338576'
20 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 39 ms 55276 KB 3rd lines differ - on the 1st token, expected: '3304', found: '3314'
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 32 ms 47340 KB Output is correct
2 Correct 30 ms 47340 KB Output is correct
3 Correct 30 ms 47340 KB Output is correct
4 Correct 31 ms 47468 KB Output is correct
5 Correct 35 ms 47340 KB Output is correct
6 Correct 31 ms 47340 KB Output is correct
7 Correct 30 ms 47340 KB Output is correct
8 Correct 30 ms 47340 KB Output is correct
9 Correct 30 ms 47340 KB Output is correct
10 Correct 31 ms 47340 KB Output is correct
11 Correct 30 ms 47340 KB Output is correct
12 Correct 31 ms 47340 KB Output is correct
13 Correct 31 ms 47340 KB Output is correct
14 Correct 30 ms 47340 KB Output is correct
15 Correct 30 ms 47340 KB Output is correct
16 Correct 31 ms 47340 KB Output is correct
17 Correct 35 ms 47340 KB Output is correct
18 Correct 34 ms 47344 KB Output is correct
19 Incorrect 35 ms 55404 KB 3rd lines differ - on the 1st token, expected: '338572', found: '338576'
20 Halted 0 ms 0 KB -