Submission #100670

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
100670	2019-03-13T06:32:33 Z	cki86201	Mountain Trek Route (IZhO12_route)	C++11	100 / 100	310 ms	29544 KB

route

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#include <math.h>
#include <assert.h>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <algorithm>
#include <iostream>
#include <functional>
#include <unordered_set>
#include <bitset>
#include <time.h>
#include <limits.h>

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define Fi first
#define Se second
#define pb(x) push_back(x)
#define szz(x) (int)x.size()
#define rep(i,n) for(int i=0;i<n;i++)
#define all(x) x.begin(),x.end()
typedef tuple<int, int, int> t3;

int N, K;
int A[1000010];
int p[1000010]; int Find(int x) { return p[x] == x ? x : p[x] = Find(p[x]); }
int li[1000010], ri[1000010], z[1000010];
priority_queue <pii, vector<pii>, greater<pii> > pq;
inline int nxt_i(int i) { return i==N-1 ? 0 : i+1; }
inline int pre_i(int i) { return i==0 ? N-1 : i-1; }

int main() {
	scanf("%d%d", &N, &K);
	rep(i, N) scanf("%d", A + i);
	rep(i, N) li[i] = pre_i(i), ri[i] = nxt_i(i);
	rep(i, N) p[i] = i, z[i] = 1;
	rep(i, N) {
		int j = nxt_i(i);
		if(A[i] != A[j]) continue;
		int pi = Find(i), pj = Find(j);
		if(pi != pj) {
			p[pi] = pj; li[pj] = li[pi];
			z[pj] += z[pi];
		}
	}
	rep(i, N) if(p[i] == i) {
		if(A[i] < A[li[i]] && A[i] < A[ri[i]]) pq.push(pii(z[i], i));
	}
	ll ans = 0;
	while(!pq.empty()) {
		pii t = pq.top(); pq.pop();
		int x = t.Se;
		int mul = min(A[Find(li[x])], A[Find(ri[x])]) - A[x];
		if((ll)mul * t.Fi >= K) {
			ans += 2 * (K / t.Fi);
			break;
		}
		ans += 2 * mul;
		K -= t.Fi * mul;
		A[x] += mul;
		if(A[x] == A[Find(li[x])]) {
			int pi = Find(li[x]), pj = Find(x);
			if(pi != pj) {
				p[pi] = pj; li[pj] = li[pi];
				z[pj] += z[pi];
			}
		}
		if(A[x] == A[Find(ri[x])]) {
			int pi = Find(x), pj = Find(ri[x]);
			if(pi != pj) {
				p[pi] = pj; li[pj] = li[pi];
				z[pj] += z[pi];
			}
		}
		x = Find(x);
		if(A[x] < A[Find(li[x])] && A[x] < A[Find(ri[x])]) pq.push(pii(z[x], x));
	}
	printf("%lld\n", ans);
	return 0;
}

Compilation message

route.cpp: In function 'int main()':
route.cpp:41:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &N, &K);
  ~~~~~^~~~~~~~~~~~~~~~
route.cpp:42:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  rep(i, N) scanf("%d", A + i);
            ~~~~~^~~~~~~~~~~~~

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	384 KB	Output is correct
2	Correct	2 ms	384 KB	Output is correct
3	Correct	2 ms	384 KB	Output is correct
4	Correct	3 ms	384 KB	Output is correct
5	Correct	2 ms	384 KB	Output is correct
6	Correct	2 ms	384 KB	Output is correct
7	Correct	2 ms	384 KB	Output is correct
8	Correct	3 ms	432 KB	Output is correct
9	Correct	3 ms	384 KB	Output is correct
10	Correct	23 ms	3160 KB	Output is correct
11	Correct	28 ms	4084 KB	Output is correct
12	Correct	21 ms	4020 KB	Output is correct
13	Correct	186 ms	29432 KB	Output is correct
14	Correct	310 ms	29544 KB	Output is correct
15	Correct	227 ms	27552 KB	Output is correct
16	Correct	153 ms	28536 KB	Output is correct
17	Correct	147 ms	28536 KB	Output is correct
18	Correct	177 ms	29356 KB	Output is correct
19	Correct	184 ms	29432 KB	Output is correct
20	Correct	136 ms	25848 KB	Output is correct