#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int maxN = 505;
struct DSU {
int parent[maxN], sz[maxN];
void reset(){
for(int x=0;x<maxN;x++){
parent[x] = x;
sz[x] = 1;
}
}
int getParent(int x){
if(parent[x] == x) return x;
return parent[x] = getParent(parent[x]);
}
bool merge(int x, int y){
int a = getParent(x);
int b = getParent(y);
if(a != b){
if(sz[a] < sz[b]) swap(a, b);
parent[b] = a;
sz[a] += sz[b];
return true;
}
return false;
}
};
DSU dsu;
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n, m;
cin >> n >> m;
vector<array<ll, 3>> edge;
for(int x=0;x<m;x++){
ll a, b, w;
cin >> a >> b >> w;
a--; b--;
edge.push_back({w, a, b});
}
sort(edge.begin(), edge.end());
vector<ll> v;
for(int x=0;x<m;x++){
v.push_back(edge[x][0]);
for(int y=x+1;y<m;y++){
v.push_back((edge[x][0]+edge[y][0]+1)/2);
}
}
sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end());
vector<ll> ans[v.size()];
int pos = -1;
for(int x=0;x<v.size();x++){
while(pos+1 < m && edge[pos+1][0] <= v[x]){
pos++;
}
dsu.reset();
int cnt = n;
int l = pos, r = pos+1;
while(cnt > 1){
if(l >= 0 && r < edge.size()){
if(v[x]-edge[l][0] <= edge[r][0]-v[x]){
if(dsu.merge(edge[l][1], edge[l][2])){
cnt--;
ans[x].push_back(edge[l][0]);
}
l--;
} else {
if(dsu.merge(edge[r][1], edge[r][2])){
cnt--;
ans[x].push_back(edge[r][0]);
}
r++;
}
} else if(l >= 0){
if(dsu.merge(edge[l][1], edge[l][2])){
cnt--;
ans[x].push_back(edge[l][0]);
}
l--;
} else if(r < edge.size()){
if(dsu.merge(edge[r][1], edge[r][2])){
cnt--;
ans[x].push_back(edge[r][0]);
}
r++;
}
}
}
int q;
cin >> q;
pos = -1;
while(q--){
ll val;
cin >> val;
while(pos+1 < v.size() && v[pos+1] <= val){
pos++;
}
ll mn = 1e18;
if(pos >= 0){
ll cnt = 0;
for(int x=0;x<ans[pos].size();x++){
if(ans[pos][x] <= val){
cnt += val-ans[pos][x];
} else {
cnt += ans[pos][x]-val;
}
}
mn = min(mn, cnt);
}
if(pos+1 < v.size()){
ll cnt = 0;
for(int x=0;x<ans[pos+1].size();x++){
if(ans[pos+1][x] <= val){
cnt += val-ans[pos+1][x];
} else {
cnt += ans[pos+1][x]-val;
}
}
mn = min(mn, cnt);
}
cout << mn << "\n";
}
return 0;
}
Compilation message
reconstruction.cpp: In function 'int main()':
reconstruction.cpp:74:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
74 | for(int x=0;x<v.size();x++){
| ~^~~~~~~~~
reconstruction.cpp:84:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<long long int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
84 | if(l >= 0 && r < edge.size()){
| ~~^~~~~~~~~~~~~
reconstruction.cpp:104:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<long long int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
104 | } else if(r < edge.size()){
| ~~^~~~~~~~~~~~~
reconstruction.cpp:122:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
122 | while(pos+1 < v.size() && v[pos+1] <= val){
| ~~~~~~^~~~~~~~~~
reconstruction.cpp:129:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
129 | for(int x=0;x<ans[pos].size();x++){
| ~^~~~~~~~~~~~~~~~
reconstruction.cpp:138:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
138 | if(pos+1 < v.size()){
| ~~~~~~^~~~~~~~~~
reconstruction.cpp:140:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
140 | for(int x=0;x<ans[pos+1].size();x++){
| ~^~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
324 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
320 KB |
Output is correct |
| 4 |
Correct |
1 ms |
340 KB |
Output is correct |
| 5 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
324 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
320 KB |
Output is correct |
| 4 |
Correct |
1 ms |
340 KB |
Output is correct |
| 5 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
324 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Runtime error |
765 ms |
1048576 KB |
Execution killed with signal 9 |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
324 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
320 KB |
Output is correct |
| 4 |
Correct |
1 ms |
340 KB |
Output is correct |
| 5 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
324 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
320 KB |
Output is correct |
| 4 |
Correct |
1 ms |
340 KB |
Output is correct |
| 5 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
324 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
320 KB |
Output is correct |
| 4 |
Correct |
1 ms |
340 KB |
Output is correct |
| 5 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
