Submission #885654

#	Time	Username	Problem	Language	Result	Execution time	Memory
885654		Tob	Islands (IOI08_islands)	C++14	90 / 100	547 ms	131072 KiB

islands

#include <bits/stdc++.h>

#define ll long long
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define pb push_back
#define FIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)

using namespace std;

typedef pair <ll, ll> pii;

const ll N = 1e6 + 7, inf = 1e18;

ll n, ro, sp, res, R;
ll a[N], b[N], dp[N], dis[N];
int bio[N], cyc[N];
vector <pii> adj[N];

void Merge(pii& x, ll y) {
	if (y >= x.F) x = {y, x.F};
	else x = {x.F, max(x.S, y)};
}

void dfs(int x) {
	pii p1 = {0, 0};
	for (auto y : adj[x]) {
		if (cyc[y.F]) continue;
		dfs(y.F);
		Merge(p1, dp[y.F] + y.S);
	}
	dp[x] = p1.F;
	res = max(res, p1.F + p1.S);
}

int main () {
	FIO;
	cin >> n;
	
	for (int i = 1; i <= n; i++) {
		cin >> a[i] >> b[i];
		adj[a[i]].pb({i, b[i]});
	}
	
	ll sum = 0;
	for (int i = 1; i <= n; i++) {
		if (bio[i]) continue;
		int x = a[i], y = i;
		bio[i] = i;
		while (!bio[x]) {
			bio[x] = i;
			y = x;
			x = a[x];
		}
		if (bio[x] == i) {
			res = 0;
			cyc[y] = 1;
			vector <int> v; v = {0, y};
			while (x != y) {
				v.pb(x);
				cyc[x] = 1;
				x = a[x];
			}
			int siz = v.size();
			vector <ll> dis(siz+1, 0), rdis(siz+1, 0);
			vector <ll> pr(siz+1, -inf), suf(siz+1, -inf), pr2(siz+1, -inf), suf2(siz+1, -inf);
			ll suma = 0;
			for (int i = 1; i < siz; i++) {
				dfs(v[i]);
				dis[i] = dis[i-1] + b[v[i-1]];
			}
			for (int i = siz-1; i; i--) rdis[i] = rdis[i+1] + (i < siz-1)*b[v[i]];
			for (int i = 1; i < siz; i++) {
				pr[i] = max(pr[i-1], dp[v[i]] + dis[i]);
				pr2[i] = max(pr2[i-1], dp[v[i]] + rdis[i]);
			}
			for (int i = siz-1; i; i--) {
				suf[i] = max(suf[i+1], dp[v[i]] + dis[i]);
				suf2[i] = max(suf2[i+1], dp[v[i]] + rdis[i]);				
			}
			for (int i = 1; i < siz; i++) {
//				cout << i << "i " << v[i] << "x " << dis[i] << "d " << rdis[i] << "rd " << pr[i] << "p " << pr2[i] << "pp " << suf[i] << "s " << suf2[i] << "ss " << dp[v[i]] << "dp\n";
				res = max(res, dp[v[i]] + max(suf[i+1] - dis[i], pr[i-1] + rdis[i] + b[v.back()]));
				res = max(res, dp[v[i]] + max(pr2[i-1] - rdis[i], suf2[i+1] + dis[i] + b[v.back()]));
			}
			sum += res;
		}
	}
	
	cout << sum;

	return 0;
}

Compilation message (stderr)

islands.cpp: In function 'int main()':
islands.cpp:68:7: warning: unused variable 'suma' [-Wunused-variable]
   68 |    ll suma = 0;
      |       ^~~~

• Subtask 1: 33 / 33
• Subtask 2: 3 / 3
• Subtask 3: 4 / 4
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 0 / 10