#include <bits/stdc++.h>
#define int ll
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define rng(i,x,n) for(int i=x;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define fi first
#define se second
#define pb push_back
#define sz(a) (int)a.size()
#define vec(...) vector<__VA_ARGS__>
#define _3xxEYjy ios::sync_with_stdio(0),cin.tie(0)
typedef long long ll;
using pii=pair<int,int>;
using vi=vector<int>;
void print(){cout<<'\n';}
template<class h,class...t>
void print(const h&v,const t&...u){cout<<v<<' ',print(u...);}
// e
struct dsu{
int n,cmps;
vector<int> par,siz;
dsu(int m){init(m);}
void init(int m){
n=m;
cmps=m;
par.resize(n,0);
siz.resize(n,0);
for(int i=0;i<n;i++){
par[i]=i;
siz[i]=1;
}
}
void merge(int v,int u){
v=parent(v),u=parent(u);
if(v==u)return;
cmps--;
if(siz[v]<siz[u])swap(v,u);
siz[v]+=siz[u];
par[u]=v;
}
int parent(int v){
return par[v]==v?v:parent(par[v]);
}
bool same(int v, int u){
return parent(v)==parent(u);
}
int size(int v=-1){
return (v==-1?cmps:siz[parent(v)]);
}
};
signed main(){
_3xxEYjy;
int n,m;
cin>>n>>m;
assert(m>1000);
using tpii=pair<int,pii>;
vec(tpii) edges;
rep(i,m){
int u,v,w;
cin>>u>>v>>w;
u-=1,v-=1;
edges.pb({w,{u,v}});
}
sort(edges.begin(),edges.end());
const int inf=1e17;
vec(tpii) evts;
rep(i,m){
dsu uf(n);
int r=inf;
rng(j,i+1,m){
uf.merge(edges[j].se.fi,edges[j].se.se);
if(uf.same(edges[i].se.fi,edges[i].se.se)){
r=edges[j].fi;
break;
}
}
uf.init(n);
int l=-inf;
per(j,i){
uf.merge(edges[j].se.fi,edges[j].se.se);
if(uf.same(edges[i].se.fi,edges[i].se.se)){
l=edges[j].fi;
break;
}
}
evts.pb({(l+edges[i].fi)/2+(l+edges[i].fi)%2,{1,i}});
evts.pb({(r+edges[i].fi)/2+((r+edges[i].fi)%2),{-1,i}});
}
sort(evts.begin(),evts.end());
// for(auto tp:evts){
// print(tp.fi,tp.se.fi,edges[tp.se.se].fi);
// }
int q;
cin>>q;
int i=-1;
set<int> st;
rep(_,q){
int x;
cin>>x;
while(i+1<sz(evts) and evts[i+1].fi<=x){
i+=1;
if(evts[i].se.fi==1){
st.insert(evts[i].se.se);
}else{
st.erase(evts[i].se.se);
}
}
dsu uf(n);
int res=0;
for(auto id:st){
// print(edges[id].fi);
res+=abs(edges[id].fi-x);
}
assert(sz(st)<=n-1);
print(res);
// break;
}
//
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
