oj.uz

Submission #810400

# Submission time Handle Problem Language Result Execution time Memory
810400 2023-08-06T09:11:44 Z qwerasdfzxcl Security Guard (JOI23_guard) C++17
51 / 100
 354 ms 72612 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, int p = 0){
		s = find(s);
		if (!valid[s]) return;
		
		int flag = p;
		while(!pq2[s].empty() && find(pq2[s].top().second)==s){
			flag = 1;
			pq2[s].pop();
		} 

		if (!flag) return;

		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, 1);

	}
}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:88:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   88 |  scanf("%d %d %d", &n, &m, &q);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
guard.cpp:89:30: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   89 |  for (int i=1;i<=n;i++) scanf("%lld", a+i);
      |                         ~~~~~^~~~~~~~~~~~~
guard.cpp:92:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   92 |   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 96 ms 28904 KB Output is correct
3 Correct 95 ms 28964 KB Output is correct
4 Correct 166 ms 35236 KB Output is correct
5 Correct 170 ms 35144 KB Output is correct
6 Correct 181 ms 35180 KB Output is correct
7 Correct 170 ms 35180 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 96 ms 28904 KB Output is correct
3 Correct 95 ms 28964 KB Output is correct
4 Correct 166 ms 35236 KB Output is correct
5 Correct 170 ms 35144 KB Output is correct
6 Correct 181 ms 35180 KB Output is correct
7 Correct 170 ms 35180 KB Output is correct
8 Correct 3 ms 6484 KB Output is correct
9 Correct 3 ms 6484 KB Output is correct
10 Correct 253 ms 35740 KB Output is correct
11 Correct 98 ms 28904 KB Output is correct
12 Correct 93 ms 28892 KB Output is correct
13 Correct 92 ms 28984 KB Output is correct
14 Correct 254 ms 35784 KB Output is correct
15 Correct 255 ms 35756 KB Output is correct
16 Correct 277 ms 35784 KB Output is correct
17 Correct 243 ms 35712 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 96 ms 28904 KB Output is correct
3 Correct 95 ms 28964 KB Output is correct
4 Correct 166 ms 35236 KB Output is correct
5 Correct 170 ms 35144 KB Output is correct
6 Correct 181 ms 35180 KB Output is correct
7 Correct 170 ms 35180 KB Output is correct
8 Correct 3 ms 6484 KB Output is correct
9 Correct 3 ms 6484 KB Output is correct
10 Correct 253 ms 35740 KB Output is correct
11 Correct 98 ms 28904 KB Output is correct
12 Correct 93 ms 28892 KB Output is correct
13 Correct 92 ms 28984 KB Output is correct
14 Correct 254 ms 35784 KB Output is correct
15 Correct 255 ms 35756 KB Output is correct
16 Correct 277 ms 35784 KB Output is correct
17 Correct 243 ms 35712 KB Output is correct
18 Correct 3 ms 6484 KB Output is correct
19 Correct 321 ms 36120 KB Output is correct
20 Correct 321 ms 36332 KB Output is correct
21 Correct 351 ms 35916 KB Output is correct
22 Correct 322 ms 36020 KB Output is correct
23 Correct 292 ms 34956 KB Output is correct
24 Correct 316 ms 33788 KB Output is correct
25 Correct 206 ms 29952 KB Output is correct
26 Correct 193 ms 28980 KB Output is correct
27 Correct 167 ms 28920 KB Output is correct
28 Correct 333 ms 34392 KB Output is correct
29 Correct 330 ms 33028 KB Output is correct
30 Correct 240 ms 29924 KB Output is correct
31 Correct 143 ms 28984 KB Output is correct
32 Correct 275 ms 35980 KB Output is correct
33 Correct 354 ms 33332 KB Output is correct
34 Correct 313 ms 72612 KB Output is correct
35 Correct 298 ms 68656 KB Output is correct
36 Correct 217 ms 51248 KB Output is correct
37 Correct 209 ms 46892 KB Output is correct
38 Correct 265 ms 30992 KB Output is correct
39 Correct 152 ms 29324 KB Output is correct
40 Correct 227 ms 29680 KB Output is correct
41 Correct 157 ms 30032 KB Output is correct
42 Correct 264 ms 36940 KB Output is correct
43 Runtime error 281 ms 68124 KB Execution killed with signal 6
44 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 96 ms 28904 KB Output is correct
3 Correct 95 ms 28964 KB Output is correct
4 Correct 166 ms 35236 KB Output is correct
5 Correct 170 ms 35144 KB Output is correct
6 Correct 181 ms 35180 KB Output is correct
7 Correct 170 ms 35180 KB Output is correct
8 Correct 3 ms 6484 KB Output is correct
9 Correct 3 ms 6484 KB Output is correct
10 Correct 253 ms 35740 KB Output is correct
11 Correct 98 ms 28904 KB Output is correct
12 Correct 93 ms 28892 KB Output is correct
13 Correct 92 ms 28984 KB Output is correct
14 Correct 254 ms 35784 KB Output is correct
15 Correct 255 ms 35756 KB Output is correct
16 Correct 277 ms 35784 KB Output is correct
17 Correct 243 ms 35712 KB Output is correct
18 Correct 3 ms 6484 KB Output is correct
19 Correct 321 ms 36120 KB Output is correct
20 Correct 321 ms 36332 KB Output is correct
21 Correct 351 ms 35916 KB Output is correct
22 Correct 322 ms 36020 KB Output is correct
23 Correct 292 ms 34956 KB Output is correct
24 Correct 316 ms 33788 KB Output is correct
25 Correct 206 ms 29952 KB Output is correct
26 Correct 193 ms 28980 KB Output is correct
27 Correct 167 ms 28920 KB Output is correct
28 Correct 333 ms 34392 KB Output is correct
29 Correct 330 ms 33028 KB Output is correct
30 Correct 240 ms 29924 KB Output is correct
31 Correct 143 ms 28984 KB Output is correct
32 Correct 275 ms 35980 KB Output is correct
33 Correct 354 ms 33332 KB Output is correct
34 Correct 313 ms 72612 KB Output is correct
35 Correct 298 ms 68656 KB Output is correct
36 Correct 217 ms 51248 KB Output is correct
37 Correct 209 ms 46892 KB Output is correct
38 Correct 265 ms 30992 KB Output is correct
39 Correct 152 ms 29324 KB Output is correct
40 Correct 227 ms 29680 KB Output is correct
41 Correct 157 ms 30032 KB Output is correct
42 Correct 264 ms 36940 KB Output is correct
43 Runtime error 281 ms 68124 KB Execution killed with signal 6
44 Halted 0 ms 0 KB -

