#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define pb push_back
#define ff first
#define ss second
#define ins insert
#define arr3 array<int, 3>
const int inf = 1e9 + 5;
const int N = 5e2;
struct dsu1{
int sz[N + 1], p[N + 1], n;
vector<int> ed;
ll W;
dsu1(int ns){
n = ns;
}
int get(int v){
if (p[v] != v){
p[v] = get(p[v]);
}
return p[v];
}
void unite(int x, int y, int w){
x = get(x); y = get(y);
if (x == y) return;
if (sz[x] > sz[y]) swap(x, y);
p[x] = y;
sz[y] += sz[x];
W += w;
ed.pb(w);
}
void clear(){
for (int i = 1; i <= n; i++){
p[i] = i;
sz[i] = 1;
}
ed.clear();
W = 0;
}
};
struct dsu{
int sz[N + 1], p[N + 1], n;
ll W;
dsu(int ns){
n = ns;
}
int get(int v){
if (p[v] != v){
p[v] = get(p[v]);
}
return p[v];
}
void unite(int x, int y, int w){
x = get(x); y = get(y);
if (x == y) return;
if (sz[x] > sz[y]) swap(x, y);
p[x] = y;
sz[y] += sz[x];
W += w;
}
void clear(){
for (int i = 1; i <= n; i++){
p[i] = i;
sz[i] = 1;
}
W = 0;
}
};
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n, m; cin>>n>>m;
vector<arr3> ed = {{0, 0, 0}};
bool ind = 1;
for (int i = 1; i <= m; i++){
int a, b, w; cin>>a>>b>>w;
if ((b - a) != 1){
ind = 0;
}
ed.pb({a, b, w});
}
ed.pb({0, 0, inf});
if (ind){
vector<int> a;
for (int i = 1; i <= m; i++){
a.pb(ed[i][2]);
}
sort(a.begin(), a.end());
vector<ll> p(m + 1);
for (int i = 0; i < m; i++){
p[i + 1] = p[i] + a[i];
}
vector<int> :: iterator it;
int q; cin>>q;
while (q--){
int x; cin>>x;
it = lower_bound(a.begin(), a.end(), x);
int j = (int) (it - a.begin());
cout<<(1LL * x * j - p[j]) + (p.back() - p[j] - 1LL * x * (m - j))<<"\n";
}
return 0;
}
auto cmp = [&](arr3& x, arr3& y){
return x[2] < y[2];
};
sort(ed.begin(), ed.end(), cmp);
vector<int> actl[m + 2];
dsu1 T1(n);
for (int i = 1; i <= m; i++){
T1.clear();
T1.unite(ed[i][0], ed[i][1], i);
for (int j: actl[i - 1]){
T1.unite(ed[j][0], ed[j][1], j);
}
actl[i] = T1.ed;
}
vector<int> actr[m + 2];
for (int i = m; i > 0; i--){
T1.clear();
T1.unite(ed[i][0], ed[i][1], i);
for (int j: actr[i + 1]){
T1.unite(ed[j][0], ed[j][1], j);
}
actr[i] = T1.ed;
}
int q; cin>>q;
vector<pii> qs;
for (int i = 1; i <= q; i++){
int x; cin>>x;
qs.pb({x, i});
}
sort(qs.begin(), qs.end());
vector<ll> out(q + 1);
int j1 = 0;
dsu T(n);
for (int i = 0; i <= m; i++){
vector<int>& edg1 = actl[i], edg2 = actr[i + 1];
int l = ed[i][2], r = ed[i + 1][2] - 1;
int j2 = j1;
while (j2 < qs.size() && l <= qs[j2].ff && qs[j2].ff <= r){
j2++;
}
while (j1 < j2){
int x = qs[j1].ff;
int i1 = 0, i2 = 0;
T.clear();
while (i1 < edg1.size() || i2 < edg2.size()){
if (i1 == edg1.size()){
int j = edg2[i2];
T.unite(ed[j][0], ed[j][1], abs(ed[j][2] - x));
i2++;
continue;
}
if (i2 == edg2.size()){
int j = edg1[i1];
T.unite(ed[j][0], ed[j][1], abs(ed[j][2] - x));
i1++;
continue;
}
int v1 = abs(ed[edg1[i1]][2] - x);
int v2 = abs(ed[edg2[i2]][2] - x);
if (v1 < v2){
int j = edg1[i1];
T.unite(ed[j][0], ed[j][1], v1);
i1++;
}
else {
int j = edg2[i2];
T.unite(ed[j][0], ed[j][1], v2);
i2++;
}
}
out[qs[j1].ss] = T.W;
j1++;
}
}
for (int i = 1; i <= q; i++) cout<<out[i]<<"\n";
}
Compilation message
reconstruction.cpp: In function 'int main()':
reconstruction.cpp:156:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
156 | while (j2 < qs.size() && l <= qs[j2].ff && qs[j2].ff <= r){
| ~~~^~~~~~~~~~~
reconstruction.cpp:163:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
163 | while (i1 < edg1.size() || i2 < edg2.size()){
| ~~~^~~~~~~~~~~~~
reconstruction.cpp:163:43: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
163 | while (i1 < edg1.size() || i2 < edg2.size()){
| ~~~^~~~~~~~~~~~~
reconstruction.cpp:164:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
164 | if (i1 == edg1.size()){
| ~~~^~~~~~~~~~~~~~
reconstruction.cpp:170:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
170 | if (i2 == edg2.size()){
| ~~~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
