Submission #1030910

#	Time	Username	Problem	Language	Result	Execution time	Memory
1030910		Unforgettablepl	Security Guard (JOI23_guard)	C++17	50 / 100	225 ms	28848 KiB

guard

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

#define int long long

struct UFDS{
	vector<int> p,siz,mini;
	multiset<int> miniset;
	int sigma,compo;
	UFDS(int n,vector<int> arr):p(n+1),siz(n+1,1),mini(n+1),sigma(0),compo(n){
		iota(p.begin(),p.end(),0);
		mini=arr;
		for(int i=1;i<=n;i++){
			miniset.insert(arr[i]);
			sigma+=arr[i];
		}
	}
	int findRoot(int x){
		return p[x]==x ? x : p[x]=findRoot(p[x]);
	}
	int getans(){
		return sigma+(compo-2ll)*(*miniset.begin());
	}
	bool unite(int a,int b){
		a = findRoot(a);
		b = findRoot(b);
		if(a==b)return false;
		if(siz[b]>siz[a])swap(a,b);
		int maxi = max(mini[a],mini[b]);
		mini[a]=min(mini[a],mini[b]);
		miniset.erase(miniset.find(maxi));
		sigma-=maxi;
		siz[a]+=siz[b];
		p[b]=a;
		compo--;
		return true;
	}
};


int32_t main(){
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	int n,m,q;
	cin >> n >> m >> q;
	vector<int> arr(n+1);
	for(int i=1;i<=n;i++)cin>>arr[i];
	vector<tuple<int,int,int>> edges;
	for(int i=1;i<=m;i++){
		int a,b;
		cin >> a >> b;
		edges.emplace_back(arr[a]+arr[b],a,b);
	}
	sort(edges.begin(),edges.end());
	int baseans = (*max_element(arr.begin(),arr.end()));
	for(int i=1;i<=n;i++){
		baseans-=arr[i];
	}
	UFDS dsu(n,arr);
	vector<int> ans(n);
	ans[0] = dsu.getans();
	int iter = 1;
	int offset = 0;
	for(int i=0;i<m;i++){
		auto [cost,a,b] = edges[i];
		if(dsu.unite(a,b)){
			offset+=cost;
			ans[iter++]=offset+dsu.getans();
		}
	}
	for(int i=0;i<=q;i++){
		cout << baseans+ans[max(0ll,n-1ll-i)] << '\n';
	}
}

• Subtask 1: 12 / 12
• Subtask 2: 13 / 13
• Subtask 3: 12 / 12
• Subtask 4: 13 / 13
• Subtask 5: 0 / 8
• Subtask 6: 0 / 18
• Subtask 7: 0 / 24