oj.uz

답안 #1030488

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1030488 2024-07-22T05:45:26 Z vjudge1 고대 책들 (IOI17_books) C++17
0 / 100
 5 ms 984 KB 
#include "books.h"
#include<bits/stdc++.h>
#include <queue>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)
#define rng(i,l,r) for(int i=(l); i<(r); i++)
#define all(x) x.begin(),x.end()
using ll=long long;
const int INF=INT_MAX>>1;

struct SegTree{

	using T=pair<int,int>;
	inline T op(T x,T y){
		return {min(x.first,y.first),max(x.second,y.second)};
	}
	inline T e(){
		return {INF,-INF};
	}

	vector<T> tree;
	int size;
	SegTree(int sz):size(sz){
		tree.resize(size*2,e());
	}
	inline T get(int pos){
		return tree[pos+size];
	}
	inline void set(int pos,T val){
		tree[pos+size]=val;
	}
	T prod(int lf,int ri){
		lf+=size;
		ri+=size;
		T rl=e();
		T rr=e();
		while(lf<ri){
			if(lf&1){
				rl=op(rl,tree[lf]);
				lf++;
			}
			if(ri&1){
				ri--;
				rr=op(tree[ri],rr);
			}
			lf>>=1;
			ri>>=1;
		}
		return op(rl,rr);
	}
};

long long minimum_walk(std::vector<int> p, int s) {
	int n=p.size();
	vector<int> vis(n,-1);
	vector<pair<int,int>> wide;
	int cnt=0;
	ll ans=0;
	rep(i,n){
		if(vis[i]>=0)continue;
		if(p[i]==i&&i!=s)continue;
		int lf=i;
		int ri=i;
		int pos=i;
		while(vis[p[pos]]==-1){
			ans+=abs(pos-p[pos]);
			pos=p[pos];
			vis[pos]=cnt;
			lf=min(lf,pos);
			ri=max(ri,pos);
		}
		cnt++;
		wide.emplace_back(lf,ri);
	}
	vector<int> dist(cnt,-1);
	SegTree seg(n);
	rep(i,n){
		if(vis[i]!=-1)seg.set(i,{i,i});
	}
	priority_queue<pair<int,int>,vector<pair<int,int>>,less<pair<int,int>>> pq;
	pq.push({0,vis[s]});
	while(!pq.empty()){
		int dis,pos;
		tie(dis,pos)=pq.top();
		pq.pop();
		if(dist[pos]!=-1)continue;
		dist[pos]=0;
		ans+=dis*2;
		int lf,ri;
		tie(lf,ri)=wide[pos];
		rep(i,n){
			if(vis[i]==-1)continue;
			if(dist[vis[i]]!=-1)continue;
			if(i<lf){
				pq.push({abs(i-lf),vis[i]});
			}
			else if(ri<i){
				pq.push({abs(i-ri),vis[i]});
			}
			else{
				pq.push({0,vis[i]});
			}
		}
		/*
		while(true){
			int nxt=seg.prod(lf+1,ri).first;
			if(nxt>n)break;
			seg.set(nxt,seg.e());
			if(dist[vis[nxt]]==-1){
				pq.push({0,vis[nxt]});
			}
		}
		int nxt;
		nxt=seg.prod(0,lf).second;
		if(nxt>=0){
			if(dist[vis[nxt]]==-1){
				pq.push({abs(nxt-lf),vis[nxt]});
			}
		}
		nxt=seg.prod(ri+1,n).first;
		if(nxt<n){
			if(dist[vis[nxt]]==-1){
				pq.push({abs(nxt-ri),vis[nxt]});
			}
		}*/
	}
	return ans;
}

Subtask #1
0 / 12.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 28.0

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

Subtask #4
0 / 20.0

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

Subtask #5
0 / 30.0

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