Submission #1131511

#	Time	Username	Problem	Language	Result	Execution time	Memory
1131511		Math4Life2020	Security Guard (JOI23_guard)	C++20	50 / 100	335 ms	57128 KiB

guard

#include <bits/stdc++.h>
using namespace std;
using ll = long long; using pii = pair<ll,ll>;
const ll Nm = 4e5+5;
const ll INF = 1e18;

ll f[Nm]; //forward
ll fsz[Nm]; //size 
ll mval[Nm]; //max val of S

ll gt(ll x) {
	if (f[x]==x) {
		return x;
	}
	return (f[x]=gt(f[x])); //ackermann dsu impl
}

void fz(ll x, ll y) {
	x = gt(x); y=gt(y);
	if (fsz[x]>fsz[y]) {
		swap(x,y);
	}
	f[x]=y;
	fsz[y]+=fsz[x];
	mval[y]=max(mval[y],mval[x]);
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	ll N,M,Q; cin >> N >> M >> Q;
	ll S[N];
	bool ispr[N];
	vector<ll> adj[N];
	vector<pii> ord;
	ll ans = 0;
	ll maxS = 0;
	ll minSv = INF;
	ll minScns = -1;
	for (ll i=0;i<N;i++) {
		ispr[i]=0;
		cin >> S[i];
		ans -= S[i];
		maxS = max(maxS,S[i]);
		if (S[i]<minSv) {
			minSv = S[i];
			minScns = i;
		}
		f[i]=i;
		fsz[i]=1;
		mval[i]=S[i];
		ord.push_back({S[i],i});
	}
	ans += maxS;
	vector<pii> srtedg; //{weight, index}
	vector<pii> edg;
	vector<ll> adj2[N];
	for (ll m=0;m<M;m++) {
		ll a,b; cin >> a >> b;
		a--; b--;
		adj[a].push_back(b);
		adj[b].push_back(a);
		srtedg.push_back({S[a]+S[b],m});
		edg.push_back({a,b});
	}
	sort(srtedg.begin(),srtedg.end());
	for (pii p0: srtedg) {
		ll m = p0.second;
		ll wt = p0.first;
		ll a = edg[m].first; ll b = edg[m].second;
		if (gt(a)!=gt(b)) {
			adj2[a].push_back(b);
			adj2[b].push_back(a);
			ans += wt;
			fz(a,b);
		}
	}
	cout << ans << "\n";
	ll rt = minScns;
	ll radj2[N];
	radj2[rt]=-1;
	queue<ll> q2;
	q2.push(rt);
	vector<ll> vupd;
	while (!q2.empty()) {
		ll x = q2.front(); q2.pop();
		for (ll y: adj2[x]) {
			if (y != radj2[x]) {
				radj2[y]=x;
				q2.push(y);
				vupd.push_back(S[x]-S[rt]);
			}
		}
	}
	sort(vupd.rbegin(),vupd.rend());
	for (ll q=0;q<Q;q++) {
		if (q<vupd.size()) {
			ans -= vupd[q];
		}
		cout << ans << "\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