Submission #1155078

#	Time	Username	Problem	Language	Result	Execution time	Memory
1155078		NAMIN	Nile (IOI24_nile)	C++20	38 / 100	74 ms	15032 KiB

nile

#include <bits/stdc++.h>
#include "nile.h"

using namespace std;

#define ll long long

vector<ll> S,parent,mn_g;

int find(int node){
	if(parent[node] == node)
		return node;
	return parent[node] = find(parent[node]);
}

void unite(int a,int b){
	a = find(a),b = find(b);
	parent[b] = parent[a];
	S[a] += S[b];
	mn_g[a] = min(mn_g[a],mn_g[b]);
}

vector<ll> calculate_costs(vector<int> W,vector<int> A,vector<int> B,vector<int> E){
	
	int n = W.size();
	S.assign(W.size(),1);
	parent.assign(W.size(),0);
	mn_g.assign(W.size(),1e18);
	
	vector<pair<int,int>> w;

	for(int i=0;i<n;i++){
		parent[i] = i;
	}
	for(int i=0;i<n;i++){
		mn_g[i] = A[i]-B[i];
		w.push_back(make_pair(W[i],i));
	}

	ll cur_ans = 0;
	ll sum_mn = 0;
	for(int i=0;i<n;i++){
		cur_ans += B[i];
		sum_mn += mn_g[i];
	}
	vector<pair<int,ll>> possAns; // D,ans
	possAns.push_back(make_pair(-1,cur_ans+sum_mn));
	vector<pair<int,pair<int,int>>> process;
	sort(w.begin(),w.end());
	for(int i=0;i<n-1;i++){
		int a = w[i].second,b = w[i+1].second;
		process.push_back(make_pair(w[i+1].first-w[i].first,
						make_pair(a,b)));
	}
	sort(process.begin(),process.end());
	map<int,bool> take;
	map<int,ll> defAns;
	for(auto p_cur : process){
		int a = find(p_cur.second.first),b = find(p_cur.second.second);
		int d = p_cur.first;
		if(S[a]%2 == 1 && S[b]%2 == 0){
			sum_mn -= mn_g[a];
			sum_mn += min(mn_g[a],mn_g[b]);
		}
		else if(S[a]%2 == 0 && S[b]%2 == 1){
			sum_mn -= mn_g[b];
			sum_mn += min(mn_g[a],mn_g[b]);
		}
		else if(S[a]%2 == 1 && S[b]%2 == 1){
			sum_mn -= mn_g[b]+mn_g[a];
		}
		unite(a,b);
		if(!take[d]){
			defAns[d] = cur_ans+sum_mn;
			take[d] = true;
		}
		else
			defAns[d] = min(defAns[d],cur_ans+sum_mn);
	}
	for(auto p : defAns){
		possAns.push_back(p);
	}
	vector<ll> ans;
	for(int i=0;i<(int)E.size();i++){
		int d = E[i];
		auto it = upper_bound(possAns.begin(),possAns.end(),make_pair(d,(ll)1e18));
		it--;
		pair<int,ll> p = *it;
		ans.push_back(p.second);
	}
	return ans;
}

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