oj.uz

Submission #354982

# Submission time Handle Problem Language Result Execution time Memory
354982 2021-01-22T07:53:35 Z amunduzbaev Ancient Books (IOI17_books) C++14
0 / 100
 3 ms 4332 KB 
#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], 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;
}

ll minimum_walk(vector<int> p, int s) {
	n = sz(p);
	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;
	//cout<<"here";
	for(int i=0;i<n;i++){
		if(used[i]) continue;
		//cout<<i<<" ";
		dfs(i);
		//cout<<"\n";
		if(sum[f(i)] == 0){
			l[f(i)] = (i ? r[f(i-1)] : 0);
		}
		vv.pb({{ l[ f(i) ], r[ f(i) ] }, f(i)});
	}
	
	sort(vv.begin(), vv.end(), cmp);
	
	for(int i=1; i<sz(vv); i++){
		if(vv[i].ff.ff < vv[i-1].ff.ss) merge(vv[i].ss, vv[i-1].ss); 
		else{
			int a = vv[i].ss, b = vv[i-1].ss;
			merge(a, b);
			sum[f(a)] += (vv[i].ff.ff - vv[i-1].ff.ss) * 2;
		}
	}
	return sum[f(s)];
}

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4204 KB Output is correct
2 Correct 2 ms 4204 KB Output is correct
3 Correct 3 ms 4204 KB Output is correct
4 Correct 3 ms 4204 KB Output is correct
5 Correct 2 ms 4204 KB Output is correct
6 Correct 3 ms 4204 KB Output is correct
7 Correct 2 ms 4204 KB Output is correct
8 Correct 3 ms 4204 KB Output is correct
9 Incorrect 3 ms 4204 KB 3rd lines differ - on the 1st token, expected: '0', found: '2'
10 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4204 KB Output is correct
2 Correct 2 ms 4204 KB Output is correct
3 Correct 3 ms 4204 KB Output is correct
4 Correct 3 ms 4204 KB Output is correct
5 Correct 2 ms 4204 KB Output is correct
6 Correct 3 ms 4204 KB Output is correct
7 Correct 2 ms 4204 KB Output is correct
8 Correct 3 ms 4204 KB Output is correct
9 Incorrect 3 ms 4204 KB 3rd lines differ - on the 1st token, expected: '0', found: '2'
10 Halted 0 ms 0 KB -

Subtask #3
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4204 KB Output is correct
2 Correct 2 ms 4204 KB Output is correct
3 Correct 3 ms 4204 KB Output is correct
4 Correct 3 ms 4204 KB Output is correct
5 Correct 2 ms 4204 KB Output is correct
6 Correct 3 ms 4204 KB Output is correct
7 Correct 2 ms 4204 KB Output is correct
8 Correct 3 ms 4204 KB Output is correct
9 Incorrect 3 ms 4204 KB 3rd lines differ - on the 1st token, expected: '0', found: '2'
10 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

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

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4204 KB Output is correct
2 Correct 2 ms 4204 KB Output is correct
3 Correct 3 ms 4204 KB Output is correct
4 Correct 3 ms 4204 KB Output is correct
5 Correct 2 ms 4204 KB Output is correct
6 Correct 3 ms 4204 KB Output is correct
7 Correct 2 ms 4204 KB Output is correct
8 Correct 3 ms 4204 KB Output is correct
9 Incorrect 3 ms 4204 KB 3rd lines differ - on the 1st token, expected: '0', found: '2'
10 Halted 0 ms 0 KB -