oj.uz

Submission #797429

# Submission time Handle Problem Language Result Execution time Memory
797429 2023-07-29T11:14:53 Z firewater Ancient Books (IOI17_books) C++14
0 / 100
 2 ms 468 KB 
#include "books.h"
#include <cstdio>
#include <vector>
#include <cassert>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long
#define N 1010
#define mp make_pair
#define fs first
#define sn second
using namespace std;

int n,m,w,x,y,s,ans,to[N],p[N],mx[N],mi[N],fa[N],fr[N];
pair<int,pair<int,int> >l[N*N];
void dfs(int x)
{
	if(p[x])return;
	p[x]=1;

	fr[x]=w;
	mx[w]=max(mx[w],x);
	mi[w]=min(mi[w],x);
	ans+=abs(x-to[x]);
	dfs(to[x]);
	return;
}
int find(int x)
{
	return (fa[x]==x?x:fa[x]=find(fa[x]));
}
long long minimum_walk(std::vector<int> too, int ss) {
	n=too.size();
	for(int i=1;i<=n;++i)
		to[i]=too[i-1]+1;
	s=ss+1;

	w=m=0;
	for(int i=1;i<=n;++i)
		if(!p[i]&&to[i]!=i){
			++w;
			mi[w]=1001000;
			mx[w]=0;
			dfs(i);
		}
	for(int i=1;i<=w;++i)
		for(int j=i+1;j<=w;++j){
			if(mi[i]<=mx[j]&&mi[j]<=mx[i])l[++m]=mp(0,mp(i,j));
			else l[++m]=mp(min(abs(mi[i]-mx[j]),abs(mi[j]-mx[i]))*2,mp(i,j));
		}
	w++;
	for(int i=1;i<=n;++i)
		if(to[i]!=i)
			l[++m]=mp(abs(s-i),mp(w,fr[i]));
	sort(l+1,l+1+m);
	for(int i=1;i<=w;++i)
		fa[i]=i;
	for(int i=1;i<=m;++i){
		x=l[i].sn.fs;
		y=l[i].sn.sn;
		x=find(x);
		y=find(y);
		if(x==y)continue;
		ans+=l[i].fs;
		fa[x]=y;
	}
	return ans;
}

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB 3rd lines differ - on the 1st token, expected: '6', found: '5'
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB 3rd lines differ - on the 1st token, expected: '6', found: '5'
2 Halted 0 ms 0 KB -

Subtask #3
0 / 28.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB 3rd lines differ - on the 1st token, expected: '6', found: '5'
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 468 KB 3rd lines differ - on the 1st token, expected: '3304', found: '2744'
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB 3rd lines differ - on the 1st token, expected: '6', found: '5'
2 Halted 0 ms 0 KB -