답안 #53799 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
53799	2018-07-01T08:13:13 Z	ics0503	Islands (IOI08_islands)	C++17	77 / 100	1716 ms	222676 KB

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.0 / 33.0

#	결과	실행 시간	메모리	Grader output
1	Correct	22 ms	23928 KB	Output is correct
2	Incorrect	26 ms	24004 KB	Output isn't correct
3	Correct	25 ms	24096 KB	Output is correct
4	Correct	24 ms	24144 KB	Output is correct
5	Correct	22 ms	24144 KB	Output is correct
6	Correct	23 ms	24144 KB	Output is correct
7	Correct	23 ms	24144 KB	Output is correct
8	Correct	23 ms	24156 KB	Output is correct
9	Correct	22 ms	24160 KB	Output is correct
10	Correct	21 ms	24160 KB	Output is correct
11	Correct	22 ms	24160 KB	Output is correct

Subtask #2
3.0 / 3.0

#	결과	실행 시간	메모리	Grader output
1	Correct	25 ms	24228 KB	Output is correct
2	Correct	24 ms	24228 KB	Output is correct

Subtask #3
4.0 / 4.0

#	결과	실행 시간	메모리	Grader output
1	Correct	23 ms	24228 KB	Output is correct
2	Correct	30 ms	24740 KB	Output is correct

Subtask #4
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	31 ms	25640 KB	Output is correct
2	Correct	47 ms	29132 KB	Output is correct
3	Correct	40 ms	29132 KB	Output is correct
4	Correct	32 ms	29132 KB	Output is correct

Subtask #5
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	63 ms	31076 KB	Output is correct
2	Correct	96 ms	34788 KB	Output is correct

Subtask #6
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	159 ms	44876 KB	Output is correct
2	Correct	166 ms	51948 KB	Output is correct
3	Correct	231 ms	64320 KB	Output is correct

Subtask #7
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	238 ms	64320 KB	Output is correct
2	Correct	358 ms	93280 KB	Output is correct
3	Correct	437 ms	103500 KB	Output is correct
4	Correct	404 ms	127820 KB	Output is correct

Subtask #8
0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	450 ms	127820 KB	Output is correct
2	Correct	1450 ms	176264 KB	Output is correct
3	Correct	423 ms	176264 KB	Output is correct
4	Correct	632 ms	176264 KB	Output is correct
5	Correct	623 ms	176264 KB	Output is correct
6	Incorrect	1615 ms	176264 KB	Output isn't correct
7	Halted	0 ms	0 KB	-

Subtask #9
0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	611 ms	176264 KB	Output is correct
2	Correct	636 ms	176264 KB	Output is correct
3	Correct	828 ms	222676 KB	Output is correct
4	Correct	485 ms	222676 KB	Output is correct
5	Correct	600 ms	222676 KB	Output is correct
6	Correct	523 ms	222676 KB	Output is correct
7	Incorrect	1716 ms	222676 KB	Output isn't correct

답안 #53799

Compilation message