제출 #355319

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
355319		amunduzbaev	Ancient Books (IOI17_books)	C++14	0 / 100	3 ms	4332 KiB

books

#include "books.h"
 
#include "bits/stdc++.h"
using namespace std;
#ifndef EVAL
#include "grader.cpp"
#endif
 
#define ll long long
#define sz(x) (int)x.size()
#define pb push_back
#define pii pair<int, int>
#define ff first
#define ss second
 
const int N = 1e6+5;
const int mod = 1e9+7;
 
int n, sz;
int par[N], ss, nearest, used[N], pp[N], l[N], r[N];
ll sum[N];
 
int f(int x){
	if(par[x] == x) return x;
	return par[x] = f(par[x]);
}
 
void merge(int a, int b){
	a = f(a), b = f(b);
	if(a == b) return;
	l[a] = min(l[b], l[a]);
	r[a] = max(r[a], r[b]);
	par[b] = a;
	sum[a] += sum[b];
}
 
void dfs(int u){
	//cout<<u<<" ";
	if(used[u]) return;
	used[u] = 1;
	l[f(u)] = min(l[f(u)], pp[u]);
	r[f(u)] = max(r[f(u)], pp[u]);
	par[pp[u]] = f(u);
	//cout<<sum[f(u)]<<" ";
	sum[f(u)] += abs(pp[u] - u);
	//cout<<sum[f(u)]<<"\n";
	dfs(pp[u]);
}
 
bool cmp(pair<pii, int> A, pair<pii, int> B){
	pii a = A.ff, b = B.ff;
	if(a.ff != b.ff) return a.ff < b.ff;
	return a.ss > b.ss;
}

/*

8 5
0 1 7 3 4 5 6 2

4 0
0 2 3 1

4 0
3 2 0 1

3 0
2 0 1

*/

ll minimum_walk(vector<int> p, int s) {
	n = sz(p);
	nearest = -mod;
	memset(used, 0, sizeof used);
	for(int i=0;i<n;i++){
		par[i] = i, sum[i] = 0, l[i] = i, r[i] = i;
	}
	
	for(int i=0;i<n;i++) pp[i] = p[i];
	vector<pair<pii, int>>  vv;
	ss = s;
	int ans;
	for(int i=s;i<n;i++){
		if(used[i]) continue;
		dfs(i);
		if(l[f(i)] != r[f(i)]) vv.pb({{ l[ f(i) ], r[ f(i) ] }, f(i)});
		if(l[f(i)] != r[f(i)]){
			int u = i, tt = i;
			if(abs(nearest - s) > abs(u - s)) nearest = u;
			u = pp[u];
			while(tt != u){
				if(abs(nearest - s) > abs(u - s)) nearest = u;
				u = pp[u];
			}
		}
		ans = i;
	}
	sort(vv.begin(), vv.end(), cmp);
	ll tmp = 0;
	for(int i=1; i<sz(vv); i++){
		int a = vv[i].ss, b = vv[i-1].ss;
		tmp += max((vv[i].ff.ff - vv[i-1].ff.ss) * 2, 0);
		vv[i].ff.ss = max(vv[i].ff.ss, vv[i-1].ff.ss);
		merge(a, b);
		ans = a;
	}
	
	return sum[f(ans)] + tmp + abs(nearest - s)*2;
}

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

books.cpp: In function 'long long int minimum_walk(std::vector<int>, int)':
books.cpp:24:10: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
   24 |  if(par[x] == x) return x;
      |     ~~~~~^
books.cpp:83:6: note: 'ans' was declared here
   83 |  int ans;
      |      ^~~

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