oj.uz

Submission #53797

# Submission time Handle Problem Language Result Execution time Memory
53797 2018-07-01T08:11:45 Z 김세빈(#1437) Islands (IOI08_islands) C++11
100 / 100
 1043 ms 133824 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 23 ms 24056 KB Output is correct
2 Correct 24 ms 24168 KB Output is correct
3 Correct 21 ms 24168 KB Output is correct
4 Correct 21 ms 24168 KB Output is correct
5 Correct 22 ms 24236 KB Output is correct
6 Correct 21 ms 24236 KB Output is correct
7 Correct 21 ms 24236 KB Output is correct
8 Correct 24 ms 24236 KB Output is correct
9 Correct 21 ms 24340 KB Output is correct
10 Correct 21 ms 24340 KB Output is correct
11 Correct 21 ms 24340 KB Output is correct

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 24368 KB Output is correct
2 Correct 22 ms 24376 KB Output is correct

Subtask #3
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 24376 KB Output is correct
2 Correct 27 ms 24508 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 25020 KB Output is correct
2 Correct 37 ms 26260 KB Output is correct
3 Correct 32 ms 26260 KB Output is correct
4 Correct 26 ms 26260 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 27096 KB Output is correct
2 Correct 58 ms 29456 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 128 ms 33716 KB Output is correct
2 Correct 100 ms 39000 KB Output is correct
3 Correct 132 ms 39692 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 176 ms 43312 KB Output is correct
2 Correct 206 ms 50976 KB Output is correct
3 Correct 223 ms 65056 KB Output is correct
4 Correct 282 ms 65056 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 322 ms 65056 KB Output is correct
2 Correct 736 ms 84408 KB Output is correct
3 Correct 342 ms 84408 KB Output is correct
4 Correct 417 ms 84408 KB Output is correct
5 Correct 385 ms 84408 KB Output is correct
6 Correct 1006 ms 84408 KB Output is correct
7 Correct 447 ms 84876 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 482 ms 133824 KB Output is correct
2 Correct 438 ms 133824 KB Output is correct
3 Correct 449 ms 133824 KB Output is correct
4 Correct 517 ms 133824 KB Output is correct
5 Correct 448 ms 133824 KB Output is correct
6 Correct 444 ms 133824 KB Output is correct
7 Correct 1043 ms 133824 KB Output is correct