oj.uz

Submission #810396

# Submission time Handle Problem Language Result Execution time Memory
810396 2023-08-06T09:08:50 Z qwerasdfzxcl Security Guard (JOI23_guard) C++17
25 / 100
 1733 ms 42080 KB 
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

int n, 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;
		}
	}

	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 refresh(int s){
		s = find(s);
		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});
		} 
	}

	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();
		}

		refresh(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];
}

int main(){
	int n, m, q;
	scanf("%d %d %d", &n, &m, &q);
	for (int i=1;i<=n;i++) scanf("%lld", a+i);
	for (int i=1;i<=m;i++){
		int x, y;
		scanf("%d %d", &x, &y);
		E[i] = {x, y};
	}

	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();

	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()){
			if (!valid(pq.top())){
				int tmp = pq.top()[3];
				pq.pop();
				dsu.refresh(tmp);
			}
			else break;
		}

		assert(!pq.empty());
		auto [cst, _, u, v] = pq.top();

		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);
}

Compilation message

guard.cpp: In function 'int main()':
guard.cpp:79:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   79 |  scanf("%d %d %d", &n, &m, &q);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
guard.cpp:80:30: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   80 |  for (int i=1;i<=n;i++) scanf("%lld", a+i);
      |                         ~~~~~^~~~~~~~~~~~~
guard.cpp:83:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   83 |   scanf("%d %d", &x, &y);
      |   ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6484 KB Output is correct
2 Correct 102 ms 28944 KB Output is correct
3 Correct 95 ms 28912 KB Output is correct
4 Correct 346 ms 40724 KB Output is correct
5 Correct 407 ms 40688 KB Output is correct
6 Correct 385 ms 40616 KB Output is correct
7 Correct 344 ms 40664 KB Output is correct
8 Correct 3 ms 6484 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6484 KB Output is correct
2 Correct 102 ms 28944 KB Output is correct
3 Correct 95 ms 28912 KB Output is correct
4 Correct 346 ms 40724 KB Output is correct
5 Correct 407 ms 40688 KB Output is correct
6 Correct 385 ms 40616 KB Output is correct
7 Correct 344 ms 40664 KB Output is correct
8 Correct 3 ms 6484 KB Output is correct
9 Correct 4 ms 6484 KB Output is correct
10 Correct 1505 ms 42080 KB Output is correct
11 Correct 116 ms 28960 KB Output is correct
12 Correct 89 ms 28984 KB Output is correct
13 Correct 110 ms 28944 KB Output is correct
14 Correct 1560 ms 42028 KB Output is correct
15 Correct 1633 ms 42040 KB Output is correct
16 Correct 1733 ms 42028 KB Output is correct
17 Correct 1533 ms 42012 KB Output is correct

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6484 KB Output is correct
2 Correct 102 ms 28944 KB Output is correct
3 Correct 95 ms 28912 KB Output is correct
4 Correct 346 ms 40724 KB Output is correct
5 Correct 407 ms 40688 KB Output is correct
6 Correct 385 ms 40616 KB Output is correct
7 Correct 344 ms 40664 KB Output is correct
8 Correct 3 ms 6484 KB Output is correct
9 Correct 4 ms 6484 KB Output is correct
10 Correct 1505 ms 42080 KB Output is correct
11 Correct 116 ms 28960 KB Output is correct
12 Correct 89 ms 28984 KB Output is correct
13 Correct 110 ms 28944 KB Output is correct
14 Correct 1560 ms 42028 KB Output is correct
15 Correct 1633 ms 42040 KB Output is correct
16 Correct 1733 ms 42028 KB Output is correct
17 Correct 1533 ms 42012 KB Output is correct
18 Runtime error 8 ms 13140 KB Execution killed with signal 6
19 Halted 0 ms 0 KB -

Subtask #4
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6484 KB Output is correct
2 Correct 102 ms 28944 KB Output is correct
3 Correct 95 ms 28912 KB Output is correct
4 Correct 346 ms 40724 KB Output is correct
5 Correct 407 ms 40688 KB Output is correct
6 Correct 385 ms 40616 KB Output is correct
7 Correct 344 ms 40664 KB Output is correct
8 Correct 3 ms 6484 KB Output is correct
9 Correct 4 ms 6484 KB Output is correct
10 Correct 1505 ms 42080 KB Output is correct
11 Correct 116 ms 28960 KB Output is correct
12 Correct 89 ms 28984 KB Output is correct
13 Correct 110 ms 28944 KB Output is correct
14 Correct 1560 ms 42028 KB Output is correct
15 Correct 1633 ms 42040 KB Output is correct
16 Correct 1733 ms 42028 KB Output is correct
17 Correct 1533 ms 42012 KB Output is correct
18 Runtime error 8 ms 13140 KB Execution killed with signal 6
19 Halted 0 ms 0 KB -

Subtask #5
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6484 KB Output is correct
2 Correct 3 ms 6516 KB Output is correct
3 Correct 3 ms 6484 KB Output is correct
4 Correct 3 ms 6484 KB Output is correct
5 Runtime error 9 ms 13140 KB Execution killed with signal 6
6 Halted 0 ms 0 KB -

Subtask #6
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6484 KB Output is correct
2 Correct 3 ms 6516 KB Output is correct
3 Correct 3 ms 6484 KB Output is correct
4 Correct 3 ms 6484 KB Output is correct
5 Runtime error 9 ms 13140 KB Execution killed with signal 6
6 Halted 0 ms 0 KB -

Subtask #7
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6484 KB Output is correct
2 Correct 102 ms 28944 KB Output is correct
3 Correct 95 ms 28912 KB Output is correct
4 Correct 346 ms 40724 KB Output is correct
5 Correct 407 ms 40688 KB Output is correct
6 Correct 385 ms 40616 KB Output is correct
7 Correct 344 ms 40664 KB Output is correct
8 Correct 3 ms 6484 KB Output is correct
9 Correct 4 ms 6484 KB Output is correct
10 Correct 1505 ms 42080 KB Output is correct
11 Correct 116 ms 28960 KB Output is correct
12 Correct 89 ms 28984 KB Output is correct
13 Correct 110 ms 28944 KB Output is correct
14 Correct 1560 ms 42028 KB Output is correct
15 Correct 1633 ms 42040 KB Output is correct
16 Correct 1733 ms 42028 KB Output is correct
17 Correct 1533 ms 42012 KB Output is correct
18 Runtime error 8 ms 13140 KB Execution killed with signal 6
19 Halted 0 ms 0 KB -