Submission #439905

#	Time	Username	Problem	Language	Result	Execution time	Memory
439905		dutch	Islands (IOI08_islands)	C++17	0 / 100	434 ms	131076 KiB

islands

#include <bits/stdc++.h>
using namespace std;

const int LIM = 1e6;

vector<array<int, 2>> a(LIM), g[LIM];
bitset<LIM> vis;
pair<long long, int> c;
long long toRoot;
int r;

void dfs(int u, int p, long long d){
	vis[u] = 1, c = max(c, {d, u});
	for(auto &[v, w] : g[u]) if(v != p){
		if(v == r) toRoot = d;
		else dfs(v, u, d + (long long)w);
	}
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n; cin >> n;

	for(int i=0; i<n; ++i){
		cin >> a[i][0] >> a[i][1];
		g[--a[i][0]].push_back({i, a[i][1]});
	}

	long long ans = 0;

	for(r=0; r<n; ++r){
		if(vis[r]) continue;
		dfs(r, r, 0);
		long long curr = toRoot + a[r][1];
		dfs(c.second, -1, 0);
		curr = max(curr, c.first);
		ans += curr;
	}

	cout << ans;
}

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