Subtask #5
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6576 KB Output is correct
2 Correct 3 ms 6484 KB Output is correct
3 Correct 3 ms 6484 KB Output is correct
4 Correct 4 ms 6484 KB Output is correct
5 Correct 3 ms 6484 KB Output is correct
6 Correct 3 ms 6484 KB Output is correct
7 Correct 3 ms 6484 KB Output is correct
8 Correct 20 ms 8752 KB Output is correct
9 Correct 20 ms 8796 KB Output is correct
10 Correct 20 ms 8532 KB Output is correct
11 Correct 23 ms 8800 KB Output is correct
12 Correct 20 ms 8716 KB Output is correct
13 Correct 20 ms 8792 KB Output is correct
14 Correct 20 ms 8780 KB Output is correct
15 Correct 23 ms 8708 KB Output is correct
16 Correct 20 ms 8716 KB Output is correct

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6576 KB Output is correct
2 Correct 3 ms 6484 KB Output is correct
3 Correct 3 ms 6484 KB Output is correct
4 Correct 4 ms 6484 KB Output is correct
5 Correct 3 ms 6484 KB Output is correct
6 Correct 3 ms 6484 KB Output is correct
7 Correct 3 ms 6484 KB Output is correct
8 Correct 20 ms 8752 KB Output is correct
9 Correct 20 ms 8796 KB Output is correct
10 Correct 20 ms 8532 KB Output is correct
11 Correct 23 ms 8800 KB Output is correct
12 Correct 20 ms 8716 KB Output is correct
13 Correct 20 ms 8792 KB Output is correct
14 Correct 20 ms 8780 KB Output is correct
15 Correct 23 ms 8708 KB Output is correct
16 Correct 20 ms 8716 KB Output is correct
17 Correct 43 ms 12384 KB Output is correct
18 Correct 38 ms 12412 KB Output is correct
19 Correct 64 ms 19108 KB Output is correct
20 Correct 109 ms 29576 KB Output is correct
21 Correct 151 ms 35328 KB Output is correct
22 Correct 105 ms 23172 KB Output is correct
23 Correct 113 ms 34072 KB Output is correct
24 Correct 145 ms 30960 KB Output is correct
25 Correct 23 ms 9300 KB Output is correct
26 Correct 151 ms 35932 KB Output is correct
27 Correct 42 ms 14812 KB Output is correct
28 Correct 22 ms 9300 KB Output is correct
29 Correct 21 ms 9244 KB Output is correct
30 Correct 22 ms 9300 KB Output is correct
31 Correct 20 ms 8020 KB Output is correct
32 Correct 26 ms 8036 KB Output is correct
33 Correct 24 ms 9668 KB Output is correct
34 Correct 25 ms 10288 KB Output is correct
35 Correct 73 ms 21536 KB Output is correct
36 Correct 178 ms 49188 KB Output is correct

