Submission #1208058

#	Time	Username	Problem	Language	Result	Execution time	Memory
1208058		PenguinsAreCute	Security Guard (JOI23_guard)	C++17	76 / 100	4083 ms	14660 KiB

guard

#include <bits/stdc++.h>
using namespace std;
struct ufds {
	int n;
	vector<int> par;
	ufds(int _n): n(_n), par(_n,-1) {}
	int onion(int x) {return (par[x]<0?x:par[x]=onion(par[x]));}
	bool unite(int x, int y) {
		x=onion(x), y=onion(y);
		if(x==y)
			return 0;
		if(par[x]<par[y])
			swap(x,y);
		par[y]+=par[x];
		par[x]=y;
		return 1;
	}
};

struct tree {
	vector<int> x, d, w, s;
	int n;
	tree(int _n, vector<int> _s): n(_n), x(_n,0), d(_n,0), w(_n,0), s(_s) {}
	void t(int a, int b) {
		x[a] ^= b;
		x[b] ^= a;
		d[a]++;
		d[b]++;
		w[a] ^= (s[a] + s[b]);
		w[b] ^= (s[a] + s[b]);
	}
	tuple<int,int,int> orz() {
		int ord[n], cnt = 0;
		int k = min_element(s.begin(),s.end())-s.begin();
		d[k] = 0;
		for(int i=0;i<n;i++)
			for(int j=i;d[j]==1;j=x[j]) {
				d[j]--;
				d[x[j]]--;
				x[x[j]] ^= j;
				w[x[j]] ^= w[j];
				ord[cnt++] = j;
			}
		pair<int,int> maxEdge[n];
		memset(maxEdge,-128,sizeof(maxEdge));
		while(cnt--)
			maxEdge[ord[cnt]] = max(maxEdge[x[ord[cnt]]],{w[ord[cnt]],ord[cnt]});
		tuple<int,int,int> bst = {1,0,0};
		for(int i=0;i<n;i++)
			if(i!=k)
				bst = min(bst,{s[i] - maxEdge[i].first, i, maxEdge[i].second});
		get<0>(bst) += *min_element(s.begin(),s.end());
		return bst;
	}
};

int main() {
	int n, m, q;
	cin >> n >> m >> q;
	int d[n];
	vector<int> s(n);
	for(int i=0;i<n;i++)
		cin >> s[i];
	memset(d,0,sizeof(d));

	vector<tuple<int,int,int>> edge;
	for(int i=0;i<m;i++) {
		int a, b;
		cin >> a >> b;
		a--; b--;
		edge.push_back({s[a]+s[b],a,b});
	}

	vector<pair<int,int>> real;
	int small = min_element(s.begin(),s.end())-s.begin();
	long long ans[n];
	memset(ans,1,sizeof(ans));

	ans[0] = 0;
	sort(edge.begin(),edge.end());
	ufds dsu(n);
	for(auto [w, u, v]: edge)
		if(dsu.unite(u,v)) {
			ans[0] += w;
			real.push_back({u,v});
		}

	for(int i=1;i<min(n,q+1);i++) {
		ans[i] = ans[i-1];
		tree tyx(n,s);
		for(auto [y, x]: real)
			tyx.t(y,x);
		auto res = tyx.orz();
		ans[i] += get<0>(res);
		if(ans[i] == ans[i-1]) {
			for(int j=i;j<n;j++)
				ans[j] = ans[i];
			break;
		}
		int a = get<2>(res);
		int b = tyx.x[a];
		auto it = find(real.begin(),real.end(),make_pair(a,b));
		if(it != real.end())
			real.erase(it);
		it = find(real.begin(),real.end(),make_pair(b,a));
		if(it != real.end())
			real.erase(it);
		real.push_back(make_pair(small,get<1>(res)));
	}

	long long delta = 0;
	for(int i=0;i<n;i++)
		delta -= s[i];
	delta += *max_element(s.begin(),s.end());

	for(int i=0;i<=q;i++)
		cout << ans[min(i,n-1)] + delta << "\n";
}

• 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: 0 / 24