Submission #810433

#	Time	Username	Problem	Language	Result	Execution time	Memory
810433		qwerasdfzxcl	Security Guard (JOI23_guard)	C++17	0 / 100	4061 ms	105304 KiB

guard

#include <bits/stdc++.h>
 
using namespace std;
typedef long long ll;
 
int 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;
			while(!pq2[i].empty()) pq2[i].pop();
		}
	}
 
	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);
		assert(valid[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;
	return p[1] - a[mn] - a[dsu.find(p[3])] == p[0];
}
 
void solve(int n, int m, int q){
	while(!pq.empty()) pq.pop();
 
	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();
 
 	ans[sz] = 0;
	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);
}

mt19937 seed(1557);
uniform_int_distribution<int> rng(0, 2147483647);
int getrand(int l, int r){return rng(seed) % (r-l+1) + l;}

int n, m, q;

void gen(){
	n = getrand(2, 200000);
	m = n-1;
	q = 0;

	for (int i=1;i<=n;i++) a[i] = getrand(1, 1'000'000'000);

	for (int i=1;i<=n-1;i++){
		E[i].first = getrand(1, i);
		E[i].second = i+1;
	}
}

void stress(int tc){
	// printf("------------------------------\n");
	// printf("Stress #%d\n", tc);
	// printf("Input:\n");

	gen();
	// printf("%d %d %d\n", n, m, q);
	// for (int i=1;i<=n;i++) printf("%lld ", a[i]);
	// printf("\n");

	// for (int i=1;i<=m;i++) printf("%d %d\n", E[i].first, E[i].second);

	// printf("Output:\n");
	solve(n, m, q);
}

int main(){
	for (int i=1;;i++) stress(i);
}

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