Submission #810444

#	Time	Username	Problem	Language	Result	Execution time	Memory
810444		qwerasdfzxcl	Security Guard (JOI23_guard)	C++17	100 / 100	559 ms	127148 KiB

guard

#include <bits/stdc++.h>
 
using namespace std;
typedef long long ll;
 
int n, mn, mx;
ll a[200200];
pair<int, int> E[400400];
 
ll ans[200200];
 
priority_queue<array<ll, 4>, vector<array<ll, 4>>, greater<array<ll, 4>>> pq;
 
struct DSU{
	int path[200200], valid[200200], n;
	priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq2[200200];
 
	void init(int N){
		n = N;
		for (int i=1;i<=n;i++){
			path[i] = i;
			valid[i] = 1;
		}
	}
 
	void reset(int x){valid[x] = 0;}
 
	void push(int x, int y){
		pq2[x].emplace(a[x]+a[y], y);
		pq2[y].emplace(a[x]+a[y], x);
	}
 
	void init2(){
		for (int i=1;i<=n;i++) if (valid[i] && !pq2[i].empty()){
			auto [cst, v] = pq2[i].top();
			pq.push({cst - a[i] - a[mn], cst, v, i});
		}
	}
 
	int find(int s){
		if (path[s]==s) return s;
		return path[s] = find(path[s]);
	}
 
	void merge(int s, int v){
		s = find(s), v = find(v);
		assert(s!=v);
 
		path[v] = s;
		if (!valid[s]) return;
 
		if (pq2[s].size() < pq2[v].size()) swap(pq2[s], pq2[v]);
		while(!pq2[v].empty()){
			pq2[s].push(pq2[v].top()); pq2[v].pop();
		}
 
		while(!pq2[s].empty() && find(pq2[s].top().second)==s) pq2[s].pop();
		if (!pq2[s].empty()){
			auto [cst, nxt] = pq2[s].top();
			pq.push({cst - a[s] - a[mn], cst, nxt, s});
		} 
 
	}
}dsu;
 
bool valid(const array<ll, 4> &p){
	if (dsu.find(p[2]) == dsu.find(p[3])) return 0;
	if (!dsu.valid[dsu.find(p[3])]) return 0;
	return p[1] - a[mn] - a[dsu.find(p[3])] == p[0];
}
 
int main(){
	int n, m, q;
	scanf("%d %d %d", &n, &m, &q);
	for (int i=1;i<=n;i++) scanf("%lld", a+i);
	for (int i=1;i<=m;i++){
		int x, y;
		scanf("%d %d", &x, &y);
		E[i] = {x, y};
	}
 
	mn = min_element(a+1, a+n+1) - a;
	mx = max_element(a+1, a+n+1) - a;
	dsu.init(n);
 
	int sz = n-1;
 
	for (int i=1;i<=m;i++){
		if (E[i].first==mn || E[i].second==mn){
			if (E[i].second==mn) swap(E[i].first, E[i].second);
			dsu.reset(E[i].second);
			sz--;
		}
 
		else{
			dsu.push(E[i].first, E[i].second);
		}
	}
 
	dsu.init2();
 
	for (int i=1;i<=n;i++) ans[sz] += a[i];
	ans[sz] += a[mn] * (n-2);
 
	for (int i=sz-1;i>=0;i--){
		while(!pq.empty() && !valid(pq.top())) pq.pop();
		assert(!pq.empty());
		auto [cst, _, u, v] = pq.top(); pq.pop();
 
		dsu.merge(u, v);
		ans[i] = ans[i+1] + cst;
	}
 
	ll ofs = a[mx];
	for (int i=1;i<=n;i++) ofs -= a[i];
 
	for (int i=0;i<=q;i++) printf("%lld\n", ans[min(i, sz)] + ofs);
}

Compilation message (stderr)

guard.cpp: In function 'int main()':
guard.cpp:74:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   74 |  scanf("%d %d %d", &n, &m, &q);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
guard.cpp:75:30: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   75 |  for (int i=1;i<=n;i++) scanf("%lld", a+i);
      |                         ~~~~~^~~~~~~~~~~~~
guard.cpp:78:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   78 |   scanf("%d %d", &x, &y);
      |   ~~~~~^~~~~~~~~~~~~~~~~

• 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