oj.uz

Submission #53751

# Submission time Handle Problem Language Result Execution time Memory
53751 2018-07-01T06:37:01 Z 강한육군장홍준(#2037) Islands (IOI08_islands) C++11
90 / 100
 2000 ms 107320 KB 
#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
vector<int>edge[1212121];
long long RD[1212121], D[1212121], X[1212121], Y[1212121], indeg[1212121], SV[1212121], L[1212121], V[1212121];
long long max(long long a, long long b) { if (a < b)return b; return a; }
bool sort_DY(int a, int b) { return D[a] + Y[a] > D[b] + Y[b]; }
long long get_RD(int x) {
	if (edge[x].size() < 2)return 0;
	sort(edge[x].begin(), edge[x].end(), sort_DY);
	return D[edge[x][0]] + D[edge[x][1]] + Y[edge[x][0]] + Y[edge[x][1]];
}
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]]++, edge[X[i]].push_back(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();
		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]);
		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, mx1 = -1e18,mx2 = -1e18;
		while (X[now]) {
			L[++sz] = D[now]; V[sz] = Y[now];
			res = max(res, max(RD[now], get_RD(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++) {
			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;
	}
	printf("%lld", ans);
	return 0;
}

Compilation message

islands.cpp: In function 'int main()':
islands.cpp:16:18: warning: unused variable 'j' [-Wunused-variable]
  long long n, i, j; scanf("%lld", &n);
                  ^
islands.cpp:16: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:17:73: 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]]++, edge[X[i]].push_back(i);
                           ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 28764 KB Output is correct
2 Correct 26 ms 28900 KB Output is correct
3 Correct 25 ms 28976 KB Output is correct
4 Correct 30 ms 28976 KB Output is correct
5 Correct 29 ms 29048 KB Output is correct
6 Correct 26 ms 29048 KB Output is correct
7 Correct 26 ms 29068 KB Output is correct
8 Correct 28 ms 29128 KB Output is correct
9 Correct 25 ms 29128 KB Output is correct
10 Correct 26 ms 29164 KB Output is correct
11 Correct 25 ms 29164 KB Output is correct

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 29172 KB Output is correct
2 Correct 29 ms 29180 KB Output is correct

Subtask #3
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 29264 KB Output is correct
2 Correct 28 ms 29324 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 30108 KB Output is correct
2 Correct 54 ms 31732 KB Output is correct
3 Correct 39 ms 31732 KB Output is correct
4 Correct 31 ms 31732 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 32636 KB Output is correct
2 Correct 71 ms 35460 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 166 ms 41732 KB Output is correct
2 Correct 137 ms 44672 KB Output is correct
3 Correct 176 ms 48168 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 250 ms 53492 KB Output is correct
2 Correct 236 ms 63220 KB Output is correct
3 Correct 224 ms 69288 KB Output is correct
4 Correct 334 ms 77360 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 730 ms 77360 KB Output is correct
2 Correct 768 ms 92252 KB Output is correct
3 Correct 506 ms 92252 KB Output is correct
4 Correct 427 ms 96708 KB Output is correct
5 Correct 452 ms 96708 KB Output is correct
6 Correct 1075 ms 96708 KB Output is correct
7 Correct 467 ms 104004 KB Output is correct

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 545 ms 104004 KB Output is correct
2 Correct 422 ms 104004 KB Output is correct
3 Correct 452 ms 107320 KB Output is correct
4 Execution timed out 2055 ms 107320 KB Time limit exceeded
5 Halted 0 ms 0 KB -