Submission #101068

#	Time	Username	Problem	Language	Result	Execution time	Memory
101068		maruii	Islands (IOI08_islands)	C++14	9 / 100	721 ms	132096 KiB

islands

#include <bits/stdc++.h>
using namespace std;
bool vis[1000001], isC[1000001];
vector<pair<int, int> > edge[1000001];
long long dp1[1000001], dp2[1000001], D;
int prt[1000001], pdg[1000001], dth[1000001], X, C;
vector<int> vec;
void dfs(int x, int p, int pp){
	vis[x] = 1;
	dp1[x] = dp2[x] = 0;
	long long mx1 = 0, mx2 = 0, m2 = 0;
	bool flag = 1;
	for(auto i: edge[x]){
		if(i.second == p && i.first == pp && flag){
			flag = 0;
			continue;
		}
		if(vis[i.second]){
			if(dth[i.second] > dth[x]) continue;
			vec.clear();
			for(int v=x; v!=i.second; v=prt[v]) vec.push_back(v), isC[v] = 1;
			isC[i.second] = 1;
			X = i.first;
			C = i.second;
			continue;
		}
		prt[i.second] = x;
		pdg[i.second] = i.first;
		dth[i.second] = dth[x] + 1;
		dfs(i.second, x, i.first);
		if(x==C && !isC[i.second]) m2 = max(m2, dp2[i.second]+i.first);
		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;
	}
	if(x==C){
		long long t = X;
		vector<long long> v1;
		for(auto i: vec){
			if(v1.size() && v1.back() > t+dp2[i]) v1.push_back(v1.back());
			else v1.push_back(t+dp2[i]);
			dp2[x] = max(dp2[x], t+dp2[i]);
			t += pdg[i];
		}
		reverse(vec.begin(), vec.end());
		t = 0;
		int cnt = vec.size()-2;
		long long s = 0;
		for(auto i: vec){
			if(cnt<0) break;
			t += pdg[i];
			for(auto j: edge[i]){
				if(isC[j.second]) continue;
				s = max(s, dp2[j.second]+t);
			}
			s = max(s, t+dp2[i]);
			dp1[x] = max(dp1[x], s+v1[cnt]);
			--cnt;
		}
		dp1[x] = max(dp1[x], v1.back()+m2);
	}
	dp1[x] = max(dp1[x], mx1+mx2);
}
long long getD(int x){
	dfs(x, 0, 0);
	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;
		ans += getD(i);
	}
	cout<<ans;
	return 0;
}

• Subtask 1: 9 / 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