Submission #1245649

#	Time	Username	Problem	Language	Result	Execution time	Memory
1245649		YassirSalama	Nile (IOI24_nile)	C++20	17 / 100	2095 ms	20724 KiB

nile

#include "nile.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define all(v) v.begin(),v.end()
const int maxn = 1e5+100;
int par[maxn];
vector<int> a,b,w;
void init(){
	for(int i = 0;i<maxn;i++){
		par[i] = i;
	}
}
int find(int node){
	return node==par[node]?node:par[node] = find(par[node]);
}
void merge(int a,int b){
	a = find(a);
	b = find(b);
	if(a==b) return;
	par[b] = a;
}

vector<ll> calculate_costs(vector<int> W, vector<int> A,vector<int> B, vector<int> E) {
	a = A;
	b = B;
	w = W;
	vector<vector<ll>> v;
	int n = w.size();
	for(int i = 0;i<n;i++){
		v.pb({(ll)w[i],(ll)a[i],(ll)b[i]});
	}
	vector<ll> ans;
	sort(all(v));
	for(auto d : E){
		init();
		for(int i = 0;i+1<n;i++){
			if((v[i+1][0]-v[i][0])<=d){
				//merge these two
				merge(i,i+1);
			}
		}
		map<int,vector<int>> mp;
		for(int i = 0;i<n;i++){
			mp[find(i)].pb(i);
		}
		ll sum = 0;
		#define F first
		#define S second
		for(auto x : mp){
			vector<int> c = x.S;
			if(c.size()%2==0){
				for(auto x : c){
					sum+=(ll)v[x][2];
				}
			}else{
				pair<ll,ll> mn = {(ll)1e18,(ll)1e18};
				for(auto x : c){
					mn = min(mn,make_pair((ll)v[x][1],(ll)v[x][2]));
					sum+=(ll)v[x][2];
				}
				sum-=(ll)mn.S;
				sum+=(ll)mn.F;
			}
		}
		ans.pb(sum);
	}
	return ans;
}

• Subtask 0: 0 / 0
• Subtask 1: 0 / 6
• Subtask 2: 0 / 13
• Subtask 3: 17 / 17
• Subtask 4: 0 / 11
• Subtask 5: 0 / 20
• Subtask 6: 0 / 15
• Subtask 7: 0 / 18