Submission #1032066

#	Time	Username	Problem	Language	Result	Execution time	Memory
1032066		Unforgettablepl	Security Guard (JOI23_guard)	C++17	100 / 100	351 ms	108716 KiB

guard

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

#define int long long

struct UFDSsimple{
	vector<int> p,siz,mini;
	UFDSsimple(int n):p(n+1),siz(n+1,1){iota(p.begin(),p.end(),0);}
	int findRoot(int x){
		return p[x]==x ? x : p[x]=findRoot(p[x]);
	}
	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);
		siz[a]+=siz[b];
		p[b]=a;
		return true;
	}
};

struct UFDS{
	vector<int> p,siz,mini,lazy,decomissioner;
	vector<priority_queue<pair<int,int>>> pq;
	priority_queue<pair<int,int>> globalpq;
	UFDS(int n,vector<int> arr,vector<pair<int,int>> edges):p(n+1),siz(n+1,1),mini(n+1),lazy(n+1),decomissioner(n+1),pq(n+1){
		iota(p.begin(),p.end(),0);
		mini=arr;
		int globalmini = *min_element(arr.begin()+1,arr.end());
		for(int i=0;i<n-1;i++){
			auto [u,v] = edges[i];
			pq[u].emplace(globalmini-arr[v],v);
			pq[v].emplace(globalmini-arr[u],u);
		}
		for(int i=1;i<=n;i++)globalpq.emplace(pq[i].top().first,i);
	}
	int findRoot(int x){
		return p[x]==x ? x : p[x]=findRoot(p[x]);
	}
	void unite(int a,int b){
		a = findRoot(a);
		b = findRoot(b);
		if(a==b)assert(false);
		if(siz[b]>siz[a])swap(a,b);
		int newmin = min(mini[a],mini[b]);
		decomissioner[a]++;
		decomissioner[b]++;
		lazy[a]+=newmin-mini[a];
		lazy[b]+=newmin-mini[b];
		if(pq[b].size()>pq[a].size()){
			swap(pq[a],pq[b]);
			swap(lazy[a],lazy[b]);
		}
		while(!pq[b].empty()){
			auto [cost,v] = pq[b].top();pq[b].pop();
			pq[a].emplace(cost+lazy[b]-lazy[a],v);
		}
		if(!pq[a].empty())globalpq.emplace(pq[a].top().first+lazy[a],a);
		mini[a]=newmin;
		siz[a]+=siz[b];
		p[b]=a;
	}
	int get_best(){
		if(globalpq.empty())assert(false);
		auto [cost,curra] = globalpq.top();globalpq.pop();
		if(decomissioner[curra]){
			decomissioner[curra]--;
			return get_best();
		}
		auto [temp,currb] = pq[curra].top();pq[curra].pop();
		curra = findRoot(curra);
		currb = findRoot(currb);
		if(curra==currb){
			globalpq.emplace(pq[curra].top().first+lazy[curra],curra);
			return get_best();
		}
		decomissioner[curra]--;
		unite(curra,currb);
		return cost;
	}
};


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()));
	baseans += (n-2ll)*(*min_element(arr.begin()+1,arr.end()));
	UFDSsimple dsusim(n);
	vector<pair<int,int>> gudedges;
	for(int i=0;i<m;i++){
		auto [cost,a,b] = edges[i];
		if(!dsusim.unite(a,b))continue;
		gudedges.emplace_back(a,b);
	} 
	vector<int> ans(n);
	ans[0] = baseans;
	UFDS dsu(n,arr,gudedges);
	for(int i=1;i<n;i++){
		ans[i]=ans[i-1]-dsu.get_best();
	}
	for(int i=0;i<=q;i++){
		cout << ans[max(n-1-i,0ll)] << '\n';
	}
}

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