#include<bits/stdc++.h>
using namespace std;
const int nax = 503;
const int bnax = 1e6 + 3;
int n, m;
long long ans[bnax];
vector<tuple<int,int,int>>edges;
struct DSU {
int dad[nax], sz[nax];
void reset() {
for(int i=1; i<nax; ++i) {
dad[i] = i, sz[i] = 1;
}
}
int find(int v) {
return dad[v] = (v==dad[v]) ? v : find(dad[v]);
}
void unite(int u, int v) {
u = find(u), v = find(v);
if(sz[u] < sz[v]) swap(u, v);
dad[v] = u;
sz[u] += sz[v];
}
bool same(int u, int v) {
return find(u) == find(v);
}
} T;
long long MakeTree(int x, long long &cnt1, long long &cnt2) {
long long ret = 0;
sort(edges.begin(), edges.end(), [&] (auto p, auto q) {
auto [w1, u1, v1] = p;
auto [w2, u2, v2] = q;
return abs(x-w1) < abs(x-w2);
});
T.reset();
cnt1 = cnt2 = 0;
for(auto [w, u, v] : edges) {
if(!T.same(u, v)) {
T.unite(u, v);
if(x >= w) ++cnt1;
else ++cnt2;
ret += abs(x-w);
}
}
return ret;
}
void PlayGround() {
cin>>n>>m;
edges.resize(m);
for(auto &[w, u, v] : edges) {
cin>>u>>v>>w;
}
int q;
cin>>q;
while(q--) {
long long z;
int x;
cin>>x;
cout<<MakeTree(x, z, z)<<'\n';
}
// sort(edges.begin(), edges.end());
// set<int>makeTree = {get<0>(edges[0])};
// vector<int>points = {get<0>(edges[0])};
// for(int i=1; i<m; ++i) {
// auto [w1, u1, v1] = edges[i-1];
// auto [w2, u2, v2] = edges[i];
// makeTree.insert((w1+w2+1)/2);
// points.push_back((w1+w2+1)/2);
// points.push_back(w2);
// makeTree.insert(w2);
// }
// int q;
// cin>>q;
// vector<pair<int,int>>qs(q);
// for(int i=0; i<q; ++i) {
// int x;
// cin>>x;
// qs[i] = {x, i};
// points.push_back(x);
// }
// sort(qs.begin(), qs.end());
// sort(points.begin(), points.end());
// points.resize(unique(points.begin(), points.end()) - points.begin());
// int at = 0;
// long long cnt1, cnt2;
// long long cur = 0;
// int prv;
// // cerr<<MakeTree(14, cnt1, cnt2)<<'\n';
// // cerr<<cnt1<<' '<<cnt2<<'\n';
// // exit(0);
// for(int x : points) {
// if(makeTree.count(x)) {
// cur = MakeTree(x, cnt1, cnt2);
// } else {
// cur += cnt1 * (x-prv) - cnt2 * (x-prv);
// }
// auto [z, j] = qs[at];
// if(z==x) {
// ans[j] = cur;
// ++at;
// if(at==q) break;
// }
// prv = x;
// }
// for(int i=0; i<q; ++i) {
// cout<<ans[i]<<'\n';
// }
// cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
PlayGround();
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
328 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
10 |
Correct |
1 ms |
212 KB |
Output is correct |
11 |
Correct |
1 ms |
212 KB |
Output is correct |
12 |
Correct |
1 ms |
212 KB |
Output is correct |
13 |
Correct |
1 ms |
212 KB |
Output is correct |
14 |
Correct |
1 ms |
212 KB |
Output is correct |
15 |
Correct |
1 ms |
212 KB |
Output is correct |
16 |
Correct |
1 ms |
212 KB |
Output is correct |
17 |
Correct |
1 ms |
212 KB |
Output is correct |
18 |
Correct |
1 ms |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
328 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
10 |
Correct |
1 ms |
212 KB |
Output is correct |
11 |
Correct |
1 ms |
212 KB |
Output is correct |
12 |
Correct |
1 ms |
212 KB |
Output is correct |
13 |
Correct |
1 ms |
212 KB |
Output is correct |
14 |
Correct |
1 ms |
212 KB |
Output is correct |
15 |
Correct |
1 ms |
212 KB |
Output is correct |
16 |
Correct |
1 ms |
212 KB |
Output is correct |
17 |
Correct |
1 ms |
212 KB |
Output is correct |
18 |
Correct |
1 ms |
212 KB |
Output is correct |
19 |
Correct |
1 ms |
212 KB |
Output is correct |
20 |
Correct |
80 ms |
3148 KB |
Output is correct |
21 |
Correct |
78 ms |
3152 KB |
Output is correct |
22 |
Correct |
97 ms |
3164 KB |
Output is correct |
23 |
Correct |
81 ms |
3160 KB |
Output is correct |
24 |
Correct |
75 ms |
3156 KB |
Output is correct |
25 |
Correct |
79 ms |
3148 KB |
Output is correct |
26 |
Correct |
95 ms |
3148 KB |
Output is correct |
27 |
Correct |
91 ms |
3160 KB |
Output is correct |
28 |
Correct |
58 ms |
3164 KB |
Output is correct |
29 |
Correct |
58 ms |
3148 KB |
Output is correct |
30 |
Correct |
79 ms |
3164 KB |
Output is correct |
31 |
Correct |
104 ms |
3160 KB |
Output is correct |
32 |
Correct |
84 ms |
3152 KB |
Output is correct |
33 |
Correct |
80 ms |
3164 KB |
Output is correct |
34 |
Correct |
58 ms |
3284 KB |
Output is correct |
35 |
Correct |
65 ms |
3160 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Execution timed out |
5055 ms |
3420 KB |
Time limit exceeded |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
328 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
10 |
Correct |
1 ms |
212 KB |
Output is correct |
11 |
Correct |
1 ms |
212 KB |
Output is correct |
12 |
Correct |
1 ms |
212 KB |
Output is correct |
13 |
Correct |
1 ms |
212 KB |
Output is correct |
14 |
Correct |
1 ms |
212 KB |
Output is correct |
15 |
Correct |
1 ms |
212 KB |
Output is correct |
16 |
Correct |
1 ms |
212 KB |
Output is correct |
17 |
Correct |
1 ms |
212 KB |
Output is correct |
18 |
Correct |
1 ms |
212 KB |
Output is correct |
19 |
Correct |
1 ms |
212 KB |
Output is correct |
20 |
Execution timed out |
5031 ms |
4464 KB |
Time limit exceeded |
21 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
328 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
10 |
Correct |
1 ms |
212 KB |
Output is correct |
11 |
Correct |
1 ms |
212 KB |
Output is correct |
12 |
Correct |
1 ms |
212 KB |
Output is correct |
13 |
Correct |
1 ms |
212 KB |
Output is correct |
14 |
Correct |
1 ms |
212 KB |
Output is correct |
15 |
Correct |
1 ms |
212 KB |
Output is correct |
16 |
Correct |
1 ms |
212 KB |
Output is correct |
17 |
Correct |
1 ms |
212 KB |
Output is correct |
18 |
Correct |
1 ms |
212 KB |
Output is correct |
19 |
Correct |
1 ms |
212 KB |
Output is correct |
20 |
Correct |
80 ms |
3148 KB |
Output is correct |
21 |
Correct |
78 ms |
3152 KB |
Output is correct |
22 |
Correct |
97 ms |
3164 KB |
Output is correct |
23 |
Correct |
81 ms |
3160 KB |
Output is correct |
24 |
Correct |
75 ms |
3156 KB |
Output is correct |
25 |
Correct |
79 ms |
3148 KB |
Output is correct |
26 |
Correct |
95 ms |
3148 KB |
Output is correct |
27 |
Correct |
91 ms |
3160 KB |
Output is correct |
28 |
Correct |
58 ms |
3164 KB |
Output is correct |
29 |
Correct |
58 ms |
3148 KB |
Output is correct |
30 |
Correct |
79 ms |
3164 KB |
Output is correct |
31 |
Correct |
104 ms |
3160 KB |
Output is correct |
32 |
Correct |
84 ms |
3152 KB |
Output is correct |
33 |
Correct |
80 ms |
3164 KB |
Output is correct |
34 |
Correct |
58 ms |
3284 KB |
Output is correct |
35 |
Correct |
65 ms |
3160 KB |
Output is correct |
36 |
Execution timed out |
5036 ms |
3532 KB |
Time limit exceeded |
37 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
328 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
10 |
Correct |
1 ms |
212 KB |
Output is correct |
11 |
Correct |
1 ms |
212 KB |
Output is correct |
12 |
Correct |
1 ms |
212 KB |
Output is correct |
13 |
Correct |
1 ms |
212 KB |
Output is correct |
14 |
Correct |
1 ms |
212 KB |
Output is correct |
15 |
Correct |
1 ms |
212 KB |
Output is correct |
16 |
Correct |
1 ms |
212 KB |
Output is correct |
17 |
Correct |
1 ms |
212 KB |
Output is correct |
18 |
Correct |
1 ms |
212 KB |
Output is correct |
19 |
Correct |
1 ms |
212 KB |
Output is correct |
20 |
Correct |
80 ms |
3148 KB |
Output is correct |
21 |
Correct |
78 ms |
3152 KB |
Output is correct |
22 |
Correct |
97 ms |
3164 KB |
Output is correct |
23 |
Correct |
81 ms |
3160 KB |
Output is correct |
24 |
Correct |
75 ms |
3156 KB |
Output is correct |
25 |
Correct |
79 ms |
3148 KB |
Output is correct |
26 |
Correct |
95 ms |
3148 KB |
Output is correct |
27 |
Correct |
91 ms |
3160 KB |
Output is correct |
28 |
Correct |
58 ms |
3164 KB |
Output is correct |
29 |
Correct |
58 ms |
3148 KB |
Output is correct |
30 |
Correct |
79 ms |
3164 KB |
Output is correct |
31 |
Correct |
104 ms |
3160 KB |
Output is correct |
32 |
Correct |
84 ms |
3152 KB |
Output is correct |
33 |
Correct |
80 ms |
3164 KB |
Output is correct |
34 |
Correct |
58 ms |
3284 KB |
Output is correct |
35 |
Correct |
65 ms |
3160 KB |
Output is correct |
36 |
Correct |
1 ms |
212 KB |
Output is correct |
37 |
Correct |
1 ms |
212 KB |
Output is correct |
38 |
Correct |
1 ms |
212 KB |
Output is correct |
39 |
Execution timed out |
5055 ms |
3420 KB |
Time limit exceeded |
40 |
Halted |
0 ms |
0 KB |
- |