oj.uz

Submission #53732

# Submission time Handle Problem Language Result Execution time Memory
53732 2018-07-01T06:09:01 Z 강한육군장홍준(#2037) Islands (IOI08_islands) C++11
44 / 100
 2000 ms 31964 KB 
#include<stdio.h>
#include<vector>
using namespace std;
long long indeg[1212121], ck[1212121], D[1212121], X[1212121], Y[1212121];
long long SV[1212121], L[1212121], V[1212121];
long long max(long long a, long long b) { if (a < b)return b; return a; }
int main() {
	vector<long long>Q;
	long long n, i, j; scanf("%lld", &n);
	for (i = 1; i <= n; i++) scanf("%lld%lld", &X[i], &Y[i]), indeg[X[i]]++;
	for (i = 1; i <= n; i++)if (indeg[i] == 0)Q.push_back(i);
	while (!Q.empty()) {
		long long now = Q.back(); Q.pop_back();
		D[X[now]] = max(D[X[now]], D[now] + Y[now]);
		if (--indeg[X[now]] == 0)Q.push_back(X[now]);
		X[now] = 0;
	}
	long long ans = 0;
	for (i = 1; i <= n; i++) if(X[i]){
		long long now = i, S = 0, sz = 0, res = 0;
		while (X[now]) {
			L[++sz] = D[now]; V[sz] = Y[now];
			S += Y[now];
			long long tmp = now; now = X[now]; X[tmp] = 0;
		}
		for (i = 1; i <= sz; i++)SV[i] = SV[i - 1] + V[i];
		for (i = 1; i <= sz; i++) {
			for (j = i + 1; j <= sz; j++) {
				res = max(res, L[i] + L[j] + max(SV[j-1]-SV[i-1], S - (SV[j-1] - SV[i-1])));
			}
		}
		ans += res;
	}
	printf("%lld", ans);
	return 0;
}

Compilation message

islands.cpp: In function 'int main()':
islands.cpp:9:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  long long n, i, j; scanf("%lld", &n);
                     ~~~~~^~~~~~~~~~~~
islands.cpp:10:58: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for (i = 1; i <= n; i++) scanf("%lld%lld", &X[i], &Y[i]), indeg[X[i]]++;
                           ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~

Subtask #1
27.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 380 KB Output is correct
2 Incorrect 2 ms 580 KB Output isn't correct
3 Correct 3 ms 580 KB Output is correct
4 Correct 2 ms 580 KB Output is correct
5 Correct 2 ms 580 KB Output is correct
6 Correct 2 ms 580 KB Output is correct
7 Correct 2 ms 580 KB Output is correct
8 Correct 2 ms 580 KB Output is correct
9 Correct 2 ms 580 KB Output is correct
10 Incorrect 2 ms 652 KB Output isn't correct
11 Correct 2 ms 652 KB Output is correct

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 652 KB Output is correct
2 Correct 3 ms 652 KB Output is correct

Subtask #3
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 652 KB Output is correct
2 Correct 13 ms 760 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 1272 KB Output is correct
2 Correct 213 ms 2292 KB Output is correct
3 Correct 11 ms 2292 KB Output is correct
4 Incorrect 10 ms 2292 KB Output isn't correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 366 ms 2932 KB Output is correct
2 Correct 510 ms 4336 KB Output is correct

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 391 ms 8168 KB Output is correct
2 Execution timed out 2059 ms 8568 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1345 ms 14124 KB Output is correct
2 Execution timed out 2068 ms 23012 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 322 ms 24740 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 364 ms 31868 KB Output is correct
2 Incorrect 464 ms 31964 KB Output isn't correct
3 Halted 0 ms 0 KB -