Subtask #7
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6484 KB Output is correct
2 Correct 96 ms 28904 KB Output is correct
3 Correct 95 ms 28964 KB Output is correct
4 Correct 166 ms 35236 KB Output is correct
5 Correct 170 ms 35144 KB Output is correct
6 Correct 181 ms 35180 KB Output is correct
7 Correct 170 ms 35180 KB Output is correct
8 Correct 3 ms 6484 KB Output is correct
9 Correct 3 ms 6484 KB Output is correct
10 Correct 253 ms 35740 KB Output is correct
11 Correct 98 ms 28904 KB Output is correct
12 Correct 93 ms 28892 KB Output is correct
13 Correct 92 ms 28984 KB Output is correct
14 Correct 254 ms 35784 KB Output is correct
15 Correct 255 ms 35756 KB Output is correct
16 Correct 277 ms 35784 KB Output is correct
17 Correct 243 ms 35712 KB Output is correct
18 Correct 3 ms 6484 KB Output is correct
19 Correct 321 ms 36120 KB Output is correct
20 Correct 321 ms 36332 KB Output is correct
21 Correct 351 ms 35916 KB Output is correct
22 Correct 322 ms 36020 KB Output is correct
23 Correct 292 ms 34956 KB Output is correct
24 Correct 316 ms 33788 KB Output is correct
25 Correct 206 ms 29952 KB Output is correct
26 Correct 193 ms 28980 KB Output is correct
27 Correct 167 ms 28920 KB Output is correct
28 Correct 333 ms 34392 KB Output is correct
29 Correct 330 ms 33028 KB Output is correct
30 Correct 240 ms 29924 KB Output is correct
31 Correct 143 ms 28984 KB Output is correct
32 Correct 275 ms 35980 KB Output is correct
33 Correct 354 ms 33332 KB Output is correct
34 Correct 313 ms 72612 KB Output is correct
35 Correct 298 ms 68656 KB Output is correct
36 Correct 217 ms 51248 KB Output is correct
37 Correct 209 ms 46892 KB Output is correct
38 Correct 265 ms 30992 KB Output is correct
39 Correct 152 ms 29324 KB Output is correct
40 Correct 227 ms 29680 KB Output is correct
41 Correct 157 ms 30032 KB Output is correct
42 Correct 264 ms 36940 KB Output is correct
43 Runtime error 281 ms 68124 KB Execution killed with signal 6
44 Halted 0 ms 0 KB -