oj.uz

Submission #53737

# Submission time Handle Problem Language Result Execution time Memory
53737 2018-07-01T06:13:09 Z 김세빈(#1437) Islands (IOI08_islands) C++11
100 / 100
 1048 ms 133820 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

vector <ll> V[1010101], S;
ll P[1010101], L[1010101];
ll K[1010101], D[1010101], X[1010101];
ll chk[1010101];
ll n, ans, rt, c;

ll dfs(ll p)
{
	ll i, m1, m2, k;
	m1 = m2 = 0;
	
	chk[p] = 1;
	
	for(i=0;i<V[p].size();i++){
		if(!chk[V[p][i]]){
			k = dfs(V[p][i]) + L[V[p][i]];
			if(k > m1) m2 = m1, m1 = k;
			else if(k > m2) m2 = k;
		}
	}
	
	rt = max(rt, m1 + m2);
	
	return m1;
}

int main()
{
	ll i, j, p;
	
	scanf("%lld", &n);
	
	for(i=1;i<=n;i++){
		scanf("%lld%lld", P+i, L+i);
		V[P[i]].push_back(i);
	}
	
	for(i=1;i<=n;i++){
		if(!chk[i]){
			S.clear(); rt = c = 0;
			for(p=i,j=0;!chk[p];){
				S.push_back(p);
				chk[p] = ++j;
				p = P[p];
			}
			
			for(j=0;j<chk[p]-1;j++) chk[S[j]] = 0;
			p = chk[p] - 1;
			
			for(j=p;j<S.size();j++) K[j] = dfs(S[j]);
			
			if(S.size() - p > 1){
				if(P[S[p]] == S[p+1]){
					for(j=p;j<S.size();j++) D[j] = L[S[j]];
				}
				else{
					for(j=p+1;j<S.size();j++) D[j] = L[S[j-1]];
					D[p] = L[S.back()];
				}
				
				X[p] = K[p];
				rt = max(rt, X[p]);
				for(j=p+1;j<S.size();j++){
					X[j] = max(X[j-1] + D[j-1], K[j]);
					rt = max(rt, X[j-1] + D[j-1] + K[j]);
				}
				
				for(j=p;j<S.size();j++){
					c += D[j];
					D[j] = -D[j];
				}
				
				for(j=p+1;j<S.size();j++){
					X[j] = max(X[j-1] + D[j-1], K[j]);
					rt = max(rt, X[j-1] + D[j-1] + K[j] + c);
				}
			}
			
			ans += rt;
		}
	}
	
	printf("%lld\n", ans);
	
	return 0;
}

Compilation message

islands.cpp: In function 'll dfs(ll)':
islands.cpp:20:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(i=0;i<V[p].size();i++){
          ~^~~~~~~~~~~~
islands.cpp: In function 'int main()':
islands.cpp:56:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(j=p;j<S.size();j++) K[j] = dfs(S[j]);
            ~^~~~~~~~~
islands.cpp:60:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
      for(j=p;j<S.size();j++) D[j] = L[S[j]];
              ~^~~~~~~~~
islands.cpp:63:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
      for(j=p+1;j<S.size();j++) D[j] = L[S[j-1]];
                ~^~~~~~~~~
islands.cpp:69:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(j=p+1;j<S.size();j++){
               ~^~~~~~~~~
islands.cpp:74:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(j=p;j<S.size();j++){
             ~^~~~~~~~~
islands.cpp:79:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(j=p+1;j<S.size();j++){
               ~^~~~~~~~~
islands.cpp:37:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld", &n);
  ~~~~~^~~~~~~~~~~~
islands.cpp:40:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld%lld", P+i, L+i);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 24080 KB Output is correct
2 Correct 21 ms 24168 KB Output is correct
3 Correct 22 ms 24348 KB Output is correct
4 Correct 22 ms 24348 KB Output is correct
5 Correct 22 ms 24348 KB Output is correct
6 Correct 22 ms 24348 KB Output is correct
7 Correct 21 ms 24348 KB Output is correct
8 Correct 21 ms 24348 KB Output is correct
9 Correct 21 ms 24348 KB Output is correct
10 Correct 20 ms 24396 KB Output is correct
11 Correct 22 ms 24396 KB Output is correct

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 24396 KB Output is correct
2 Correct 23 ms 24396 KB Output is correct

Subtask #3
4.0 / 4.0

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

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 25092 KB Output is correct
2 Correct 44 ms 26272 KB Output is correct
3 Correct 36 ms 26272 KB Output is correct
4 Correct 26 ms 26272 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 27072 KB Output is correct
2 Correct 69 ms 29500 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 33728 KB Output is correct
2 Correct 116 ms 39036 KB Output is correct
3 Correct 147 ms 39740 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 205 ms 43340 KB Output is correct
2 Correct 244 ms 51112 KB Output is correct
3 Correct 239 ms 65160 KB Output is correct
4 Correct 295 ms 65160 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 363 ms 65160 KB Output is correct
2 Correct 780 ms 84412 KB Output is correct
3 Correct 371 ms 84412 KB Output is correct
4 Correct 478 ms 84412 KB Output is correct
5 Correct 394 ms 84412 KB Output is correct
6 Correct 1048 ms 84412 KB Output is correct
7 Correct 483 ms 84828 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 463 ms 133820 KB Output is correct
2 Correct 489 ms 133820 KB Output is correct
3 Correct 489 ms 133820 KB Output is correct
4 Correct 422 ms 133820 KB Output is correct
5 Correct 436 ms 133820 KB Output is correct
6 Correct 471 ms 133820 KB Output is correct
7 Correct 1000 ms 133820 KB Output is correct