Submission #355093

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
355093	2021-01-22T09:02:50 Z	amunduzbaev	Ancient Books (IOI17_books)	C++14	22 / 100	143 ms	16364 KB

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], 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)});
	}
	
	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++){
		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);
	}
	
	return sum[f(s)] + tmp;
}

Subtask #1
12.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	2 ms	4204 KB	Output is correct
4	Correct	2 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	3 ms	4204 KB	Output is correct
8	Correct	3 ms	4204 KB	Output is correct
9	Correct	2 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	2 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	2 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	2 ms	4204 KB	Output is correct

Subtask #2
10.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	2 ms	4204 KB	Output is correct
4	Correct	2 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	3 ms	4204 KB	Output is correct
8	Correct	3 ms	4204 KB	Output is correct
9	Correct	2 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	2 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	2 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	2 ms	4204 KB	Output is correct
19	Correct	3 ms	4332 KB	Output is correct
20	Correct	3 ms	4332 KB	Output is correct
21	Correct	3 ms	4332 KB	Output is correct
22	Correct	3 ms	4332 KB	Output is correct
23	Correct	3 ms	4332 KB	Output is correct
24	Correct	3 ms	4332 KB	Output is correct
25	Correct	3 ms	4332 KB	Output is correct
26	Correct	3 ms	4332 KB	Output is correct
27	Correct	3 ms	4352 KB	Output is correct
28	Correct	3 ms	4332 KB	Output is correct
29	Correct	4 ms	4332 KB	Output is correct

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	2 ms	4204 KB	Output is correct
4	Correct	2 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	3 ms	4204 KB	Output is correct
8	Correct	3 ms	4204 KB	Output is correct
9	Correct	2 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	2 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	2 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	2 ms	4204 KB	Output is correct
19	Correct	3 ms	4332 KB	Output is correct
20	Correct	3 ms	4332 KB	Output is correct
21	Correct	3 ms	4332 KB	Output is correct
22	Correct	3 ms	4332 KB	Output is correct
23	Correct	3 ms	4332 KB	Output is correct
24	Correct	3 ms	4332 KB	Output is correct
25	Correct	3 ms	4332 KB	Output is correct
26	Correct	3 ms	4332 KB	Output is correct
27	Correct	3 ms	4352 KB	Output is correct
28	Correct	3 ms	4332 KB	Output is correct
29	Correct	4 ms	4332 KB	Output is correct
30	Runtime error	143 ms	16364 KB	Execution killed with signal 6
31	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: '2744'
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	2 ms	4204 KB	Output is correct
4	Correct	2 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	3 ms	4204 KB	Output is correct
8	Correct	3 ms	4204 KB	Output is correct
9	Correct	2 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	2 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	2 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	2 ms	4204 KB	Output is correct
19	Correct	3 ms	4332 KB	Output is correct
20	Correct	3 ms	4332 KB	Output is correct
21	Correct	3 ms	4332 KB	Output is correct
22	Correct	3 ms	4332 KB	Output is correct
23	Correct	3 ms	4332 KB	Output is correct
24	Correct	3 ms	4332 KB	Output is correct
25	Correct	3 ms	4332 KB	Output is correct
26	Correct	3 ms	4332 KB	Output is correct
27	Correct	3 ms	4352 KB	Output is correct
28	Correct	3 ms	4332 KB	Output is correct
29	Correct	4 ms	4332 KB	Output is correct
30	Runtime error	143 ms	16364 KB	Execution killed with signal 6
31	Halted	0 ms	0 KB	-

Submission #355093

Compilation message

Subtask #1 12.0 / 12.0

Subtask #2 10.0 / 10.0

Subtask #3 0 / 28.0

Subtask #4 0 / 20.0

Subtask #5 0 / 30.0

Subtask #1
12.0 / 12.0

Subtask #2
10.0 / 10.0

Subtask #3
0 / 28.0

Subtask #4
0 / 20.0

Subtask #5
0 / 30.0