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>
#pragma GCC optimize("Ofast,unroll-loops")
using namespace std;
#define pb push_back
#define all(v) v.begin(),v.end()
#define sz(s) (int)s.size()
#define ppb pop_back
#define ll long long
#define pii pair<int,int>
#define F first
#define S second
#define lb lower_bound
#define mem(a,i) memset(a,i,sizeof(a))
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int MAX=1e5+10;
int n,m;
struct DSU{
int f[MAX];
void init(int n){
for(int i=1;i<=n;i++)f[i]=i;
}
int get(int v){
return (f[v]==v?v:f[v]=get(f[v]));
}
void unite(int a,int b){
a=get(a);
b=get(b);
f[a]=b;
}
}D;
struct segtree{
ll t[60*MAX];
int L[60*MAX],R[60*MAX];
int zs;
segtree(){
mem(t,0);
mem(L,0);
mem(R,0);
zs=1;
}
void update(int v,int tl,int tr,int l,int r,int x){
if(l>r||tl>r||l>tr)return;
if(l<=tl&&tr<=r){
t[v]+=x;
return;
}
int tm=(tl+tr)/2;
if(!L[v]){
L[v]=++zs;
}
if(!R[v]){
R[v]=++zs;
}
update(L[v],tl,tm,l,r,x);
update(R[v],tm+1,tr,l,r,x);
}
ll get(int v,int tl,int tr,int pos){
if(tl==tr)return t[v];
int tm=(tl+tr)/2;
if(pos<=tm){
if(L[v])return t[v]+get(L[v],tl,tm,pos);
return t[v];
}
else{
if(R[v])return t[v]+get(R[v],tm+1,tr,pos);
return t[v];
}
}
}T[2];
vector<pair<int,pii>> e;
set<pii> g[510];
int d[510];
void dfs(int v,int p=-1){
for(auto to:g[v]){
if(to.F==p)continue;
d[to.F]=max(d[v],to.S);
dfs(to.F,v);
}
}
void dfs1(int v,int p=-1){
for(auto to:g[v]){
if(to.F==p)continue;
d[to.F]=min(d[v],to.S);
dfs1(to.F,v);
}
}
void solve(){
cin>>n>>m;
for(int i=1;i<=m;i++){
int a,b,c;
cin>>a>>b>>c;
e.pb({c,{a,b}});
}
sort(all(e));
D.init(n);
for(int i=m-1;i>=0;i--){
if(D.get(e[i].S.F)!=D.get(e[i].S.S)){
D.unite(e[i].S.F,e[i].S.S);
g[e[i].S.F].insert({e[i].S.S,i});
g[e[i].S.S].insert({e[i].S.F,i});
// if(e[i].F<=10)cout<<i<<" "<<10-e[i].F<<"\n";
T[0].update(1,0,1e9,e[i].F,1e9,-e[i].F);
T[1].update(1,0,1e9,e[i].F,1e9,1);
}
else{
mem(d,0);
dfs(e[i].S.F);
int edge=d[e[i].S.S];
g[e[edge].S.F].erase({e[edge].S.S,edge});
g[e[edge].S.S].erase({e[edge].S.F,edge});
{
int pos=(e[i].F+e[edge].F)/2;
// if(e[i].F<=10&&10<=pos)cout<<e[i].F<<" "<<e[edge].F<<" "<<pos<<" "<<10-e[i].F<<"\n";
T[0].update(1,0,1e9,e[i].F,pos,-e[i].F);
T[1].update(1,0,1e9,e[i].F,pos,1);
}
g[e[i].S.F].insert({e[i].S.S,i});
g[e[i].S.S].insert({e[i].S.F,i});
}
}
D.init(n);
for(int i=0;i<m;i++){
if(D.get(e[i].S.F)!=D.get(e[i].S.S)){
D.unite(e[i].S.F,e[i].S.S);
g[e[i].S.F].insert({e[i].S.S,i});
g[e[i].S.S].insert({e[i].S.F,i});
T[0].update(1,0,1e9,0,e[i].F,e[i].F);
T[1].update(1,0,1e9,0,e[i].F,-1);
}
else{
for(int i=1;i<=n;i++)d[i]=1e9;
dfs1(e[i].S.F);
int edge=d[e[i].S.S];
g[e[edge].S.F].erase({e[edge].S.S,edge});
g[e[edge].S.S].erase({e[edge].S.F,edge});
{
int pos=(e[edge].F+e[i].F)/2+1;
T[0].update(1,0,1e9,pos,e[i].F,e[i].F);
T[1].update(1,0,1e9,pos,e[i].F,-1);
}
g[e[i].S.F].insert({e[i].S.S,i});
g[e[i].S.S].insert({e[i].S.F,i});
}
}
int q;
cin>>q;
while(q--){
int d;
cin>>d;
cout<<T[0].get(1,0,1e9,d)+T[1].get(1,0,1e9,d)*d<<"\n";
}
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t=1;
// cin>>t;
int init=clock();
while(t--)solve();
#ifdef LOCAL
cout.precision(10);
cout<<fixed<<1.0*(clock()-init)/CLOCKS_PER_SEC<<"\n";
#endif
}
Compilation message (stderr)
reconstruction.cpp: In function 'int main()':
reconstruction.cpp:179:9: warning: unused variable 'init' [-Wunused-variable]
179 | int init=clock();
| ^~~~
# | 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... |