oj.uz

Submission #927914

# Submission time Handle Problem Language Result Execution time Memory
927914 2024-02-15T14:02:12 Z TAhmed33 Islands (IOI08_islands) C++
80 / 100
 766 ms 131072 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MAX = 1e6;
int n;
int deg[MAX + 26];
int dp[MAX + 25];
bool vis[MAX + 25];
pair <int, int> nxt[MAX + 25];
vector <pair <int, int>> adj[MAX + 26];
struct Mono {
	int sze = 0;
	stack <pair <int, int>> s1, s2;
	int get_min () {
		if (s1.empty() || s2.empty()) {
			return s1.empty() ? s2.top().second : s1.top().second;
		} else {
			return max(s1.top().second, s2.top().second);
		}
	}
	void insert (int x) {
		int mn = s1.empty() ? x : max(x, s1.top().second);
		s1.push({x, mn});
		sze++;
	}
	void remove () {
		if (s2.empty()) while (!s1.empty()) {
			int x = s1.top().first; s1.pop();
			int mn = (s2.empty() ? x : max(x, s2.top().second));
			s2.push({x, mn});
		}
		s2.pop();
		sze--;
	}
};
int dp2[MAX + 25][2];
int diameter (int x, int t, int par) {
	if (adj[x].empty()) return 0;
	if (adj[x].size() == 1 && par != -1) return 0;
	if (dp2[x][t] != -1) return dp2[x][t];
	int mx1 = 0, mx2 = 0;
	int mx3 = 0;
	for (auto j : adj[x]) {
		if (j.first == par) continue;
		int sum = j.second + diameter(j.first, 0, x);
		if (sum > mx1) {
			mx2 = mx1;
			mx1 = sum;
		} else if (sum > mx2) {
			mx2 = sum;
		}
		mx3 = max(mx3, diameter(j.first, 1, x));
	}
	if (t) return dp2[x][t] = max(mx3, mx1 + mx2);
	return dp2[x][t] = mx1;
}
vector <int> l;
vector <int> l2;
signed main () {
    ios::sync_with_stdio(0);
    cin.tie(0);
    memset(dp2, -1, sizeof(dp2));
	cin >> n;
	for (int i = 1; i <= n; i++) {
		int x, y;
		cin >> x >> y;
		nxt[i] = {x, y};
		deg[x]++;
	}
	queue <int> cur;
	for (int i = 1; i <= n; i++) {
		if (!deg[i]) {
			cur.push(i);
		}
	}
	while (!cur.empty()) {
		int k = cur.front();
		cur.pop();
		auto j = nxt[k];
		dp[j.first] = max(dp[j.first], j.second + dp[k]);
		adj[j.first].push_back({k, j.second});
		adj[k].push_back(j);
		deg[j.first]--;
		if (deg[j.first] == 0) {
			cur.push(j.first);
		}
	}
	int sum = 0;
	for (int i = 1; i <= n; i++) {
		if (!vis[i] && deg[i]) {	
			int cur = i;
			Mono ddd;
			l.clear(); l2.clear();
			int mx2 = diameter(i, 1, -1);
			l.push_back(dp[i]);
			l2.push_back(0);
			vis[i] = 1;
			int cnt = 1;
			while (nxt[cur].first != i) {
				cnt++;
				mx2 = max(mx2, diameter(nxt[cur].first, 1, -1));
				l.push_back(dp[nxt[cur].first]);
				l2.push_back(nxt[cur].second);
				cur = nxt[cur].first;
				vis[cur] = 1;
			}
			l.push_back(dp[nxt[cur].first]);
			l2.push_back(nxt[cur].second);
			cur = nxt[cur].first;
			while (nxt[cur].first != i) {
				l.push_back(dp[nxt[cur].first]);
				l2.push_back(nxt[cur].second);
				cur = nxt[cur].first;
			}
			int xx = l2.size();
			int pref[xx] = {};
			for (int j = 1; j < xx; j++) {
				pref[j] = l2[j] + pref[j - 1];
			}
			ddd.insert(l[0]);
			for (int j = 1; j < xx; j++) {
				mx2 = max(mx2, l[j] + pref[j] + ddd.get_min());
				ddd.insert(l[j] - pref[j]);
				if (ddd.sze >= cnt) {
					ddd.remove();
				}
			}

			sum += mx2;
		}
	}
	cout << sum << '\n';
}

Subtask #1
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 41564 KB Output is correct
2 Correct 10 ms 41648 KB Output is correct
3 Correct 8 ms 41676 KB Output is correct
4 Correct 8 ms 41668 KB Output is correct
5 Correct 8 ms 41564 KB Output is correct
6 Correct 8 ms 41664 KB Output is correct
7 Correct 8 ms 41564 KB Output is correct
8 Correct 8 ms 41560 KB Output is correct
9 Correct 8 ms 41564 KB Output is correct
10 Correct 9 ms 41640 KB Output is correct
11 Correct 9 ms 42072 KB Output is correct

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 41564 KB Output is correct
2 Correct 9 ms 43612 KB Output is correct

Subtask #3
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 43612 KB Output is correct
2 Correct 9 ms 43868 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 44632 KB Output is correct
2 Correct 18 ms 48600 KB Output is correct
3 Correct 15 ms 45404 KB Output is correct
4 Correct 11 ms 44496 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 49868 KB Output is correct
2 Correct 29 ms 51152 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 63432 KB Output is correct
2 Correct 56 ms 60260 KB Output is correct
3 Correct 73 ms 70576 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 75748 KB Output is correct
2 Correct 134 ms 94300 KB Output is correct
3 Correct 119 ms 85988 KB Output is correct
4 Correct 162 ms 116944 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 194 ms 121032 KB Output is correct
2 Correct 419 ms 131072 KB Output is correct
3 Correct 201 ms 107812 KB Output is correct
4 Correct 266 ms 131072 KB Output is correct
5 Correct 259 ms 131072 KB Output is correct
6 Correct 766 ms 131072 KB Output is correct
7 Runtime error 229 ms 131072 KB Execution killed with signal 9
8 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 216 ms 131072 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -