oj.uz

Submission #53718

# Submission time Handle Problem Language Result Execution time Memory
53718 2018-07-01T05:55:31 Z 김세빈(#1437) Islands (IOI08_islands) C++11
9 / 100
 830 ms 133980 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;

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 = 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]);
			K[S.size()] = K[p];
			
			if(S.size() - p > 1){
				if(P[S[p]] == 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]);
				}
				
				D[p+1] = K[p+1];
				for(j=p+2;j<=S.size();j++){
					X[j] = max(X[j-1] + D[j-1], K[j]);
					rt = max(rt, X[j]);
				}
			}
			
			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:61: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:64: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:70:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(j=p+1;j<S.size();j++){
               ~^~~~~~~~~
islands.cpp:76:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(j=p+2;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
9.0 / 33.0

# Verdict Execution time Memory Grader output
1 Incorrect 28 ms 24056 KB Output isn't correct
2 Incorrect 21 ms 24164 KB Output isn't correct
3 Incorrect 24 ms 24240 KB Output isn't correct
4 Correct 23 ms 24240 KB Output is correct
5 Correct 21 ms 24240 KB Output is correct
6 Incorrect 22 ms 24240 KB Output isn't correct
7 Incorrect 21 ms 24352 KB Output isn't correct
8 Incorrect 22 ms 24352 KB Output isn't correct
9 Incorrect 21 ms 24392 KB Output isn't correct
10 Correct 26 ms 24392 KB Output is correct
11 Incorrect 23 ms 24392 KB Output isn't correct

Subtask #2
0 / 3.0

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

Subtask #3
0 / 4.0

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

Subtask #4
0 / 10.0

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

Subtask #5
0 / 10.0

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

Subtask #6
0 / 10.0

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

Subtask #7
0 / 10.0

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

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 349 ms 55740 KB Output is correct
2 Incorrect 830 ms 84464 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 500 ms 133980 KB Output is correct
2 Correct 512 ms 133980 KB Output is correct
3 Incorrect 437 ms 133980 KB Output isn't correct
4 Halted 0 ms 0 KB -