#include<bits/stdc++.h>
#define fori(i,a,b) for(int i=a;i<=b;i++)
#define int long long
#define pb push_back
using namespace std;
typedef pair<int,int> ii;
typedef tuple<int,int,int> tp;
const int M = 1e6 + 10;
const int N = 5e2 + 10;
const int mod = 1e9 + 7;
int n, m, q, x[M];
struct node
{
int u, v, w, idx;
node() : u(0), v(0), w(0), idx(0) {}
node(int u,int v,int w,int idx) : u(u), v(v), w(w), idx(idx) {}
bool operator < (const node &rhs) {return w < rhs.w; }
friend ostream& operator << (ostream &os, node rhs) {
return os << "(" << rhs.u << ", " << rhs.v << ", " << rhs.w << ")" << "\n";
}
};
node edge[M];
int id[N];
int finded(int u) {
return id[u] < 0 ? u : id[u] = finded(id[u]);
}
bool unioned(int u,int v)
{
u = finded(u);
v = finded(v);
if(u == v) return false;
if(id[u] > id[v]) swap(u,v);
id[u] += id[v];
id[v] = u;
return true;
}
int par[N], mi[M], num[N], tail[N], cnt;
vector<ii> ke[N];
void dfs(int u,int p)
{
num[u] = ++cnt;
for(ii tmp : ke[u]) {
int v = tmp.first, w = tmp.second;
if(v == p) continue;
//cout << v << " " << u << " " << w << "\n";
par[v] = u;
mi[v] = w;
dfs(v,u);
}
tail[u] = cnt;
}
bool anc(int u,int v)
{
return num[u] <= num[v] && tail[u] >= tail[v];
}
void make_tree(int pre_idx,int cur_idx,vector<int> &pre)
{
if(pre_idx != 0) {
vector<int> cur;
for(int v : pre) if(v != pre_idx) cur.pb(v);
cur.pb(cur_idx);
swap(pre,cur);
}
else pre.pb(cur_idx);
// for(int v : pre) cout << v << " ";
// cout << endl;
cnt = 0;
for(int i = 1;i <= n; i++)
{
ke[i].clear();
num[i] = tail[i] = 0;
}
for(int idx : pre) {
int u = edge[idx].u, v = edge[idx].v;
ke[u].pb({v,idx});
ke[v].pb({u,idx});
}
for(int i = 1;i <= n; i++) {
if(!num[i]) dfs(i,0);
}
}
///
int nxt[M];
int get(int u,int v) {
int res = 0;
while(!anc(u,v)) {
res = max(res, mi[u]);
u = par[u];
}
while(!anc(v,u)) {
res = max(res, mi[v]);
v = par[v];
}
return res;
}
void calculate_nxt()
{
for(int i = 1;i <= m; i++) nxt[i] = -1;
for(int i = 1;i <= n; i++) id[i] = -1;
vector<int> store;
for(int i = m; i != 0; i--) {
if(unioned(edge[i].u,edge[i].v)) {
make_tree(0,i,store);
//cout << i << "\n";
}
else {
nxt[i] = get(edge[i].u,edge[i].v);
//cout << i << " " << nxt[i] << "\n";
make_tree(nxt[i],i,store);
}
}
//for(int i = 1;i <= m; i++) cerr << i << " " << nxt[i] << "\n";
}
vector<int> Q[M];
vector<int> change[M];
vector<int> rrh;
///
void roi_rac_hoa()
{
// rrh
for(int i = 1;i <= m; i++) {
if(nxt[i] != -1) {
rrh.pb((edge[i].w + edge[nxt[i]].w)/2);
}
}
for(int i = 1;i <= q; i++) rrh.pb(x[i]);
sort(rrh.begin(), rrh.end());
rrh.resize(unique(rrh.begin(), rrh.end()) - rrh.begin());
for(int i = 1;i <= m; i++) {
if(nxt[i] != -1) {
int val = (edge[i].w + edge[nxt[i]].w)/2;
val = lower_bound(rrh.begin(), rrh.end(), val) - rrh.begin() + 1;
change[val].pb(i);
}
}
for(int i = 1;i <= q; i++) {
int val = lower_bound(rrh.begin(), rrh.end(), x[i]) - rrh.begin() + 1;
Q[val].pb(i);
}
}
///
//void make_unioned(vector<int> &pre,int val)
//{
// vector<int> cur;
// for(int i = 1;i <= n; i++) id[i] = -1;
// reverse(pre.begin(),pre.end());
// for(int idx : pre) {
// if(unioned(edge[idx].u, edge[idx].v)) {
// cur.pb(idx);
// }
// }
// reverse(cur.begin(),cur.end());
//// if(val == 7) {
//// for(int v : cur) cout << v << " ";
//// }
// swap(pre,cur);
//
//}
bool dd[M];
int ans[M];
void solve()
{
multiset<int> store;
cnt = n;
for(int i = 1;i <= n; i++) id[i] = -1;
for(int i = m;i != 0; i--) {
if(unioned(edge[i].u,edge[i].v)) {
cnt--;
store.insert(i);
}
if(cnt == 1) break;
}
int sz = rrh.size();
for(int i = sz;i != 0; i--) {
sort(change[i].begin(), change[i].end(),greater<int> ());
for(int idx : change[i]) {
// cout << idx << " " << nxt[idx] << "\n";
store.insert(idx);
store.erase(store.find(nxt[idx]));
}
for(int idx : Q[i]) {
for(int v : store) {
ans[idx] += abs(x[idx] - edge[v].w);
//cout << edge[v] ;
}
}
}
}
int32_t main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
if(fopen("1.inp","r")) {
freopen("1.inp","r",stdin);
freopen("1.out","w",stdout);
}
#define task ""
if(fopen(task".inp","r")) {
freopen(task".inp","r",stdin);
freopen(task".out","w",stdout);
}
cin >> n >> m;
for(int i = 1;i <= m; i++) {
cin >> edge[i].u >> edge[i].v >> edge[i].w;
edge[i].idx = i;
}
sort(edge + 1,edge + m + 1);
cin >> q;
for(int i = 1;i <= q; i++) cin >> x[i];
calculate_nxt();
roi_rac_hoa();
solve();
for(int i = 1;i <= q; i++) cout << ans[i] << "\n";
}
Compilation message (stderr)
reconstruction.cpp: In function 'int32_t main()':
reconstruction.cpp:219:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
219 | freopen("1.inp","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~
reconstruction.cpp:220:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
220 | freopen("1.out","w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~
reconstruction.cpp:225:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
225 | freopen(task".inp","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
reconstruction.cpp:226:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
226 | freopen(task".out","w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
# | 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... |