제출 #165648

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
165648		Segtree	고대 책들 (IOI17_books)	C++14	0 / 100	58 ms	55288 KiB

books

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#include<unordered_set>
#include<set>
#include"books.h"
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
typedef vector<int> vi;
#define chmin(a,b) a=min(a,b)
#define N 1000010
namespace uf{
    ll par[N];
    void init(){
	for(int i=0;i<N;i++)par[i]=i;
    }
    ll pare(ll x){
	return par[x]=(par[x]==x?x:pare(par[x]));
    }
    void unite(ll a,ll b){
	a=pare(a),b=pare(b);
	par[a]=b;
    }
};
vector<int> cyc[N];
struct qry{
    ll l,r,id;
    bool type;
    bool operator<(const qry&key)const{
	return this->l<key.l;
    }
    qry(ll l,ll r,ll id,bool type){
	this->l=l,this->r=r,this->id=id,this->type=type;
    }
};
int wh[N];
vector<P> g[N];
void makee(ll a,ll b,ll c){
    //cout<<"edge:"<<a<<" "<<b<<" "<<c<<endl;
    g[a].push_back(make_pair(b,c));
}
ll dist[N];

ll minimum_walk(vi p,int s){
    int n=p.size();
    ll ans=0;
    
    int m=0;
    unordered_set<int> vis;
    for(int i=0;i<n;i++){
	if(vis.find(i)!=vis.end())continue;
	ll x=i;
	while(1){
	    vis.insert(x);
	    cyc[m].push_back(x);
	    ans+=abs(x-p[x]);
	    x=p[x];
	    if(x==i)break;
	}
	if(cyc[m].size()==1)cyc[m].clear();
	else{
	    sort(cyc[m].begin(),cyc[m].end());
	    m++;
	}
    }/*
    cout<<"H"<<endl;
    cout<<m<<endl;
    for(int i=0;i<m;i++){
	for(auto t:cyc[i])cout<<t<<" "; cout<<endl;
    }*/
    uf::init();
    vector<qry> Q;
    for(int i=0;i<m;i++){
	for(int j=1;j<cyc[i].size();j++){
	    Q.push_back(qry(cyc[i][0],cyc[i][j],i,0));
	}
	for(int j=0;j<cyc[i].size()-1;j++){
	    Q.push_back(qry(cyc[i][j],cyc[i].back(),i,1));
	}
    }
    sort(Q.begin(),Q.end());
    priority_queue<P,vector<P>,greater<P> > S;
    for(auto t:Q){
	if(t.type==0){
	    S.push(make_pair(t.r,t.id));
	}
	if(t.type==1){
	    P last=make_pair(-1,-1);
	    while(!S.empty()&&S.top().first<t.r){
		uf::unite(S.top().second,t.id);
		last=S.top();
		S.pop();
	    }
	    if(last.first!=-1){
		S.push(last);
	    }
	}
    }
    for(int i=0;i<n;i++)wh[i]=-1;
    for(int i=0;i<m;i++){
	int pp=uf::pare(i);
	if(i!=pp){
	    for(auto t:cyc[i]){
		cyc[pp].push_back(t);
		wh[t]=pp;
	    }
	    cyc[i].clear();
	}
	else{
	    for(auto t:cyc[i])wh[t]=i;
	}
    }/*
    cout<<"He"<<endl;
    for(int i=0;i<m;i++){
	for(auto t:cyc[i])cout<<t<<" "; cout<<endl;
    }*/
    vector<ll> kyma;
    Q.clear(); //Q reuse
    for(int i=0;i<m;i++){
	if(cyc[i].size()==0)continue;
	sort(cyc[i].begin(),cyc[i].end());
	Q.push_back(qry(cyc[i][0],cyc[i].back(),i,0));
    }
    sort(Q.begin(),Q.end());
    stack<int> st;
    int nxtl=-1;
    for(auto t:Q){
	while(!st.empty()&&cyc[st.top()].back()<t.l){
	    nxtl=st.top();
	    st.pop();
	}
	if(~nxtl){
	    ll cost=t.l-cyc[nxtl].back();
	    makee(nxtl,t.id,cost);
	    makee(t.id,nxtl,cost);
	}
	if(!st.empty()){
	    auto it=lower_bound(cyc[st.top()].begin(),cyc[st.top()].end(),t.l);
	    ll rs=*it;
	    it--; ll ls=*it;
	    ll cost=2*min(t.l-ls,rs-t.r);
	    makee(t.id,st.top(),cost);
	}
	else{
	    kyma.push_back(t.id);
	}
    }
    //cout<<"Li"<<endl;
    for(int i=0;i<n;i++){
	if(~wh[i])makee(m,wh[i],2*abs(s-i));
    }
    for(int i=0;i<=m;i++)dist[i]=1e17;
    while(!S.empty())S.pop(); //S.reuse
    S.push(make_pair(0,m));
    while(!S.empty()){
	ll cost=S.top().first;
	ll x=S.top().second;
	S.pop();
	if(dist[x]<=cost)continue;
	dist[x]=cost;
	for(auto y:g[x]){
	    S.push(make_pair(cost+y.second,y.first));
	}
    }
    //for(int i=0;i<=m;i++)cout<<dist[i]<<" ";cout<<endl;
    ll mi=1e17;
    for(auto t:kyma){
	chmin(mi,dist[t]);
    }
    ans+=mi;
    for(int i=0;i<kyma.size()-1;i++){
	ans+=2*(cyc[kyma[i+1]][0]-cyc[kyma[i]].back());
    }
    return ans;
}/*
int main(){
    int n,s; cin>>n>>s;
    vi p(n);
    for(int i=0;i<n;i++){
	cin>>p[i];
    }
    cout<<minimum_walk(p,s)<<endl;
}*/

컴파일 시 표준 에러 (stderr) 메시지

books.cpp: In function 'll minimum_walk(vi, int)':
books.cpp:77:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int j=1;j<cyc[i].size();j++){
              ~^~~~~~~~~~~~~~
books.cpp:80:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int j=0;j<cyc[i].size()-1;j++){
              ~^~~~~~~~~~~~~~~~
books.cpp:174:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<kyma.size()-1;i++){
                 ~^~~~~~~~~~~~~~

• Subtask 1: 0 / 12
• Subtask 2: 0 / 10
• Subtask 3: 0 / 28
• Subtask 4: 0 / 20
• Subtask 5: 0 / 30