Submission #1244897

#	Time	Username	Problem	Language	Result	Execution time	Memory
1244897		altern23	Islands (IOI08_islands)	C++20	24 / 100	610 ms	196608 KiB

islands

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

#define ll long long
#define pii pair<ll, ll>
#define fi first
#define sec second
#define ld long double

const int MAXN = 1e6;
const ll INF = 1e18;
const int MOD = 998244353;
const ld eps = 1e-6;

struct DSU{
	ll N;
	vector<ll> par;
	DSU(ll _n){
		N = _n;
		par.resize(N + 5);
		for(int i = 1; i <= N; i++) par[i] = i;
	}
	ll find(ll idx){
		return (par[idx] == idx ? idx : par[idx] = find(par[idx]));
	}
	bool join(ll a, ll b){
		a = find(a), b = find(b);
		if(a == b) return false;
		par[b] = a;
		return true;
	}
};

vector<pii> adj[MAXN + 5];
ll vis[MAXN + 5], dp[MAXN + 5][2];

void dfs(ll idx){
	vis[idx] = 1;
	ll sum = 0;
	vector<ll> v;
	for(auto [i, j] : adj[idx]){
		if(!vis[i]){
			dfs(i);
			sum += max(dp[i][0], dp[i][1]);
			v.push_back(dp[i][0] + j - max(dp[i][0], dp[i][1]));
		}
	}
	dp[idx][0] = sum;
	sort(v.begin(), v.end(), greater<ll>());
	if(v.size() >= 1){
		dp[idx][0] = max(dp[idx][0], sum + v[0]);
	}
	if(v.size() >= 2){
		dp[idx][1] = max(dp[idx][1], sum + v[0] + v[1]);
	}
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);		
	int tc = 1;	
	// cin >> tc;
	for(;tc--;){
		ll N; cin >> N;
		vector<pair<ll, pii>> edges;
		for(int i = 1; i <= N; i++){
			ll idx, val; cin >> idx >> val;
			edges.push_back({val, {i, idx}});
		}
		sort(edges.begin(), edges.end(), greater<pair<ll, pii>>());
		DSU dsu(N);
		for(auto [w, node] : edges){
			if(dsu.join(node.fi, node.sec)){
				adj[node.fi].push_back({node.sec, w});
				adj[node.sec].push_back({node.fi, w});
			}
		}
		
		ll ans = 0;
		for(int i = 1; i <= N; i++){
			if(!vis[i]){
				dfs(i);
				ans += max(dp[i][0], dp[i][1]);
			}
		}
		
		cout << ans << "\n";
	}
}

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