oj.uz

Submission #53799

# Submission time Handle Problem Language Result Execution time Memory
53799 2018-07-01T08:13:13 Z ics0503 Islands (IOI08_islands) C++17
77 / 100
 1716 ms 222676 KB 
#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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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