#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const int N = 5e5 + 23;
const int sq = 50;
const ll inf = 1e18;
#define F first
#define S second
#define pb push_back
#define sz(x) ((int)x.size())
#define kill(x) cout<< x , exit(0);
#define all(x) x.begin(),x.end()
#define lc (v<<1)
#define rc ((v<<1)|1)
struct DSU {
int par[N];
int s[N];
void clear(int n) {
iota(par,par+n+1,0);
fill(s,s+n+1,1);
}
int getPar(int v) {
return (par[v] == v ? v : par[v] = getPar(par[v]));
}
bool merge(int v,int u) {
v = getPar(v),u = getPar(u);
if(v == u) return false;
if(s[v] > s[u]) swap(v,u);
par[v] = u;
s[u] += s[v];
return true;
}
} ds;
int n,m;
vector<int> comp;
vector<int> edges;
pair<int,pii> E[N];
int cnt[N];
int fnd(int x) {
return upper_bound(all(comp),x) - comp.begin() - 1;
}
int sex = 0;
int mos =0;
ll calc(int W) {
edges.clear();
ds.clear(n);
fill(cnt,cnt+sz(edges) + 1,0);
sex = 0;
mos = 0;
edges.resize(m);
iota(all(edges),0);
sort(all(edges),[&] (int x,int y) { return abs(E[x].F - W) < abs(E[y].F-W);});
ll ans= 0;
for(auto ind: edges) {
auto [w,e] = E[ind];
if(ds.merge(e.F,e.S)) {
ans += abs(w-W);
if(w < W) sex ++;
if(w == W) mos ++;
}
}
return ans;
}
int32_t main() {
cin.tie(nullptr)->sync_with_stdio(false);
cin>>n>>m;
for(int i = 0 ; i < m; i ++) {
int v,u,w; cin>>v>>u>>w;
comp.pb(w);
E[i]= {w,{v,u}};
}
comp.pb(0);
comp.pb(int(1e9 + 9));
int f=sz(comp);
sort(all(comp));
for(int i = 0 ; i+1 < f; i ++) comp.pb((comp[i] + comp[i+1])/2);
sort(all(comp));
comp.resize(unique(all(comp)) - comp.begin());
int q; cin>>q;
int I = 0;
ll val1,val2;
int sex1,sex2,mos1,mos2;
bool change =true;
while(q--) {
int x; cin>>x;
while(I+1 < sz(comp) && comp[I+1] <= x) {
I++;
change = true;
}
if(change) {
val1 = calc(comp[I]);
sex1 = sex;
mos1 = mos;
val2 = calc(comp[I+1]);
sex2 = sex;
mos2 = mos;
}
// chapi
int left= sex1 + mos1, right = (n-1)-sex1-mos1;
ll javab1 = val1;
//cerr<< "! " << javab << ' ' << left << ' ' << comp[I] << '\n';
if(left != 0) javab1 += 1LL*left*(x-comp[I]);
if(right!= 0) javab1 -= 1LL*right*(x-comp[I]);
// rasti
left = sex2, right = (n-1)-sex2;
ll javab2 = val2;
if(left != 0) javab2 -= 1LL*left*(comp[I+1]-x);
if(right!= 0) javab2 += 1LL*right*(comp[I+1]-x);
//cerr<< javab1 << ' ' << javab2 << '\n';
cout<<min(javab1,javab2) << '\n';
change = false;
}
return 0;
}
Compilation message
reconstruction.cpp: In function 'int32_t main()':
reconstruction.cpp:99:21: warning: variable 'mos2' set but not used [-Wunused-but-set-variable]
99 | int sex1,sex2,mos1,mos2;
| ^~~~
reconstruction.cpp:116:26: warning: 'mos1' may be used uninitialized in this function [-Wmaybe-uninitialized]
116 | int left= sex1 + mos1, right = (n-1)-sex1-mos1;
| ^~~~~
reconstruction.cpp:124:31: warning: 'sex2' may be used uninitialized in this function [-Wmaybe-uninitialized]
124 | if(left != 0) javab2 -= 1LL*left*(comp[I+1]-x);
| ^~~~
reconstruction.cpp:116:39: warning: 'sex1' may be used uninitialized in this function [-Wmaybe-uninitialized]
116 | int left= sex1 + mos1, right = (n-1)-sex1-mos1;
| ~~~~~^~~~~
reconstruction.cpp:124:24: warning: 'val2' may be used uninitialized in this function [-Wmaybe-uninitialized]
124 | if(left != 0) javab2 -= 1LL*left*(comp[I+1]-x);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
reconstruction.cpp:119:24: warning: 'val1' may be used uninitialized in this function [-Wmaybe-uninitialized]
119 | if(left != 0) javab1 += 1LL*left*(x-comp[I]);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
6744 KB |
Output is correct |
| 2 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 3 |
Correct |
1 ms |
6488 KB |
Output is correct |
| 4 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 5 |
Incorrect |
1 ms |
6488 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
6744 KB |
Output is correct |
| 2 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 3 |
Correct |
1 ms |
6488 KB |
Output is correct |
| 4 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 5 |
Incorrect |
1 ms |
6488 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 2 |
Correct |
2 ms |
6492 KB |
Output is correct |
| 3 |
Correct |
1 ms |
6488 KB |
Output is correct |
| 4 |
Execution timed out |
5078 ms |
9848 KB |
Time limit exceeded |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
6744 KB |
Output is correct |
| 2 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 3 |
Correct |
1 ms |
6488 KB |
Output is correct |
| 4 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 5 |
Incorrect |
1 ms |
6488 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
6744 KB |
Output is correct |
| 2 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 3 |
Correct |
1 ms |
6488 KB |
Output is correct |
| 4 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 5 |
Incorrect |
1 ms |
6488 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
6744 KB |
Output is correct |
| 2 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 3 |
Correct |
1 ms |
6488 KB |
Output is correct |
| 4 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 5 |
Incorrect |
1 ms |
6488 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
