This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1e18;
void input();
void solve();
int main(){
input();
solve();
}
struct Edge{
int a, b; ll w;
Edge(){}
Edge(int a, int b, ll w): a(a), b(b), w(w){}
bool operator<(const Edge &r)const{
return w<r.w;
}
};
int n, m, q;
Edge edge[100002];
ll queries[1000002];
void input(){
scanf("%d %d", &n, &m);
for(int i=1; i<=m; i++) scanf("%d %d %lld", &edge[i].a, &edge[i].b, &edge[i].w);
sort(edge+1, edge+m+1);
scanf("%d", &q);
for(int i=1; i<=q; i++) scanf("%lld", &queries[i]);
}
struct unionFind{
int par[100002];
void init(int n){
for(int i=1; i<=n; i++) par[i] = i;
}
int find(int x){
if(x == par[x]) return x;
return par[x] = find(par[x]);
}
void merge(int x, int y){
x = find(x), y = find(y);
par[y] = x;
}
} dsu;
bool used[100002], visited[100002];
vector<int> link[100002];
ll ans[100002];
ll L[100002], R[100002];
int getMin(int x, int p, int y, int minV = INT_MAX){
if(x == y) return minV;
for(int nxt: link[x]){
int nxtV = edge[nxt].a ^ edge[nxt].b ^ x;
if(nxtV == p) continue;
int tmp = getMin(nxtV, x, y, min(minV, nxt));
if(tmp != -1) return tmp;
}
return -1;
}
ll down[1000002], downSum[1000002];
ll up[1000002], upSum[1000002];
void solve(){
for(int i=1; i<=m; i++) L[i] = INF, R[i] = -INF;
/// get first mst
dsu.init(n);
for(int i=1; i<=m; i++){
if(dsu.find(edge[i].a) == dsu.find(edge[i].b)) continue;
dsu.merge(edge[i].a, edge[i].b);
link[edge[i].a].push_back(i);
link[edge[i].b].push_back(i);
used[i] = 1;
L[i] = 0;
}
for(int i=1; i<=m; i++){
if(used[i]) continue;
int pnt = getMin(edge[i].a, -1, edge[i].b);
used[pnt] = 0, used[i] = 1;
link[edge[pnt].a].erase(find(link[edge[pnt].a].begin(), link[edge[pnt].a].end(), pnt));
link[edge[pnt].b].erase(find(link[edge[pnt].b].begin(), link[edge[pnt].b].end(), pnt));
link[edge[i].a].push_back(i);
link[edge[i].b].push_back(i);
ll v = (edge[i].w + edge[pnt].w);
R[pnt] = v / 2;
L[i] = v / 2 + 1;
}
for(int i=1; i<=m; i++) if(L[i] != INF && R[i] == -INF) R[i] = INF;
for(int i=1; i<=m; i++){
if(L[i] == INF) continue;
int l = lower_bound(queries+1, queries+q+1, L[i]) - queries;
int m = lower_bound(queries+1, queries+q+1, edge[i].w) - queries;
int r = upper_bound(queries+1, queries+q+1, R[i]) - queries;
down[l]++, downSum[l] += edge[i].w;
down[m]--, downSum[m] -= edge[i].w;
up[m]++, upSum[m] += edge[i].w;
up[r]--, upSum[r] -= edge[i].w;
}
for(int i=1; i<=q; i++){
down[i] += down[i-1], downSum[i] += downSum[i-1];
up[i] += up[i-1], upSum[i] += upSum[i-1];
ans[i] += downSum[i] - down[i] * queries[i];
ans[i] += up[i] * queries[i] - upSum[i];
printf("%lld\n", ans[i]);
}
}
Compilation message (stderr)
reconstruction.cpp: In function 'void input()':
reconstruction.cpp:30:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
30 | scanf("%d %d", &n, &m);
| ~~~~~^~~~~~~~~~~~~~~~~
reconstruction.cpp:31:34: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
31 | for(int i=1; i<=m; i++) scanf("%d %d %lld", &edge[i].a, &edge[i].b, &edge[i].w);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
reconstruction.cpp:33:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
33 | scanf("%d", &q);
| ~~~~~^~~~~~~~~~
reconstruction.cpp:34:34: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
34 | for(int i=1; i<=q; i++) scanf("%lld", &queries[i]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |