Submission #101053

#	Time	Username	Problem	Language	Result	Execution time	Memory
101053		maruii	Islands (IOI08_islands)	C++14	21 / 100	1367 ms	132096 KiB

islands

#include <bits/stdc++.h>
using namespace std;
bool vis[1000001];
vector<pair<int, int> > edge[1000001];
long long dp1[1000001], dp2[1000001];
vector<int> vec;
void dfs(int x){
	vec.push_back(x);
	vis[x] = 1;
	dp1[x] = dp2[x] = 0;
	long long mx1 = 0, mx2 = 0;
	for(auto i: edge[x]){
		if(vis[i.second]) continue; 
		dfs(i.second);
		dp1[x] = max(dp1[x], dp1[i.second]);
		long long t = dp2[i.second]+i.first;
		dp2[x] = max(dp2[x], t);
		if(mx1 <= t) mx2 = mx1, mx1 = t;
		else if(mx2 < t) mx2 = t;
	}
	dp1[x] = max(dp1[x], mx1+mx2);
}
long long getD(int x){
	dfs(x);
	return dp1[x];
}
int main(){
	ios_base::sync_with_stdio(0), cin.tie(0);
	int N; cin>>N;
	for(int i=1; i<=N; ++i){
		int a,b; cin>>a>>b;
		edge[i].push_back({b, a});
		edge[a].push_back({b, i});
	}
	long long ans = 0;
	for(int i=1; i<=N; ++i){
		if(vis[i]) continue;
		long long t = getD(i);
		for(auto j: vec) reverse(edge[j].begin(), edge[j].end()), vis[j] = 0;
		vec.clear();
		t = max(t, getD(i));
		vec.clear();
		ans += t;

	}
	cout<<ans;
	return 0;
}

• Subtask 1: 21 / 33
• Subtask 2: 0 / 3
• Subtask 3: 0 / 4
• Subtask 4: 0 / 10
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10