oj.uz

Submission #216630

# Submission time Handle Problem Language Result Execution time Memory
216630 2020-03-27T17:32:03 Z songc Islands (IOI08_islands) C++14
100 / 100
 833 ms 131072 KB 
#include <bits/stdc++.h>
#define pb push_back
#define all(v) v.begin(),v.end()
#define fi first
#define se second
#define INF (1ll<<60)
using namespace std;
typedef long long LL;
typedef pair<int,int> pii;
 
int N, M;
LL ans, ret;
int P[1000010], W[1000010];
LL R[1000010], mx[1000010];
bool chk[1000010];
vector<int> adj[1000010];
vector<LL> V, S;
 
inline int cyc(int u){
	if (chk[u]) return u;
	chk[u] = true;
	R[u] = cyc(P[u]);
	if (R[u]){
		V.pb(u), S.pb(W[u]);
		return (R[u]==u)?0:R[u];
	}
	chk[u] = false;
	return 0;
}

inline LL dfs(int u){
	mx[u]=0;
	chk[u] = true;
	for (int v : adj[u]){
		if (chk[v]) continue;
		R[u] = dfs(v) + W[v];
		ret = max(ret, (LL)mx[u]+R[u]);
		mx[u] = max(mx[u], R[u]);
	}
	return mx[u];
}

void dia(int u){
	V.clear(), S.clear();
	cyc(u);
	reverse(all(V)); reverse(all(S));
	for (LL &v : V) v = dfs(v);
	M = V.size();
	for (int i=M-1; i>0; i--) swap(S[i], S[i-1]);
	for (int i=1; i<M; i++) S[i] += S[i-1];
	LL m1=-INF, m2=-INF;
	for (int i=0; i<M; i++){
		ret = max(ret, m1+S[i]+V[i]);
		ret = max(ret, m2-S[i]+V[i]+S[M-1]);
		m1 = max(m1, V[i]-S[i]);
		m2 = max(m2, V[i]+S[i]);
	}
}
 
int main(){
	scanf("%d", &N);
	for (int i=1; i<=N; i++){
		scanf("%d %lld", &P[i], &W[i]);
		adj[P[i]].pb(i);
	}
	for (int i=1; i<=N; i++){
		if (chk[i]) continue;
		dia(i);
		ans+=ret, ret=0;
	}
	printf("%lld\n", ans);
	return 0;
}

Compilation message

islands.cpp: In function 'int main()':
islands.cpp:63:32: warning: format '%lld' expects argument of type 'long long int*', but argument 3 has type 'int*' [-Wformat=]
   scanf("%d %lld", &P[i], &W[i]);
                           ~~~~~^
islands.cpp:61:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N);
  ~~~~~^~~~~~~~~~
islands.cpp:63:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %lld", &P[i], &W[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 23808 KB Output is correct
2 Correct 18 ms 23808 KB Output is correct
3 Correct 19 ms 23936 KB Output is correct
4 Correct 19 ms 23808 KB Output is correct
5 Correct 19 ms 23808 KB Output is correct
6 Correct 18 ms 23808 KB Output is correct
7 Correct 20 ms 23808 KB Output is correct
8 Correct 18 ms 23808 KB Output is correct
9 Correct 18 ms 23808 KB Output is correct
10 Correct 18 ms 23808 KB Output is correct
11 Correct 19 ms 23808 KB Output is correct

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 23936 KB Output is correct
2 Correct 19 ms 23936 KB Output is correct

Subtask #3
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 23936 KB Output is correct
2 Correct 22 ms 24192 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 24992 KB Output is correct
2 Correct 34 ms 26488 KB Output is correct
3 Correct 28 ms 25088 KB Output is correct
4 Correct 23 ms 24448 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 27636 KB Output is correct
2 Correct 56 ms 30708 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 35688 KB Output is correct
2 Correct 102 ms 42212 KB Output is correct
3 Correct 124 ms 45148 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 175 ms 46200 KB Output is correct
2 Correct 220 ms 56616 KB Output is correct
3 Correct 228 ms 72536 KB Output is correct
4 Correct 288 ms 72396 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 303 ms 46300 KB Output is correct
2 Correct 607 ms 86068 KB Output is correct
3 Correct 317 ms 60920 KB Output is correct
4 Correct 402 ms 82380 KB Output is correct
5 Correct 394 ms 80000 KB Output is correct
6 Correct 826 ms 68472 KB Output is correct
7 Correct 453 ms 97976 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 445 ms 111824 KB Output is correct
2 Correct 452 ms 95352 KB Output is correct
3 Correct 482 ms 131072 KB Output is correct
4 Correct 428 ms 81228 KB Output is correct
5 Correct 393 ms 80640 KB Output is correct
6 Correct 411 ms 76420 KB Output is correct
7 Correct 833 ms 68944 KB Output is correct