제출 #521311

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
521311		ymm	고대 책들 (IOI17_books)	C++17	0 / 100	4 ms	8140 KiB

books

///
///   Oh? You're approaching me?
///

#include <bits/stdc++.h>
#define Loop(x,l,r) for(ll x = ll(l); x < ll(r); ++x)
#define LoopR(x,l,r) for(ll x = ll(r)-1; x >= ll(l); --x)
#define Kill(x) exit((cout << (x) << '\n', 0))
typedef long long ll;
typedef std::pair<int,int> pii;
typedef std::pair<ll,ll> pll;
using namespace std;

#include "books.h"

const int N = 1'000'010;
int col[N]; int cnt=0;
int mn[N], mx[N];

int c1[N], c2[N];

ll minimum_walk(vector<int> p, int s) {
	int n = p.size();
	fill(col,col+N,-1);
	fill(mn,mn+N,N);
	Loop(i,0,n){
		if(col[i]<0){
			int j = i;
			while(col[j]<0){
				mn[cnt] = min(mn[cnt], j);
				mx[cnt] = max(mx[cnt], j);
				col[j] = cnt;
				j = p[j];
			}
			++cnt;
		}
	}
	int l=0, r=n-1;
	while(l<s && p[l]==l) ++l;
	while(r>s && p[r]==r) --r;
//	Loop(i,0,n) cout << col[i] << ' '; cout << '\n';
//	Loop(i,0,cnt) cout << mx[i] << ' '; cout << '\n';
//	Loop(i,0,cnt) cout << mn[i] << ' '; cout << '\n';
	Loop(i,l,r+1){
		c1[i]++;
		c1[mx[col[i]]]--;
		c2[i+1]--;
		c2[mn[col[i]]+1]++;
	}
	int root, droot;
	// bfs
	{
		vector<int> dis(n, N);
		set<int> cand; Loop(i,l,r+1) cand.insert(0);
		deque<pii> q; q.emplace_back(col[s], 0); dis[col[s]]=0;
		while(q.size()){
			auto [v, d] = q.front(); q.pop_front();
			if(d != dis[v]) continue;
			int mn = ::mn[v], mx = ::mx[v];
			if(mn <= s && s <= mx) { root = v; droot = d; }
			for(;;){
				int i;
				auto it = cand.lower_bound(mn);
				if(it == cand.end() || (i = *it) > mx) break;
				cand.erase(it);
				if(d < dis[i = col[i]]){
					dis[i] = d;
					q.emplace_front(i, d);
				}
			}
			if(l<mn && d+1<dis[col[mn-1]]){
				dis[col[mn-1]] = d+1;
				q.emplace_back(col[mn-1], d+1);
			}
			if(mx<r && d+1<dis[col[mx+1]]){
				dis[col[mx+1]] = d+1;
				q.emplace_back(col[mn-1], d+1);
			}
		}
	}
//	cout << root << ' ' << droot << '\n';
	ll ans = 0;
	Loop(i,l,r+1) ans += abs(i-p[i]);
	Loop(i,mx[root]+1,r+1) if(mn[col[i]] == i) ++droot;
	Loop(i,l,mn[root]) if(mx[col[i]] == i) ++droot;
	return ans+2*droot;
}

//int main()
//{
//	cout << minimum_walk({0, 2, 3, 1}, 0) << '\n';
//}

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

books.cpp: In function 'll minimum_walk(std::vector<int>, int)':
books.cpp:86:14: warning: 'droot' may be used uninitialized in this function [-Wmaybe-uninitialized]
   86 |  return ans+2*droot;
      |             ~^~~~~~
books.cpp:85:18: warning: 'root' may be used uninitialized in this function [-Wmaybe-uninitialized]
   85 |  Loop(i,l,mn[root]) if(mx[col[i]] == i) ++droot;
      |                  ^

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