oj.uz

Submission #970816

# Submission time Handle Problem Language Result Execution time Memory
970816 2024-04-27T10:36:47 Z kim Security Guard (JOI23_guard) C++17
100 / 100
 221 ms 27844 KB 
#include<bits/stdc++.h>
using namespace std;
#define eb emplace_back
using ll=long long;
using pii=pair<int,int>;
#define f first
#define s second

using A=tuple<ll,int,int>;
struct cmp{
	bool operator()(const A &l,const A &r)const{
		return get<0>(l) > get<0>(r);
	}
};
 
vector<int> adj[200005];
int a[200005],p[200005],mn[200005];
int fSet(int u){
	if(p[u]==u) return u;
	return p[u]=fSet(p[u]);
}
bool uSet(int u,int v){
	int U=fSet(u), V=fSet(v);
	if(U==V) return 0;
	p[U]=V;
	mn[V]=min(mn[U],mn[V]);
	return 1;
}
 
int main(){
	ios::sync_with_stdio(false); cin.tie(0);
 
	int n,m,Q; cin>>n>>m>>Q;
	int mn=1,mx=1;
	for(int i=1;i<=n;++i){
		cin>>a[i];
		p[i]=i;
		::mn[i]=a[i];
		if(a[i]<a[mn]) mn=i;
		if(a[i]>a[mx]) mx=i;
	}
	vector<pii> edge,edge2;
	for(int i=0;i<m;++i){
		int u,v; cin>>u>>v;
		edge.eb(u,v);
	}
	sort(edge.begin(),edge.end(),[&](const pii &l,const pii &r){
		return a[l.f]+a[l.s]<a[r.f]+a[r.s];
	});
 
	stack<ll> ans;
	ll cur=1LL*a[mn]*(n-1)+a[mx]-a[mn];
	ans.emplace(cur);
	for(auto &[u,v]:edge){
		if(fSet(u)==fSet(v)) continue;
		uSet(u,v);
		edge2.eb(u,v);
	}
	for(int i=1;i<=n;++i) p[i]=i, ::mn[i]=a[i];
	for(auto &[u,v]:edge2){
		if(u==mn||v==mn) uSet(u,v);
	}
	priority_queue<A,vector<A>,cmp> pq;
	for(auto &[u,v]:edge2){
		if(u!=mn&&v!=mn) pq.emplace(a[u]+a[v]-a[mn]-max(::mn[fSet(u)],::mn[fSet(v)]),u,v);
	}
	while(pq.size()){
		auto [w,u,v]=pq.top(); pq.pop();
		int U=fSet(u),V=fSet(v);
		if(U==V) continue;
		if(max(::mn[U],::mn[V])!=a[u]+a[v]-a[mn]-w) pq.emplace(a[u]+a[v]-a[mn]-max(::mn[U],::mn[V]),u,v);
		else{
			cur+=w;
			ans.emplace(cur);
			uSet(u,v);
		}
	}
 
	cout<<cur<<'\n';
	while(Q--){
		if(ans.size()>1) ans.pop();
		cout<<ans.top()<<'\n';
	}
 
	return 0;
}

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7256 KB Output is correct
2 Correct 55 ms 17108 KB Output is correct
3 Correct 57 ms 17616 KB Output is correct
4 Correct 67 ms 17120 KB Output is correct
5 Correct 66 ms 17356 KB Output is correct
6 Correct 67 ms 17824 KB Output is correct
7 Correct 66 ms 18380 KB Output is correct
8 Correct 2 ms 7260 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7256 KB Output is correct
2 Correct 55 ms 17108 KB Output is correct
3 Correct 57 ms 17616 KB Output is correct
4 Correct 67 ms 17120 KB Output is correct
5 Correct 66 ms 17356 KB Output is correct
6 Correct 67 ms 17824 KB Output is correct
7 Correct 66 ms 18380 KB Output is correct
8 Correct 2 ms 7260 KB Output is correct
9 Correct 2 ms 7492 KB Output is correct
10 Correct 115 ms 18676 KB Output is correct
11 Correct 64 ms 18680 KB Output is correct
12 Correct 69 ms 18132 KB Output is correct
13 Correct 69 ms 19216 KB Output is correct
14 Correct 116 ms 17824 KB Output is correct
15 Correct 116 ms 18772 KB Output is correct
16 Correct 116 ms 18340 KB Output is correct
17 Correct 115 ms 17836 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7256 KB Output is correct
2 Correct 55 ms 17108 KB Output is correct
3 Correct 57 ms 17616 KB Output is correct
4 Correct 67 ms 17120 KB Output is correct
5 Correct 66 ms 17356 KB Output is correct
6 Correct 67 ms 17824 KB Output is correct
7 Correct 66 ms 18380 KB Output is correct
8 Correct 2 ms 7260 KB Output is correct
9 Correct 2 ms 7492 KB Output is correct
10 Correct 115 ms 18676 KB Output is correct
11 Correct 64 ms 18680 KB Output is correct
12 Correct 69 ms 18132 KB Output is correct
13 Correct 69 ms 19216 KB Output is correct
14 Correct 116 ms 17824 KB Output is correct
15 Correct 116 ms 18772 KB Output is correct
16 Correct 116 ms 18340 KB Output is correct
17 Correct 115 ms 17836 KB Output is correct
18 Correct 2 ms 7256 KB Output is correct
19 Correct 123 ms 19412 KB Output is correct
20 Correct 128 ms 18468 KB Output is correct
21 Correct 128 ms 18300 KB Output is correct
22 Correct 126 ms 19048 KB Output is correct
23 Correct 118 ms 18124 KB Output is correct
24 Correct 109 ms 17864 KB Output is correct
25 Correct 100 ms 18376 KB Output is correct
26 Correct 95 ms 18636 KB Output is correct
27 Correct 85 ms 17924 KB Output is correct
28 Correct 124 ms 18176 KB Output is correct
29 Correct 116 ms 19412 KB Output is correct
30 Correct 101 ms 18024 KB Output is correct
31 Correct 86 ms 18164 KB Output is correct
32 Correct 129 ms 19744 KB Output is correct
33 Correct 89 ms 17916 KB Output is correct
34 Correct 101 ms 18124 KB Output is correct
35 Correct 95 ms 19052 KB Output is correct
36 Correct 80 ms 18864 KB Output is correct
37 Correct 79 ms 18892 KB Output is correct
38 Correct 95 ms 18892 KB Output is correct
39 Correct 82 ms 19180 KB Output is correct
40 Correct 88 ms 17856 KB Output is correct
41 Correct 90 ms 18440 KB Output is correct
42 Correct 92 ms 17312 KB Output is correct
43 Correct 89 ms 17964 KB Output is correct
44 Correct 125 ms 18124 KB Output is correct
45 Correct 94 ms 18384 KB Output is correct
46 Correct 102 ms 18564 KB Output is correct
47 Correct 105 ms 17812 KB Output is correct
48 Correct 119 ms 17828 KB Output is correct
49 Correct 99 ms 17864 KB Output is correct
50 Correct 129 ms 19336 KB Output is correct
51 Correct 85 ms 17848 KB Output is correct
52 Correct 72 ms 18296 KB Output is correct

