oj.uz

Submission #355042

# Submission time Handle Problem Language Result Execution time Memory
355042 2021-01-22T08:27:17 Z amunduzbaev Ancient Books (IOI17_books) C++14
12 / 100
 4 ms 4352 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);
	//assert(n <= 1000);
	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(l[f(i)] != r[f(i)] || i == s)
		vv.pb({{ l[ f(i) ], r[ f(i) ] }, f(i)});
		//cout<<l[f(i)]<<" "<<r[f(i)]<<"\n";
	}
	
	sort(vv.begin(), vv.end(), cmp);
	
	//for(auto x:vv) cout<<x.ff.ff<<" "<<x.ff.ss<<" "<<x.ss<<"\n";
	
	ll tmp = 0;
	
	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);
			tmp += abs(vv[i].ff.ff - vv[i-1].ff.ss) * 2;
		}
	}
	return sum[f(s)] + tmp;
}

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4204 KB Output is correct
2 Correct 3 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 3 ms 4352 KB Output is correct
6 Correct 3 ms 4204 KB Output is correct
7 Correct 4 ms 4204 KB Output is correct
8 Correct 3 ms 4236 KB Output is correct
9 Correct 3 ms 4204 KB Output is correct
10 Correct 3 ms 4204 KB Output is correct
11 Correct 3 ms 4204 KB Output is correct
12 Correct 3 ms 4204 KB Output is correct
13 Correct 3 ms 4204 KB Output is correct
14 Correct 3 ms 4204 KB Output is correct
15 Correct 3 ms 4204 KB Output is correct
16 Correct 2 ms 4204 KB Output is correct
17 Correct 3 ms 4204 KB Output is correct
18 Correct 4 ms 4204 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4204 KB Output is correct
2 Correct 3 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 3 ms 4352 KB Output is correct
6 Correct 3 ms 4204 KB Output is correct
7 Correct 4 ms 4204 KB Output is correct
8 Correct 3 ms 4236 KB Output is correct
9 Correct 3 ms 4204 KB Output is correct
10 Correct 3 ms 4204 KB Output is correct
11 Correct 3 ms 4204 KB Output is correct
12 Correct 3 ms 4204 KB Output is correct
13 Correct 3 ms 4204 KB Output is correct
14 Correct 3 ms 4204 KB Output is correct
15 Correct 3 ms 4204 KB Output is correct
16 Correct 2 ms 4204 KB Output is correct
17 Correct 3 ms 4204 KB Output is correct
18 Correct 4 ms 4204 KB Output is correct
19 Correct 4 ms 4332 KB Output is correct
20 Correct 3 ms 4332 KB Output is correct
21 Correct 4 ms 4332 KB Output is correct
22 Incorrect 4 ms 4332 KB 3rd lines differ - on the 1st token, expected: '2082', found: '2104'
23 Halted 0 ms 0 KB -

Subtask #3
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4204 KB Output is correct
2 Correct 3 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 3 ms 4352 KB Output is correct
6 Correct 3 ms 4204 KB Output is correct
7 Correct 4 ms 4204 KB Output is correct
8 Correct 3 ms 4236 KB Output is correct
9 Correct 3 ms 4204 KB Output is correct
10 Correct 3 ms 4204 KB Output is correct
11 Correct 3 ms 4204 KB Output is correct
12 Correct 3 ms 4204 KB Output is correct
13 Correct 3 ms 4204 KB Output is correct
14 Correct 3 ms 4204 KB Output is correct
15 Correct 3 ms 4204 KB Output is correct
16 Correct 2 ms 4204 KB Output is correct
17 Correct 3 ms 4204 KB Output is correct
18 Correct 4 ms 4204 KB Output is correct
19 Correct 4 ms 4332 KB Output is correct
20 Correct 3 ms 4332 KB Output is correct
21 Correct 4 ms 4332 KB Output is correct
22 Incorrect 4 ms 4332 KB 3rd lines differ - on the 1st token, expected: '2082', found: '2104'
23 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: '4072'
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4204 KB Output is correct
2 Correct 3 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 3 ms 4352 KB Output is correct
6 Correct 3 ms 4204 KB Output is correct
7 Correct 4 ms 4204 KB Output is correct
8 Correct 3 ms 4236 KB Output is correct
9 Correct 3 ms 4204 KB Output is correct
10 Correct 3 ms 4204 KB Output is correct
11 Correct 3 ms 4204 KB Output is correct
12 Correct 3 ms 4204 KB Output is correct
13 Correct 3 ms 4204 KB Output is correct
14 Correct 3 ms 4204 KB Output is correct
15 Correct 3 ms 4204 KB Output is correct
16 Correct 2 ms 4204 KB Output is correct
17 Correct 3 ms 4204 KB Output is correct
18 Correct 4 ms 4204 KB Output is correct
19 Correct 4 ms 4332 KB Output is correct
20 Correct 3 ms 4332 KB Output is correct
21 Correct 4 ms 4332 KB Output is correct
22 Incorrect 4 ms 4332 KB 3rd lines differ - on the 1st token, expected: '2082', found: '2104'
23 Halted 0 ms 0 KB -