Submission #120393

#	Time	Username	Problem	Language	Result	Execution time	Memory
120393		nvmdava	Islands (IOI08_islands)	C++17	100 / 100	862 ms	131072 KiB

islands

#include <bits/stdc++.h>
#define ff first
#define ss second
using namespace std;
#define N 1000005

pair<int, int> to[N];
vector<int> from[N];
bool inCyc[N];
bool in[N];
vector<int> cyc;
long long res, ans, tp, tmm;
vector<long long> p, dp;
void trav(int i){
	in[i] = 1;
	cyc.push_back(i);
	if(in[to[i].ff]){
		bool ok = 0;
		for(int& x : cyc){
			if(x == to[i].ff)ok = 1;
			if(ok)inCyc[x] = 1;
		}
	} else trav(to[i].ff);
	cyc.pop_back();
}
long long dfs(int v){
	long long b1 = 0, b2 = 0;
	for(int& x : from[v]){
		if(inCyc[x]) continue;
		long long up = dfs(x) + to[x].ss;
		if(up > b1){
			b2 = b1;
			b1 = up;
		} else b2 = max(b2, up);
	}
	res = max(res, b1 + b2);
	return b1;
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n;
	cin>>n;
	
	for(int i = 1; i <= n; i++){
		cin>>to[i].ff>>to[i].ss;
		from[to[i].ff].push_back(i);
	}
	
	for(int i = 1; i <= n; i++){
		if(in[i]) continue;
		trav(i);
	}
	for(int i = 1; i <= n; i++){
		if(inCyc[i]){
			res = 0;
			cyc.clear();
			p.clear();
			dp.clear();
			int t = i;
			p.push_back(0);
			do {
				cyc.push_back(t);
				p.push_back(p.back() + to[t].ss);
				dp.push_back(dfs(t));
				t = to[t].ff;
			} while (cyc[0] != t);
			for(int x : cyc) inCyc[x] = 0;
			tmm = dp[0] - p[0];
			tp = dp[0] + p[0];
			for(int i = 1; i < cyc.size(); i++){
				res = max(res, dp[i] + p[i] + tmm);
				res = max(res, dp[i] - p[i] + tp + p.back());
				tmm = max(tmm, dp[i] - p[i]);
				tp = max(tp, dp[i] + p[i]);
			}
			ans += res;
		}
	}
	cout<<ans;
}

Compilation message (stderr)

islands.cpp: In function 'int main()':
islands.cpp:73:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int i = 1; i < cyc.size(); 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: 10 / 10