oj.uz

Submission #796224

# Submission time Handle Problem Language Result Execution time Memory
796224 2023-07-28T08:11:42 Z GEN 이지후(#10112) Security Guard (JOI23_guard) C++17
26 / 100
 4000 ms 16720 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;

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);
	vector<array<lint, 3>> combs;
	for (auto &[x, s, e] : edges) {
		if (disj.uni(s, e)) {
			combs.push_back({s, e, x});
		}
	}
	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--) {
		pi foo{lint(1e18), -1};
		for (int j = 0; j < sz(combs); j++) {
			auto [s, e, x] = combs[j];
			lint cost = x - max(disj.query(s), disj.query(e));
			foo = min(foo, pi{cost, j});
		}
		tot += foo[0] - a[rt];
		if (i < sz(ans))
			ans[i] = tot;
		disj.uni(combs[foo[1]][0], combs[foo[1]][1]);
		combs.erase(combs.begin() + foo[1]);
	}
	for (auto &x : ans)
		cout << x << "\n";
}

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Execution timed out 4050 ms 16720 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Execution timed out 4050 ms 16720 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Execution timed out 4050 ms 16720 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Execution timed out 4050 ms 16720 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 2 ms 4948 KB Output is correct
5 Correct 2 ms 4948 KB Output is correct
6 Correct 2 ms 4948 KB Output is correct
7 Correct 2 ms 4948 KB Output is correct
8 Correct 15 ms 8768 KB Output is correct
9 Correct 16 ms 8756 KB Output is correct
10 Correct 19 ms 8532 KB Output is correct
11 Correct 21 ms 8736 KB Output is correct
12 Correct 19 ms 8740 KB Output is correct
13 Correct 15 ms 8716 KB Output is correct
14 Correct 20 ms 8692 KB Output is correct
15 Correct 15 ms 8788 KB Output is correct
16 Correct 16 ms 8800 KB Output is correct

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 2 ms 4948 KB Output is correct
5 Correct 2 ms 4948 KB Output is correct
6 Correct 2 ms 4948 KB Output is correct
7 Correct 2 ms 4948 KB Output is correct
8 Correct 15 ms 8768 KB Output is correct
9 Correct 16 ms 8756 KB Output is correct
10 Correct 19 ms 8532 KB Output is correct
11 Correct 21 ms 8736 KB Output is correct
12 Correct 19 ms 8740 KB Output is correct
13 Correct 15 ms 8716 KB Output is correct
14 Correct 20 ms 8692 KB Output is correct
15 Correct 15 ms 8788 KB Output is correct
16 Correct 16 ms 8800 KB Output is correct
17 Correct 39 ms 9288 KB Output is correct
18 Correct 39 ms 9304 KB Output is correct
19 Correct 51 ms 9992 KB Output is correct
20 Correct 73 ms 11068 KB Output is correct
21 Correct 80 ms 11612 KB Output is correct
22 Correct 84 ms 11088 KB Output is correct
23 Correct 128 ms 13620 KB Output is correct
24 Correct 85 ms 11836 KB Output is correct
25 Correct 34 ms 9032 KB Output is correct
26 Correct 65 ms 10524 KB Output is correct
27 Correct 41 ms 9304 KB Output is correct
28 Correct 36 ms 8948 KB Output is correct
29 Correct 39 ms 9028 KB Output is correct
30 Correct 46 ms 9036 KB Output is correct
31 Correct 30 ms 7760 KB Output is correct
32 Correct 30 ms 7760 KB Output is correct
33 Correct 42 ms 9076 KB Output is correct
34 Correct 35 ms 9120 KB Output is correct
35 Correct 54 ms 10160 KB Output is correct
36 Correct 128 ms 13648 KB Output is correct

Subtask #7
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Execution timed out 4050 ms 16720 KB Time limit exceeded
3 Halted 0 ms 0 KB -