Submission #53799

#	Time	Username	Problem	Language	Result	Execution time	Memory
53799		ics0503	Islands (IOI08_islands)	C++17	77 / 100	1716 ms	222676 KiB

islands

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<long long , ll> pil;
const long long MX = 1000010;
const ll inf = 2e17;

long long n, A[MX], C[MX];
vector<pil> G[MX];
bool done[MX];

ll D[MX];

bool vis[MX];

// list all vertices
void dfs1(long long v, vector<long long > &V) {
	done[v] = true;
	V.push_back(v);
	for (pil &e : G[v]) {
		long long x = e.first;
		if (done[x]) continue;
		dfs1(x, V);
	}
}

// find cycle 
long long found = -1;
long long dep[MX], now;
void dfs2(long long v, long long p, vector<long long > &V) {
	dep[v] = ++now;
	for (pil &e : G[v]) {
		long long x; ll c; tie(x, c) = e;
		if (p == x) continue;
		if (dep[x] >= 0)
			found = x;
		else
			dfs2(x, v, V);
		if (found >= 0) {
			if (dep[v] >= dep[found]) V.push_back(v);
			return;
		}
	}
	--now;
}

// farthest point
ll dist[MX];
long long dfs3(long long v) {
	long long res = v;
	for (pil &e : G[v]) {
		long long x; ll c; tie(x, c) = e;
		if (dist[x] >= 0) continue;
		dist[x] = dist[v] + c;
		long long y = dfs3(x);
		if (dist[y]>dist[res]) res = y;
	}
	return res;
}
ll solve_tree(vector<long long > &V) {
	long long s = V[0];

	for (long long v : V) dist[v] = -1;
	dist[s] = 0;
	long long u = dfs3(s);

	for (long long v : V) dist[v] = -1;
	dist[u] = 0;
	long long v = dfs3(u);

	return dist[v];
}

bool incyc[MX];
ll arm[MX];
// longest path from v in cyc
void dfs4(long long v) {
	arm[v] = 0;
	for (pil &e : G[v]) {
		long long x; ll c; tie(x, c) = e;
		if (incyc[x] || arm[x] >= 0) continue;
		dfs4(x);
		arm[v] = max(arm[v], arm[x] + c);
	}
}

ll Val[2 * MX], Len[2 * MX], Sum[2 * MX];

vector<long long > V, cyc;
ll solve(long long s) {
	// cout<<"\nSOLVE ON "<<s<<'\n';
	V.clear(), cyc.clear();
	dfs1(s, V);

	found = -1, now = 0;
	for (long long v : V) dep[v] = -1;
	dfs2(s, -1, cyc);

	if (cyc.empty())
		return solve_tree(V);

	for (long long v : V) arm[v] = -1;
	for (long long v : cyc) incyc[v] = true, arm[v] = 0;
	for (long long v : cyc) dfs4(v);

	long long sz = cyc.size();
	Sum[0] = 0;
	for (long long i = 0; i<sz; i++) {
		long long v = cyc[i];
		Val[i] = arm[v];
		long long nxt = cyc[(i + 1) % sz];
		for (pil &e : G[v])
			if (e.first == nxt) Len[i] = e.second;
		Sum[i + 1] = Sum[i] + Len[i];
	}
	for (long long i = sz; i<2 * sz; i++)
		Sum[i] = Sum[i%sz] + Sum[sz];
	ll res = 0;
	deque<long long > Q;
	for (long long j = 0; j <= 2 * sz - 1; j++) {
		long long i = j%sz;
		while (!Q.empty() && Q.front() <= j - sz) Q.pop_front();
		if (!Q.empty()) {
			long long x = Q.front();
			ll now = Val[x%sz] + Val[i] + Sum[j] - Sum[x];
			res = max(res, now);
		}
		while (!Q.empty()) {
			long long x = Q.back();
			ll a = Val[x%sz] - Sum[x];
			ll b = Val[j%sz] - Sum[j];
			if (a <= b) Q.pop_back();
			else break;
		}
		Q.push_back(j);
	}
	return res;
	for (long long i = 0; i<sz; i++)
		for (long long j = i + 1; j<sz; j++) {
			ll dist = max(Sum[j] - Sum[i], Sum[sz] + Sum[i] - Sum[j]);
			ll now = dist + Val[i] + Val[j];

			// printf("%d - %d : %lld (%lld)\n", cyc[i], cyc[j], now, dist);
			res = max(res, now);
		}
	return res;
}

int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	cin >> n;
	for (long long u = 1; u <= n; u++) {
		long long v, c; cin >> v >> c;
		A[u] = v, C[u] = c;
		if (v<u && A[v] == u) {
			C[u] = max(C[u], C[v]);
			C[v] = -1;
		}
	}
	for (long long i = 1; i <= n; i++) {
		if (C[i]<0) continue;
		G[i].push_back({ A[i], C[i] });
		G[A[i]].push_back({ i, C[i] });
	}
	ll ans = 0;
	for (long long i = 1; i <= n; i++) {
		if (done[i]) continue;
		ans += solve(i);
	}
	cout << ans;
	return 0;
}

• Subtask 1: 30 / 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