Submission #1131302

#	Time	Username	Problem	Language	Result	Execution time	Memory
1131302		Math4Life2020	Security Guard (JOI23_guard)	C++20	50 / 100	305 ms	39668 KiB

guard

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

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;
	for (ll i=0;i<N;i++) {
		ispr[i]=0;
		cin >> S[i];
		ans -= S[i];
		maxS = max(maxS,S[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;
	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)) {
			ans += wt;
			fz(a,b);
		}
	}
	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