oj.uz

Submission #1032049

# Submission time Handle Problem Language Result Execution time Memory
1032049 2024-07-23T10:37:53 Z Unforgettablepl Security Guard (JOI23_guard) C++17
0 / 100
 153 ms 98948 KB 
#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)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
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 101 ms 52780 KB Output is correct
3 Correct 109 ms 52856 KB Output is correct
4 Runtime error 153 ms 98948 KB Execution killed with signal 6
5 Halted 0 ms 0 KB -

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 101 ms 52780 KB Output is correct
3 Correct 109 ms 52856 KB Output is correct
4 Runtime error 153 ms 98948 KB Execution killed with signal 6
5 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 101 ms 52780 KB Output is correct
3 Correct 109 ms 52856 KB Output is correct
4 Runtime error 153 ms 98948 KB Execution killed with signal 6
5 Halted 0 ms 0 KB -

Subtask #4
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 101 ms 52780 KB Output is correct
3 Correct 109 ms 52856 KB Output is correct
4 Runtime error 153 ms 98948 KB Execution killed with signal 6
5 Halted 0 ms 0 KB -

Subtask #5
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Runtime error 1 ms 604 KB Execution killed with signal 6
6 Halted 0 ms 0 KB -

Subtask #6
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Runtime error 1 ms 604 KB Execution killed with signal 6
6 Halted 0 ms 0 KB -

Subtask #7
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 101 ms 52780 KB Output is correct
3 Correct 109 ms 52856 KB Output is correct
4 Runtime error 153 ms 98948 KB Execution killed with signal 6
5 Halted 0 ms 0 KB -