#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());
set<int> st;
vector<int> v;
for(int x=0;x<m;x++){
if(!st.count(edge[x][0])){
v.push_back(edge[x][0]);
st.insert(edge[x][0]);
}
for(int y=x+1;y<m;y++){
if(st.count((edge[x][0]+edge[y][0])/2)) continue;
v.push_back((edge[x][0]+edge[y][0])/2);
st.insert((edge[x][0]+edge[y][0])/2);
}
}
sort(v.begin(), v.end());
assert(v.size() <= 2*m);
vector<int> 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--){
int 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
In file included from /usr/include/c++/10/cassert:44,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
from reconstruction.cpp:1:
reconstruction.cpp: In function 'int main()':
reconstruction.cpp:77:18: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
77 | assert(v.size() <= 2*m);
| ~~~~~~~~~^~~~~~
reconstruction.cpp:82:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
82 | for(int x=0;x<v.size();x++){
| ~^~~~~~~~~
reconstruction.cpp:92: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]
92 | if(l >= 0 && r < edge.size()){
| ~~^~~~~~~~~~~~~
reconstruction.cpp:112: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]
112 | } else if(r < edge.size()){
| ~~^~~~~~~~~~~~~
reconstruction.cpp:130:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
130 | while(pos+1 < v.size() && v[pos+1] <= val){
| ~~~~~~^~~~~~~~~~
reconstruction.cpp:137:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
137 | for(int x=0;x<ans[pos].size();x++){
| ~^~~~~~~~~~~~~~~~
reconstruction.cpp:146:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
146 | if(pos+1 < v.size()){
| ~~~~~~^~~~~~~~~~
reconstruction.cpp:148:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
148 | for(int x=0;x<ans[pos+1].size();x++){
| ~^~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 6 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 6 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 6 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 6 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 6 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 6 |
| 4 |
Halted |
0 ms |
0 KB |
- |
