oj.uz

Submission #255367

# Submission time Handle Problem Language Result Execution time Memory
255367 2020-07-31T19:58:54 Z tutis Islands (IOI08_islands) C++17
100 / 100
 518 ms 106008 KB 
/*input
7
3 8
7 2
4 2
1 4
1 9
3 4
2 3
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll ans(vector<pair<ll, ll>> &A)
{
	ll n = A.size() / 2;
	ll mx = 0;
	ll S[2 * n];
	S[0] = 0;
	for (int i = 1; i < 2 * n; i++)
		S[i] = S[i - 1] + A[i - 1].second;
	deque<int>Q;
	for (int j = 0; j < 2 * n; j++)
	{
		while (!Q.empty() && Q.front() <= j - n)
			Q.pop_front();
		if (!Q.empty())
		{
			int i = Q[0];
			mx = max(mx, S[j] + A[j].first + (A[i].first - S[i]));
		}
		while (!Q.empty() && A[Q.back()].first - S[Q.back()] < A[j].first - S[j])
			Q.pop_back();
		Q.push_back(j);
	}
	return mx;
}
int main()
{
	ios_base::sync_with_stdio(false);
	ll N;
	cin >> N;
	ll pa[N + 1];
	ll L[N + 1];
	ll K[N + 1];
	fill_n(K, N + 1, 0ll);
	ll H[N + 1];
	fill_n(H, N + 1, 0ll);
	ll MX[N + 1];
	fill_n(MX, N + 1, 0ll);
	for (ll i = 1; i <= N; i++)
	{
		cin >> pa[i] >> L[i];
		K[pa[i]]++;
	}
	for (ll i = 1; i <= N; i++)
	{
		if (pa[i] != 0)
		{
			ll j = i;
			while (K[j] == 0)
			{
				ll k = pa[j];
				MX[k] = max({MX[j], MX[k], H[k] + H[j] + L[j]});
				H[k] = max(H[k], H[j] + L[j]);
				K[k]--;
				pa[j] = 0;
				j = k;
			}
		}
	}
	ll ret = 0;
	for (ll i = 1; i <= N; i++)
	{
		if (pa[i] != 0)
		{
			ll gal = 0;
			vector<pair<ll, ll>>A;
			ll j = i;
			while (pa[j] != 0)
			{
				gal = max(gal, MX[j]);
				A.push_back({H[j], L[j]});
				ll k = pa[j];
				pa[j] = 0;
				j = k;
			}
			ll s = A.size();
			for (ll j = 0; j < s; j++)
				A.push_back(A[j]);
			ret += max(gal, ans(A));
		}
	}
	cout << ret << "\n";
}

Subtask #1
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 0 ms 384 KB Output is correct
10 Correct 0 ms 384 KB Output is correct
11 Correct 0 ms 384 KB Output is correct

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct

Subtask #3
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 2 ms 640 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1408 KB Output is correct
2 Correct 11 ms 2940 KB Output is correct
3 Correct 7 ms 1536 KB Output is correct
4 Correct 3 ms 896 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 4092 KB Output is correct
2 Correct 30 ms 7312 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 11764 KB Output is correct
2 Correct 71 ms 19216 KB Output is correct
3 Correct 81 ms 22120 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 22420 KB Output is correct
2 Correct 134 ms 35180 KB Output is correct
3 Correct 173 ms 49712 KB Output is correct
4 Correct 213 ms 54620 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 267 ms 55032 KB Output is correct
2 Correct 378 ms 79956 KB Output is correct
3 Correct 308 ms 43644 KB Output is correct
4 Correct 294 ms 68708 KB Output is correct
5 Correct 278 ms 68324 KB Output is correct
6 Correct 518 ms 52856 KB Output is correct
7 Correct 307 ms 87648 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 278 ms 54904 KB Output is correct
2 Correct 268 ms 54908 KB Output is correct
3 Correct 338 ms 106008 KB Output is correct
4 Correct 436 ms 54392 KB Output is correct
5 Correct 285 ms 72240 KB Output is correct
6 Correct 255 ms 56808 KB Output is correct
7 Correct 444 ms 53752 KB Output is correct