oj.uz

Submission #885690

# Submission time Handle Problem Language Result Execution time Memory
885690 2023-12-10T13:12:35 Z Tob Islands (IOI08_islands) C++14
70 / 100
 299 ms 95056 KB 
#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 <int, int> pii;
typedef pair <ll, ll> pll;

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

ll n, res;
int a[N], b[N], bio[N], cyc[N], deg[N];
ll dp[N], re[N];
pll cur[N];
queue <int> q;

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

int main () {
	FIO;
	cin >> n;
	
	for (int i = 1; i <= n; i++) {
		cin >> a[i] >> b[i];
		deg[a[i]]++;
	}
	
	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) {
			cyc[y] = 1;
			while (x != y) {
				cyc[x] = 1;
				x = a[x];
			}
		}
	}
	memset(bio, 0, sizeof bio);
	for (int i = 1; i <= n; i++) if (!deg[i]) q.push(i);
	while (!q.empty()) {
		int x = q.front();
		q.pop();
		pii y = {a[x], b[x]};
		re[y.F] = max(re[y.F], cur[x].F + cur[x].S);
		dp[x] = cur[x].F;
		Merge(cur[y.F], dp[x] + y.S);
		if (cyc[y.F]) continue;
		deg[y.F]--;
		if (!deg[y.F]) q.push(y.F);
	}
	
	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;
			vector <int> v; v = {0, y};
			while (x != y) {
				v.pb(x);
				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);
			
			for (int i = 1; i < siz; i++) {
				dp[v[i]] = cur[v[i]].F;
				res = max(res, re[v[i]]);
				res = max(res, cur[v[i]].F + cur[v[i]].S);
				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;
}

Subtask #1
33.0 / 33.0

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

Subtask #2
3.0 / 3.0

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

Subtask #3
4.0 / 4.0

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

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 13404 KB Output is correct
2 Correct 10 ms 14684 KB Output is correct
3 Correct 7 ms 13404 KB Output is correct
4 Incorrect 4 ms 13148 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 15584 KB Output is correct
2 Correct 18 ms 18240 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 26452 KB Output is correct
2 Correct 36 ms 26484 KB Output is correct
3 Correct 48 ms 34888 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 30288 KB Output is correct
2 Correct 88 ms 48944 KB Output is correct
3 Correct 92 ms 42808 KB Output is correct
4 Correct 118 ms 64332 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 144 ms 37076 KB Output is correct
2 Correct 211 ms 73808 KB Output is correct
3 Correct 172 ms 51024 KB Output is correct
4 Correct 177 ms 74436 KB Output is correct
5 Correct 181 ms 74928 KB Output is correct
6 Incorrect 256 ms 58444 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 157 ms 56992 KB Output is correct
2 Correct 176 ms 57168 KB Output is correct
3 Correct 201 ms 95056 KB Output is correct
4 Correct 230 ms 43364 KB Output is correct
5 Correct 180 ms 80716 KB Output is correct
6 Correct 167 ms 68172 KB Output is correct
7 Incorrect 299 ms 66904 KB Output isn't correct
8 Halted 0 ms 0 KB -