Subtask #4
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7256 KB Output is correct
2 Correct 55 ms 17108 KB Output is correct
3 Correct 57 ms 17616 KB Output is correct
4 Correct 67 ms 17120 KB Output is correct
5 Correct 66 ms 17356 KB Output is correct
6 Correct 67 ms 17824 KB Output is correct
7 Correct 66 ms 18380 KB Output is correct
8 Correct 2 ms 7260 KB Output is correct
9 Correct 2 ms 7492 KB Output is correct
10 Correct 115 ms 18676 KB Output is correct
11 Correct 64 ms 18680 KB Output is correct
12 Correct 69 ms 18132 KB Output is correct
13 Correct 69 ms 19216 KB Output is correct
14 Correct 116 ms 17824 KB Output is correct
15 Correct 116 ms 18772 KB Output is correct
16 Correct 116 ms 18340 KB Output is correct
17 Correct 115 ms 17836 KB Output is correct
18 Correct 2 ms 7256 KB Output is correct
19 Correct 123 ms 19412 KB Output is correct
20 Correct 128 ms 18468 KB Output is correct
21 Correct 128 ms 18300 KB Output is correct
22 Correct 126 ms 19048 KB Output is correct
23 Correct 118 ms 18124 KB Output is correct
24 Correct 109 ms 17864 KB Output is correct
25 Correct 100 ms 18376 KB Output is correct
26 Correct 95 ms 18636 KB Output is correct
27 Correct 85 ms 17924 KB Output is correct
28 Correct 124 ms 18176 KB Output is correct
29 Correct 116 ms 19412 KB Output is correct
30 Correct 101 ms 18024 KB Output is correct
31 Correct 86 ms 18164 KB Output is correct
32 Correct 129 ms 19744 KB Output is correct
33 Correct 89 ms 17916 KB Output is correct
34 Correct 101 ms 18124 KB Output is correct
35 Correct 95 ms 19052 KB Output is correct
36 Correct 80 ms 18864 KB Output is correct
37 Correct 79 ms 18892 KB Output is correct
38 Correct 95 ms 18892 KB Output is correct
39 Correct 82 ms 19180 KB Output is correct
40 Correct 88 ms 17856 KB Output is correct
41 Correct 90 ms 18440 KB Output is correct
42 Correct 92 ms 17312 KB Output is correct
43 Correct 89 ms 17964 KB Output is correct
44 Correct 125 ms 18124 KB Output is correct
45 Correct 94 ms 18384 KB Output is correct
46 Correct 102 ms 18564 KB Output is correct
47 Correct 105 ms 17812 KB Output is correct
48 Correct 119 ms 17828 KB Output is correct
49 Correct 99 ms 17864 KB Output is correct
50 Correct 129 ms 19336 KB Output is correct
51 Correct 85 ms 17848 KB Output is correct
52 Correct 72 ms 18296 KB Output is correct
53 Correct 2 ms 7512 KB Output is correct
54 Correct 136 ms 18044 KB Output is correct
55 Correct 131 ms 19152 KB Output is correct
56 Correct 142 ms 23204 KB Output is correct
57 Correct 184 ms 24292 KB Output is correct
58 Correct 176 ms 24256 KB Output is correct
59 Correct 166 ms 24512 KB Output is correct
60 Correct 132 ms 22464 KB Output is correct
61 Correct 157 ms 24336 KB Output is correct
62 Correct 144 ms 23048 KB Output is correct
63 Correct 130 ms 18700 KB Output is correct
64 Correct 142 ms 22308 KB Output is correct
65 Correct 165 ms 25588 KB Output is correct
66 Correct 163 ms 23352 KB Output is correct
67 Correct 195 ms 23284 KB Output is correct
68 Correct 95 ms 17440 KB Output is correct
69 Correct 130 ms 22192 KB Output is correct
70 Correct 111 ms 18644 KB Output is correct
71 Correct 96 ms 18088 KB Output is correct
72 Correct 80 ms 17824 KB Output is correct
73 Correct 100 ms 19280 KB Output is correct
74 Correct 93 ms 18344 KB Output is correct
75 Correct 91 ms 18872 KB Output is correct
76 Correct 92 ms 18564 KB Output is correct
77 Correct 93 ms 18640 KB Output is correct
78 Correct 98 ms 18172 KB Output is correct
79 Correct 185 ms 23196 KB Output is correct
80 Correct 116 ms 19236 KB Output is correct
81 Correct 135 ms 23232 KB Output is correct
82 Correct 156 ms 23228 KB Output is correct
83 Correct 178 ms 24776 KB Output is correct
84 Correct 164 ms 23820 KB Output is correct
85 Correct 124 ms 18148 KB Output is correct
86 Correct 85 ms 18456 KB Output is correct
87 Correct 89 ms 17020 KB Output is correct
88 Correct 207 ms 24600 KB Output is correct

