oj.uz

Submission #53778

# Submission time Handle Problem Language Result Execution time Memory
53778 2018-07-01T07:22:22 Z ics0503 Islands (IOI08_islands) C++17
90 / 100
 2000 ms 103548 KB 
#include<iostream>
#include<vector>
using namespace std;
vector<int>edge[1212121];
long long RD[1212121], D[1212121], Y[1212121], SV[1212121], L[1212121], V[1212121];
int X[1212121], indeg[1212121], ck[1212121];
long long max(long long a, long long b) { if (a < b)return b; return a; }
void myassert(int x) {
	if (x == 1e14)return;
	printf("1");
	myassert(x + 1);
}
long long get_RD(int x) { // O(E)
	if (edge[x].size() < 2)return 0;
	long long mx1 = 0, mxw, mx2 = 0;
	for (int &nxt : edge[x])if (mx1 < D[nxt] + Y[nxt])mx1 = D[nxt] + Y[nxt], mxw = nxt;
	for (int &nxt : edge[x])if (nxt != mxw && mx2 < D[nxt] + Y[nxt])mx2 = D[nxt] + Y[nxt];
	return mx1 + mx2;
}
int main() {
	ios_base::sync_with_stdio(false);
	vector<long long>Q;
	long long n, i, j; cin >> n;
	for (i = 1; i <= n; i++) {
		cin >> X[i] >> Y[i], indeg[X[i]]++, edge[X[i]].push_back(i); // E == N
	}
	for (i = 1; i <= n; i++)if (indeg[i] == 0)Q.push_back(i);
	while (!Q.empty()) { // O(N)
		long long now = Q.back(); Q.pop_back();
		if (now == 0)myassert(-10);
		RD[now] = max(RD[now], get_RD(now));
		RD[X[now]] = max(RD[X[now]], RD[now]);
		D[X[now]] = max(D[X[now]], D[now] + Y[now]);
		if (--indeg[X[now]] == 0)Q.push_back(X[now]);
		ck[now] = 1;
	}
	long long ans = 0;
	for (i = 1; i <= n; i++) if (!ck[i]) { // O(N)
		long long now = i, S = 0, sz = 0, res = 0, mx1 = -1e18, mx2 = -1e18;
		while (!ck[now]) { // O(Cyc)
			if (now == 0)myassert(-10);
			L[++sz] = D[now]; V[sz] = Y[now];
			res = max(res, max(RD[now], get_RD(now)));
			S += Y[now];
			ck[now] = 1; now = X[now];
		}
		for (i = 1; i <= sz; i++)SV[i] = SV[i - 1] + V[i]; 
		for (i = 1; i <= sz; i++) {
			res = max(res, max(L[i] + SV[i - 1] + mx1, L[i] + S - SV[i - 1] + mx2));
			mx1 = max(mx1, L[i] - SV[i - 1]);
			mx2 = max(mx2, L[i] + SV[i - 1]);
		}
		ans += res;
	}
	cout << ans;
	return 0;
}

Compilation message

islands.cpp: In function 'int main()':
islands.cpp:23:18: warning: unused variable 'j' [-Wunused-variable]
  long long n, i, j; cin >> n;
                  ^
islands.cpp: In function 'long long int get_RD(int)':
islands.cpp:17:26: warning: 'mxw' may be used uninitialized in this function [-Wmaybe-uninitialized]
  for (int &nxt : edge[x])if (nxt != mxw && mx2 < D[nxt] + Y[nxt])mx2 = D[nxt] + Y[nxt];
                          ^~

Subtask #1
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 28920 KB Output is correct
2 Correct 26 ms 29036 KB Output is correct
3 Correct 26 ms 29036 KB Output is correct
4 Correct 25 ms 29036 KB Output is correct
5 Correct 25 ms 29036 KB Output is correct
6 Correct 26 ms 29036 KB Output is correct
7 Correct 25 ms 29036 KB Output is correct
8 Correct 25 ms 29068 KB Output is correct
9 Correct 26 ms 29068 KB Output is correct
10 Correct 26 ms 29116 KB Output is correct
11 Correct 25 ms 29116 KB Output is correct

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 29116 KB Output is correct
2 Correct 26 ms 29116 KB Output is correct

Subtask #3
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 29240 KB Output is correct
2 Correct 27 ms 29368 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 30012 KB Output is correct
2 Correct 42 ms 31416 KB Output is correct
3 Correct 36 ms 31416 KB Output is correct
4 Correct 29 ms 31416 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 32488 KB Output is correct
2 Correct 62 ms 35028 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 41096 KB Output is correct
2 Correct 111 ms 43752 KB Output is correct
3 Correct 129 ms 47072 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 217 ms 51960 KB Output is correct
2 Correct 244 ms 61404 KB Output is correct
3 Correct 257 ms 66924 KB Output is correct
4 Correct 272 ms 74968 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 314 ms 74968 KB Output is correct
2 Correct 641 ms 90396 KB Output is correct
3 Correct 495 ms 90396 KB Output is correct
4 Correct 400 ms 92888 KB Output is correct
5 Correct 424 ms 92888 KB Output is correct
6 Correct 901 ms 92888 KB Output is correct
7 Correct 470 ms 100056 KB Output is correct

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 414 ms 100056 KB Output is correct
2 Correct 412 ms 100056 KB Output is correct
3 Correct 488 ms 103548 KB Output is correct
4 Execution timed out 2073 ms 103548 KB Time limit exceeded
5 Halted 0 ms 0 KB -