Submission #927914

#	Time	Username	Problem	Language	Result	Execution time	Memory
927914		TAhmed33	Islands (IOI08_islands)	C++98	80 / 100	766 ms	131072 KiB

islands

#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 / 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: 0 / 10
• Subtask 9: 0 / 10