#include <bits/stdc++.h>
using namespace std;
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
const int mxN = (int)1e5 + 5;
vector<pair<int64_t,pair<int,int>>>e;
vector<pair<int64_t,pair<int,int>>>v;
int n,m;
vector<int>parent(mxN);
int UF(int u) {
if(parent[u] == u)
return u;
return parent[u] = UF(parent[u]);
}
int64_t mst(int64_t X) {
for(int i = 0 ; i < m ; i++)
v[i].first = abs(e[i].first - X), v[i].second = e[i].second;
sort(v.begin(),v.end());
int cnt = 0;
int p = 0;
int64_t ans = 0;
vector<bool>vis(n,0);
while(cnt < n-1) {
int A = UF(v[p].second.first),
B = UF(v[p].second.second);
if(A == B) {
p++;
continue;
}
ans += v[p].first;
cnt++;
parent[A] = B;
p++;
}
return ans;
}
void go() {
for(int i = 0 ; i < n ; i++)
parent[i] = i;
}
signed main() {
cin>>n>>m;
for(int i = 0 ; i < m ; i++) {
int64_t a,b,c; cin>>a>>b>>c;
a--,b--;
e.push_back({c,{a,b}});
}
v.resize(m);
int q; cin>>q;
while(q--) {
int64_t X; cin>>X;
go();
cout << mst(X) << "\n";
}
return 0;
}
Compilation message
reconstruction.cpp:5: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
5 | #pragma GCC optimization ("O3")
|
reconstruction.cpp:6: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
6 | #pragma GCC optimization ("unroll-loops")
|
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
596 KB |
Output is correct |
2 |
Correct |
1 ms |
596 KB |
Output is correct |
3 |
Correct |
1 ms |
596 KB |
Output is correct |
4 |
Correct |
1 ms |
596 KB |
Output is correct |
5 |
Correct |
1 ms |
596 KB |
Output is correct |
6 |
Correct |
1 ms |
596 KB |
Output is correct |
7 |
Correct |
1 ms |
596 KB |
Output is correct |
8 |
Correct |
1 ms |
596 KB |
Output is correct |
9 |
Correct |
1 ms |
596 KB |
Output is correct |
10 |
Correct |
1 ms |
596 KB |
Output is correct |
11 |
Correct |
1 ms |
596 KB |
Output is correct |
12 |
Correct |
1 ms |
596 KB |
Output is correct |
13 |
Correct |
1 ms |
596 KB |
Output is correct |
14 |
Correct |
1 ms |
596 KB |
Output is correct |
15 |
Correct |
1 ms |
596 KB |
Output is correct |
16 |
Correct |
1 ms |
596 KB |
Output is correct |
17 |
Correct |
1 ms |
596 KB |
Output is correct |
18 |
Correct |
1 ms |
596 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
596 KB |
Output is correct |
2 |
Correct |
1 ms |
596 KB |
Output is correct |
3 |
Correct |
1 ms |
596 KB |
Output is correct |
4 |
Correct |
1 ms |
596 KB |
Output is correct |
5 |
Correct |
1 ms |
596 KB |
Output is correct |
6 |
Correct |
1 ms |
596 KB |
Output is correct |
7 |
Correct |
1 ms |
596 KB |
Output is correct |
8 |
Correct |
1 ms |
596 KB |
Output is correct |
9 |
Correct |
1 ms |
596 KB |
Output is correct |
10 |
Correct |
1 ms |
596 KB |
Output is correct |
11 |
Correct |
1 ms |
596 KB |
Output is correct |
12 |
Correct |
1 ms |
596 KB |
Output is correct |
13 |
Correct |
1 ms |
596 KB |
Output is correct |
14 |
Correct |
1 ms |
596 KB |
Output is correct |
15 |
Correct |
1 ms |
596 KB |
Output is correct |
16 |
Correct |
1 ms |
596 KB |
Output is correct |
17 |
Correct |
1 ms |
596 KB |
Output is correct |
18 |
Correct |
1 ms |
596 KB |
Output is correct |
19 |
Correct |
1 ms |
596 KB |
Output is correct |
20 |
Correct |
168 ms |
3828 KB |
Output is correct |
21 |
Correct |
181 ms |
3948 KB |
Output is correct |
22 |
Correct |
151 ms |
3944 KB |
Output is correct |
23 |
Correct |
161 ms |
3944 KB |
Output is correct |
24 |
Correct |
159 ms |
3908 KB |
Output is correct |
25 |
Correct |
165 ms |
3992 KB |
Output is correct |
26 |
Correct |
153 ms |
3944 KB |
Output is correct |
27 |
Correct |
157 ms |
3984 KB |
Output is correct |
28 |
Correct |
203 ms |
4032 KB |
Output is correct |
29 |
Correct |
211 ms |
3956 KB |
Output is correct |
30 |
Correct |
153 ms |
3952 KB |
Output is correct |
31 |
Correct |
159 ms |
3868 KB |
Output is correct |
32 |
Correct |
189 ms |
3868 KB |
Output is correct |
33 |
Correct |
184 ms |
3848 KB |
Output is correct |
34 |
Correct |
184 ms |
3860 KB |
Output is correct |
35 |
Correct |
158 ms |
3872 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
596 KB |
Output is correct |
2 |
Correct |
1 ms |
596 KB |
Output is correct |
3 |
Correct |
1 ms |
596 KB |
Output is correct |
4 |
Execution timed out |
5048 ms |
3948 KB |
Time limit exceeded |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
596 KB |
Output is correct |
2 |
Correct |
1 ms |
596 KB |
Output is correct |
3 |
Correct |
1 ms |
596 KB |
Output is correct |
4 |
Correct |
1 ms |
596 KB |
Output is correct |
5 |
Correct |
1 ms |
596 KB |
Output is correct |
6 |
Correct |
1 ms |
596 KB |
Output is correct |
7 |
Correct |
1 ms |
596 KB |
Output is correct |
8 |
Correct |
1 ms |
596 KB |
Output is correct |
9 |
Correct |
1 ms |
596 KB |
Output is correct |
10 |
Correct |
1 ms |
596 KB |
Output is correct |
11 |
Correct |
1 ms |
596 KB |
Output is correct |
12 |
Correct |
1 ms |
596 KB |
Output is correct |
13 |
Correct |
1 ms |
596 KB |
Output is correct |
14 |
Correct |
1 ms |
596 KB |
Output is correct |
15 |
Correct |
1 ms |
596 KB |
Output is correct |
16 |
Correct |
1 ms |
596 KB |
Output is correct |
17 |
Correct |
1 ms |
596 KB |
Output is correct |
18 |
Correct |
1 ms |
596 KB |
Output is correct |
19 |
Correct |
1 ms |
596 KB |
Output is correct |
20 |
Execution timed out |
5045 ms |
2128 KB |
Time limit exceeded |
21 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
596 KB |
Output is correct |
2 |
Correct |
1 ms |
596 KB |
Output is correct |
3 |
Correct |
1 ms |
596 KB |
Output is correct |
4 |
Correct |
1 ms |
596 KB |
Output is correct |
5 |
Correct |
1 ms |
596 KB |
Output is correct |
6 |
Correct |
1 ms |
596 KB |
Output is correct |
7 |
Correct |
1 ms |
596 KB |
Output is correct |
8 |
Correct |
1 ms |
596 KB |
Output is correct |
9 |
Correct |
1 ms |
596 KB |
Output is correct |
10 |
Correct |
1 ms |
596 KB |
Output is correct |
11 |
Correct |
1 ms |
596 KB |
Output is correct |
12 |
Correct |
1 ms |
596 KB |
Output is correct |
13 |
Correct |
1 ms |
596 KB |
Output is correct |
14 |
Correct |
1 ms |
596 KB |
Output is correct |
15 |
Correct |
1 ms |
596 KB |
Output is correct |
16 |
Correct |
1 ms |
596 KB |
Output is correct |
17 |
Correct |
1 ms |
596 KB |
Output is correct |
18 |
Correct |
1 ms |
596 KB |
Output is correct |
19 |
Correct |
1 ms |
596 KB |
Output is correct |
20 |
Correct |
168 ms |
3828 KB |
Output is correct |
21 |
Correct |
181 ms |
3948 KB |
Output is correct |
22 |
Correct |
151 ms |
3944 KB |
Output is correct |
23 |
Correct |
161 ms |
3944 KB |
Output is correct |
24 |
Correct |
159 ms |
3908 KB |
Output is correct |
25 |
Correct |
165 ms |
3992 KB |
Output is correct |
26 |
Correct |
153 ms |
3944 KB |
Output is correct |
27 |
Correct |
157 ms |
3984 KB |
Output is correct |
28 |
Correct |
203 ms |
4032 KB |
Output is correct |
29 |
Correct |
211 ms |
3956 KB |
Output is correct |
30 |
Correct |
153 ms |
3952 KB |
Output is correct |
31 |
Correct |
159 ms |
3868 KB |
Output is correct |
32 |
Correct |
189 ms |
3868 KB |
Output is correct |
33 |
Correct |
184 ms |
3848 KB |
Output is correct |
34 |
Correct |
184 ms |
3860 KB |
Output is correct |
35 |
Correct |
158 ms |
3872 KB |
Output is correct |
36 |
Execution timed out |
5028 ms |
3948 KB |
Time limit exceeded |
37 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
596 KB |
Output is correct |
2 |
Correct |
1 ms |
596 KB |
Output is correct |
3 |
Correct |
1 ms |
596 KB |
Output is correct |
4 |
Correct |
1 ms |
596 KB |
Output is correct |
5 |
Correct |
1 ms |
596 KB |
Output is correct |
6 |
Correct |
1 ms |
596 KB |
Output is correct |
7 |
Correct |
1 ms |
596 KB |
Output is correct |
8 |
Correct |
1 ms |
596 KB |
Output is correct |
9 |
Correct |
1 ms |
596 KB |
Output is correct |
10 |
Correct |
1 ms |
596 KB |
Output is correct |
11 |
Correct |
1 ms |
596 KB |
Output is correct |
12 |
Correct |
1 ms |
596 KB |
Output is correct |
13 |
Correct |
1 ms |
596 KB |
Output is correct |
14 |
Correct |
1 ms |
596 KB |
Output is correct |
15 |
Correct |
1 ms |
596 KB |
Output is correct |
16 |
Correct |
1 ms |
596 KB |
Output is correct |
17 |
Correct |
1 ms |
596 KB |
Output is correct |
18 |
Correct |
1 ms |
596 KB |
Output is correct |
19 |
Correct |
1 ms |
596 KB |
Output is correct |
20 |
Correct |
168 ms |
3828 KB |
Output is correct |
21 |
Correct |
181 ms |
3948 KB |
Output is correct |
22 |
Correct |
151 ms |
3944 KB |
Output is correct |
23 |
Correct |
161 ms |
3944 KB |
Output is correct |
24 |
Correct |
159 ms |
3908 KB |
Output is correct |
25 |
Correct |
165 ms |
3992 KB |
Output is correct |
26 |
Correct |
153 ms |
3944 KB |
Output is correct |
27 |
Correct |
157 ms |
3984 KB |
Output is correct |
28 |
Correct |
203 ms |
4032 KB |
Output is correct |
29 |
Correct |
211 ms |
3956 KB |
Output is correct |
30 |
Correct |
153 ms |
3952 KB |
Output is correct |
31 |
Correct |
159 ms |
3868 KB |
Output is correct |
32 |
Correct |
189 ms |
3868 KB |
Output is correct |
33 |
Correct |
184 ms |
3848 KB |
Output is correct |
34 |
Correct |
184 ms |
3860 KB |
Output is correct |
35 |
Correct |
158 ms |
3872 KB |
Output is correct |
36 |
Correct |
1 ms |
596 KB |
Output is correct |
37 |
Correct |
1 ms |
596 KB |
Output is correct |
38 |
Correct |
1 ms |
596 KB |
Output is correct |
39 |
Execution timed out |
5048 ms |
3948 KB |
Time limit exceeded |
40 |
Halted |
0 ms |
0 KB |
- |