oj.uz

Submission #796269

# Submission time Handle Problem Language Result Execution time Memory
796269 2023-07-28T08:38:22 Z GEN 이지후(#10112) Security Guard (JOI23_guard) C++17
12 / 100
 267 ms 35520 KB 
#include <bits/stdc++.h>
using namespace std;
using lint = long long;
using pi = array<lint, 2>;
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
const int MAXN = 200005;

// case tree:
// root with maximum
// anchor in parent
// using the guard from root, can do everything

struct disj {
	int pa[MAXN], mx[MAXN];
	void init(int n, lint *a) {
		iota(pa, pa + n + 1, 0);
		for (int i = 0; i < n; i++)
			mx[i] = a[i];
	}
	int find(int x) { return pa[x] = (pa[x] == x ? x : find(pa[x])); }
	int query(int x) { return mx[find(x)]; }
	bool uni(int p, int q) {
		p = find(p);
		q = find(q);
		if (p == q)
			return 0;
		pa[q] = p;
		mx[p] = min(mx[p], mx[q]);
		return 1;
	}
} disj;

using node = array<lint, 3>;
priority_queue<pi, vector<pi>, greater<pi>> pq[MAXN];
priority_queue<node, vector<node>, greater<node>> global;

vector<pi> gph[MAXN];
lint a[MAXN];

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n, m, q;
	cin >> n >> m >> q;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	vector<array<int, 3>> edges(m);
	for (auto &[x, s, e] : edges) {
		cin >> s >> e;
		s--;
		e--;
		x = a[s] + a[e];
	}
	sort(all(edges));
	disj.init(n, a);
	for (auto &[x, s, e] : edges) {
		if (disj.uni(s, e)) {
			pq[s].push({x, e});
			pq[e].push({x, s});
		}
	}
	for (int i = 0; i < n; i++) {
		global.push({pq[i].top()[0] - a[i], i, a[i]});
	}
	disj.init(n, a);
	int rt = min_element(a, a + n) - a;
	lint tot = 1ll * a[rt] * (n - 2) + *max_element(a, a + n);
	vector<lint> ans(q + 1, tot);
	for (int i = n - 2; i >= 0; i--) {
		int v = -1;
		while (sz(global)) {
			auto x = global.top();
			global.pop();
			if (disj.query(x[1]) != x[2])
				continue;
			v = disj.find(x[1]);
			while (sz(pq[v]) && disj.find(v) == disj.find(pq[v].top()[1])) {
				pq[v].pop();
			}
			assert(sz(pq[v]));
			if (pq[v].top()[0] - disj.query(v) != x[0])
				continue;
			break;
		}
		assert(v != -1);
		auto tp = pq[v].top();
		assert(disj.find(tp[1]) != disj.find(v));
		pq[v].pop();
		tot += tp[0] - disj.query(v) - a[rt];
		if (i < sz(ans))
			ans[i] = tot;

		int w = tp[1];
		v = disj.find(v);
		w = disj.find(w);
		disj.uni(v, w); // pa[w] = v;
		if (sz(pq[w]) > sz(pq[v])) {
			swap(pq[w], pq[v]);
		}
		while (sz(pq[w])) {
			auto tp = pq[w].top();
			pq[w].pop();
			if (disj.find(tp[1]) == disj.find(v))
				continue;
			pq[v].push(tp);
		}
		if (sz(pq[v]))
			global.push({pq[v].top()[0] - disj.query(v), v, disj.query(v)});
	}
	for (auto &x : ans)
		cout << x << "\n";
}

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 11220 KB Output is correct
2 Correct 102 ms 32340 KB Output is correct
3 Correct 99 ms 32428 KB Output is correct
4 Correct 172 ms 34748 KB Output is correct
5 Correct 189 ms 34808 KB Output is correct
6 Correct 166 ms 34812 KB Output is correct
7 Correct 174 ms 34760 KB Output is correct
8 Correct 5 ms 11220 KB Output is correct

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 11220 KB Output is correct
2 Correct 102 ms 32340 KB Output is correct
3 Correct 99 ms 32428 KB Output is correct
4 Correct 172 ms 34748 KB Output is correct
5 Correct 189 ms 34808 KB Output is correct
6 Correct 166 ms 34812 KB Output is correct
7 Correct 174 ms 34760 KB Output is correct
8 Correct 5 ms 11220 KB Output is correct
9 Correct 6 ms 11220 KB Output is correct
10 Incorrect 267 ms 35520 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 11220 KB Output is correct
2 Correct 102 ms 32340 KB Output is correct
3 Correct 99 ms 32428 KB Output is correct
4 Correct 172 ms 34748 KB Output is correct
5 Correct 189 ms 34808 KB Output is correct
6 Correct 166 ms 34812 KB Output is correct
7 Correct 174 ms 34760 KB Output is correct
8 Correct 5 ms 11220 KB Output is correct
9 Correct 6 ms 11220 KB Output is correct
10 Incorrect 267 ms 35520 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 11220 KB Output is correct
2 Correct 102 ms 32340 KB Output is correct
3 Correct 99 ms 32428 KB Output is correct
4 Correct 172 ms 34748 KB Output is correct
5 Correct 189 ms 34808 KB Output is correct
6 Correct 166 ms 34812 KB Output is correct
7 Correct 174 ms 34760 KB Output is correct
8 Correct 5 ms 11220 KB Output is correct
9 Correct 6 ms 11220 KB Output is correct
10 Incorrect 267 ms 35520 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #5
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 11220 KB Output is correct
2 Correct 5 ms 11220 KB Output is correct
3 Correct 5 ms 11220 KB Output is correct
4 Correct 6 ms 11208 KB Output is correct
5 Correct 5 ms 11220 KB Output is correct
6 Correct 6 ms 11288 KB Output is correct
7 Correct 5 ms 11220 KB Output is correct
8 Correct 18 ms 15060 KB Output is correct
9 Incorrect 18 ms 14988 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #6
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 11220 KB Output is correct
2 Correct 5 ms 11220 KB Output is correct
3 Correct 5 ms 11220 KB Output is correct
4 Correct 6 ms 11208 KB Output is correct
5 Correct 5 ms 11220 KB Output is correct
6 Correct 6 ms 11288 KB Output is correct
7 Correct 5 ms 11220 KB Output is correct
8 Correct 18 ms 15060 KB Output is correct
9 Incorrect 18 ms 14988 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #7
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 11220 KB Output is correct
2 Correct 102 ms 32340 KB Output is correct
3 Correct 99 ms 32428 KB Output is correct
4 Correct 172 ms 34748 KB Output is correct
5 Correct 189 ms 34808 KB Output is correct
6 Correct 166 ms 34812 KB Output is correct
7 Correct 174 ms 34760 KB Output is correct
8 Correct 5 ms 11220 KB Output is correct
9 Correct 6 ms 11220 KB Output is correct
10 Incorrect 267 ms 35520 KB Output isn't correct
11 Halted 0 ms 0 KB -