Submission #216617

#	Time	Username	Problem	Language	Result	Execution time	Memory
216617		songc	Islands (IOI08_islands)	C++14	90 / 100	803 ms	131072 KiB

islands

#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<LL,LL> pii;

int N, M;
LL ans, ret, W[1000010];
int P[1000010];
bool chk[1000010];
vector<int> adj[1000010];
vector<pii> V;

int cyc(int u){
	if (chk[u]) return u;
	chk[u] = true;
	int r = cyc(P[u]);
	if (r){
		V.pb(pii(u, W[u]));
		return (r==u)?0:r;
	}
	chk[u] = false;
	return 0;
}

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

void dia(int u){
	V.clear();
	cyc(u);
	reverse(all(V));
	for (pii &v : V) v.first = dfs(v.first);
	M = V.size();
	for (int i=M-1; i>0; i--) swap(V[i].se, V[i-1].se);
	for (int i=1; i<M; i++) V[i].se += V[i-1].se;
	LL m1=-INF, m2=-INF;
	for (int i=0; i<M; i++){
		ret = max(ret, m1+V[i].se+V[i].fi);
		ret = max(ret, m2-V[i].se+V[i].fi+V[M-1].se);
		m1 = max(m1, V[i].fi-V[i].se);
		m2 = max(m2, V[i].fi+V[i].se);
	}
}

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 (stderr)

islands.cpp: In function 'int main()':
islands.cpp:60:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N);
  ~~~~~^~~~~~~~~~
islands.cpp:62: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 / 33
• Subtask 2: 3 / 3
• Subtask 3: 4 / 4
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 0 / 10