oj.uz

Submission #53736

# Submission time Handle Problem Language Result Execution time Memory
53736 2018-07-01T06:12:03 Z 김세빈(#1437) Islands (IOI08_islands) C++11
0 / 100
 25 ms 24444 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()
{
	freopen("input.txt","r",stdin);
	
	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:58: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:62: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:65: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:71:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(j=p+1;j<S.size();j++){
               ~^~~~~~~~~
islands.cpp:76:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(j=p;j<S.size();j++){
             ~^~~~~~~~~
islands.cpp:81:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(j=p+1;j<S.size();j++){
               ~^~~~~~~~~
islands.cpp:35:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  freopen("input.txt","r",stdin);
  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
islands.cpp:39:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld", &n);
  ~~~~~^~~~~~~~~~~~
islands.cpp:42: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
0 / 33.0

# Verdict Execution time Memory Grader output
1 Incorrect 22 ms 24056 KB Output isn't correct
2 Incorrect 22 ms 24300 KB Output isn't correct
3 Incorrect 21 ms 24300 KB Output isn't correct
4 Incorrect 22 ms 24300 KB Output isn't correct
5 Incorrect 22 ms 24300 KB Output isn't correct
6 Incorrect 21 ms 24300 KB Output isn't correct
7 Incorrect 23 ms 24420 KB Output isn't correct
8 Incorrect 25 ms 24420 KB Output isn't correct
9 Incorrect 22 ms 24420 KB Output isn't correct
10 Incorrect 20 ms 24420 KB Output isn't correct
11 Incorrect 21 ms 24420 KB Output isn't correct

Subtask #2
0 / 3.0

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

Subtask #3
0 / 4.0

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

Subtask #4
0 / 10.0

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

Subtask #5
0 / 10.0

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

Subtask #6
0 / 10.0

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

Subtask #7
0 / 10.0

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

Subtask #8
0 / 10.0

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

Subtask #9
0 / 10.0

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