Subtask #5
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7324 KB Output is correct
2 Correct 2 ms 7256 KB Output is correct
3 Correct 2 ms 7328 KB Output is correct
4 Correct 2 ms 7092 KB Output is correct
5 Correct 2 ms 7260 KB Output is correct
6 Correct 2 ms 7260 KB Output is correct
7 Correct 2 ms 7328 KB Output is correct
8 Correct 16 ms 9308 KB Output is correct
9 Correct 14 ms 9304 KB Output is correct
10 Correct 16 ms 9312 KB Output is correct
11 Correct 22 ms 9296 KB Output is correct
12 Correct 14 ms 9308 KB Output is correct
13 Correct 23 ms 9296 KB Output is correct
14 Correct 16 ms 9820 KB Output is correct
15 Correct 14 ms 9308 KB Output is correct
16 Correct 14 ms 9304 KB Output is correct

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7324 KB Output is correct
2 Correct 2 ms 7256 KB Output is correct
3 Correct 2 ms 7328 KB Output is correct
4 Correct 2 ms 7092 KB Output is correct
5 Correct 2 ms 7260 KB Output is correct
6 Correct 2 ms 7260 KB Output is correct
7 Correct 2 ms 7328 KB Output is correct
8 Correct 16 ms 9308 KB Output is correct
9 Correct 14 ms 9304 KB Output is correct
10 Correct 16 ms 9312 KB Output is correct
11 Correct 22 ms 9296 KB Output is correct
12 Correct 14 ms 9308 KB Output is correct
13 Correct 23 ms 9296 KB Output is correct
14 Correct 16 ms 9820 KB Output is correct
15 Correct 14 ms 9308 KB Output is correct
16 Correct 14 ms 9304 KB Output is correct
17 Correct 19 ms 9992 KB Output is correct
18 Correct 20 ms 10208 KB Output is correct
19 Correct 31 ms 10956 KB Output is correct
20 Correct 51 ms 11912 KB Output is correct
21 Correct 59 ms 12488 KB Output is correct
22 Correct 50 ms 11976 KB Output is correct
23 Correct 99 ms 15288 KB Output is correct
24 Correct 63 ms 12740 KB Output is correct
25 Correct 15 ms 9564 KB Output is correct
26 Correct 34 ms 11280 KB Output is correct
27 Correct 22 ms 9940 KB Output is correct
28 Correct 16 ms 9564 KB Output is correct
29 Correct 14 ms 9672 KB Output is correct
30 Correct 15 ms 9564 KB Output is correct
31 Correct 13 ms 8540 KB Output is correct
32 Correct 13 ms 8540 KB Output is correct
33 Correct 16 ms 9868 KB Output is correct
34 Correct 16 ms 9820 KB Output is correct
35 Correct 34 ms 11068 KB Output is correct
36 Correct 96 ms 14784 KB Output is correct

