Submission #1131301

#	Time	Username	Problem	Language	Result	Execution time	Memory
1131301		Math4Life2020	Security Guard (JOI23_guard)	C++20	37 / 100	188 ms	23216 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;
	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);
	}
	sort(ord.begin(),ord.end());
	for (pii p1: ord) {
		ll x = p1.second;
		ispr[x]=1;
		for (ll y: adj[x]) {
			if (ispr[y]) {
				//ans += (S[y]+S[x]-mval[gt(y)]);
				ans += (S[y]+S[x]);
				fz(x,y);
			}
		}
	}
	cout << ans << "\n";
}

//sum of mval[gt(y)] is just sum of all non-maximal S??!!?

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