Subtask #7
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7256 KB Output is correct
2 Correct 55 ms 17108 KB Output is correct
3 Correct 57 ms 17616 KB Output is correct
4 Correct 67 ms 17120 KB Output is correct
5 Correct 66 ms 17356 KB Output is correct
6 Correct 67 ms 17824 KB Output is correct
7 Correct 66 ms 18380 KB Output is correct
8 Correct 2 ms 7260 KB Output is correct
9 Correct 2 ms 7492 KB Output is correct
10 Correct 115 ms 18676 KB Output is correct
11 Correct 64 ms 18680 KB Output is correct
12 Correct 69 ms 18132 KB Output is correct
13 Correct 69 ms 19216 KB Output is correct
14 Correct 116 ms 17824 KB Output is correct
15 Correct 116 ms 18772 KB Output is correct
16 Correct 116 ms 18340 KB Output is correct
17 Correct 115 ms 17836 KB Output is correct
18 Correct 2 ms 7256 KB Output is correct
19 Correct 123 ms 19412 KB Output is correct
20 Correct 128 ms 18468 KB Output is correct
21 Correct 128 ms 18300 KB Output is correct
22 Correct 126 ms 19048 KB Output is correct
23 Correct 118 ms 18124 KB Output is correct
24 Correct 109 ms 17864 KB Output is correct
25 Correct 100 ms 18376 KB Output is correct
26 Correct 95 ms 18636 KB Output is correct
27 Correct 85 ms 17924 KB Output is correct
28 Correct 124 ms 18176 KB Output is correct
29 Correct 116 ms 19412 KB Output is correct
30 Correct 101 ms 18024 KB Output is correct
31 Correct 86 ms 18164 KB Output is correct
32 Correct 129 ms 19744 KB Output is correct
33 Correct 89 ms 17916 KB Output is correct
34 Correct 101 ms 18124 KB Output is correct
35 Correct 95 ms 19052 KB Output is correct
36 Correct 80 ms 18864 KB Output is correct
37 Correct 79 ms 18892 KB Output is correct
38 Correct 95 ms 18892 KB Output is correct
39 Correct 82 ms 19180 KB Output is correct
40 Correct 88 ms 17856 KB Output is correct
41 Correct 90 ms 18440 KB Output is correct
42 Correct 92 ms 17312 KB Output is correct
43 Correct 89 ms 17964 KB Output is correct
44 Correct 125 ms 18124 KB Output is correct
45 Correct 94 ms 18384 KB Output is correct
46 Correct 102 ms 18564 KB Output is correct
47 Correct 105 ms 17812 KB Output is correct
48 Correct 119 ms 17828 KB Output is correct
49 Correct 99 ms 17864 KB Output is correct
50 Correct 129 ms 19336 KB Output is correct
51 Correct 85 ms 17848 KB Output is correct
52 Correct 72 ms 18296 KB Output is correct
53 Correct 2 ms 7512 KB Output is correct
54 Correct 136 ms 18044 KB Output is correct
55 Correct 131 ms 19152 KB Output is correct
56 Correct 142 ms 23204 KB Output is correct
57 Correct 184 ms 24292 KB Output is correct
58 Correct 176 ms 24256 KB Output is correct
59 Correct 166 ms 24512 KB Output is correct
60 Correct 132 ms 22464 KB Output is correct
61 Correct 157 ms 24336 KB Output is correct
62 Correct 144 ms 23048 KB Output is correct
63 Correct 130 ms 18700 KB Output is correct
64 Correct 142 ms 22308 KB Output is correct
65 Correct 165 ms 25588 KB Output is correct
66 Correct 163 ms 23352 KB Output is correct
67 Correct 195 ms 23284 KB Output is correct
68 Correct 95 ms 17440 KB Output is correct
69 Correct 130 ms 22192 KB Output is correct
70 Correct 111 ms 18644 KB Output is correct
71 Correct 96 ms 18088 KB Output is correct
72 Correct 80 ms 17824 KB Output is correct
73 Correct 100 ms 19280 KB Output is correct
74 Correct 93 ms 18344 KB Output is correct
75 Correct 91 ms 18872 KB Output is correct
76 Correct 92 ms 18564 KB Output is correct
77 Correct 93 ms 18640 KB Output is correct
78 Correct 98 ms 18172 KB Output is correct
79 Correct 185 ms 23196 KB Output is correct
80 Correct 116 ms 19236 KB Output is correct
81 Correct 135 ms 23232 KB Output is correct
82 Correct 156 ms 23228 KB Output is correct
83 Correct 178 ms 24776 KB Output is correct
84 Correct 164 ms 23820 KB Output is correct
85 Correct 124 ms 18148 KB Output is correct
86 Correct 85 ms 18456 KB Output is correct
87 Correct 89 ms 17020 KB Output is correct
88 Correct 207 ms 24600 KB Output is correct
89 Correct 2 ms 7324 KB Output is correct
90 Correct 2 ms 7256 KB Output is correct
91 Correct 2 ms 7328 KB Output is correct
92 Correct 2 ms 7092 KB Output is correct
93 Correct 2 ms 7260 KB Output is correct
94 Correct 2 ms 7260 KB Output is correct
95 Correct 2 ms 7328 KB Output is correct
96 Correct 16 ms 9308 KB Output is correct
97 Correct 14 ms 9304 KB Output is correct
98 Correct 16 ms 9312 KB Output is correct
99 Correct 22 ms 9296 KB Output is correct
100 Correct 14 ms 9308 KB Output is correct
101 Correct 23 ms 9296 KB Output is correct
102 Correct 16 ms 9820 KB Output is correct
103 Correct 14 ms 9308 KB Output is correct
104 Correct 14 ms 9304 KB Output is correct
105 Correct 19 ms 9992 KB Output is correct
106 Correct 20 ms 10208 KB Output is correct
107 Correct 31 ms 10956 KB Output is correct
108 Correct 51 ms 11912 KB Output is correct
109 Correct 59 ms 12488 KB Output is correct
110 Correct 50 ms 11976 KB Output is correct
111 Correct 99 ms 15288 KB Output is correct
112 Correct 63 ms 12740 KB Output is correct
113 Correct 15 ms 9564 KB Output is correct
114 Correct 34 ms 11280 KB Output is correct
115 Correct 22 ms 9940 KB Output is correct
116 Correct 16 ms 9564 KB Output is correct
117 Correct 14 ms 9672 KB Output is correct
118 Correct 15 ms 9564 KB Output is correct
119 Correct 13 ms 8540 KB Output is correct
120 Correct 13 ms 8540 KB Output is correct
121 Correct 16 ms 9868 KB Output is correct
122 Correct 16 ms 9820 KB Output is correct
123 Correct 34 ms 11068 KB Output is correct
124 Correct 96 ms 14784 KB Output is correct
125 Correct 143 ms 21956 KB Output is correct
126 Correct 140 ms 20924 KB Output is correct
127 Correct 158 ms 21952 KB Output is correct
128 Correct 201 ms 26940 KB Output is correct
129 Correct 167 ms 26524 KB Output is correct
130 Correct 187 ms 26920 KB Output is correct
131 Correct 167 ms 27844 KB Output is correct
132 Correct 168 ms 26304 KB Output is correct
133 Correct 155 ms 25976 KB Output is correct
134 Correct 151 ms 21956 KB Output is correct
135 Correct 143 ms 21760 KB Output is correct
136 Correct 172 ms 27072 KB Output is correct
137 Correct 148 ms 26100 KB Output is correct
138 Correct 192 ms 27588 KB Output is correct
139 Correct 99 ms 19700 KB Output is correct
140 Correct 142 ms 26832 KB Output is correct
141 Correct 124 ms 22264 KB Output is correct
142 Correct 92 ms 20892 KB Output is correct
143 Correct 92 ms 21196 KB Output is correct
144 Correct 108 ms 21184 KB Output is correct
145 Correct 94 ms 20824 KB Output is correct
146 Correct 103 ms 21588 KB Output is correct
147 Correct 104 ms 19648 KB Output is correct
148 Correct 100 ms 20160 KB Output is correct
149 Correct 118 ms 20880 KB Output is correct
150 Correct 189 ms 27804 KB Output is correct
151 Correct 130 ms 22192 KB Output is correct
152 Correct 147 ms 26364 KB Output is correct
153 Correct 161 ms 26304 KB Output is correct
154 Correct 185 ms 26484 KB Output is correct
155 Correct 182 ms 26308 KB Output is correct
156 Correct 136 ms 20784 KB Output is correct
157 Correct 94 ms 21504 KB Output is correct
158 Correct 88 ms 18532 KB Output is correct
159 Correct 221 ms 26072 KB Output is correct