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;
#define ll int
#define pll pair<ll,ll>
#define ff first
#define ss second
#define pb push_back
#define endl "\n"
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
const ll maxn=503;
const ll maxn1=1e5+10;
const ll mod=1e9+7 ;
const ll base=1e9;
/// i believe myself
/// goal 2/7
ll par[maxn];
ll find_par(ll u)
{
if (par[u]<0)
return u;
return par[u]=find_par(par[u]);
}
bool dsu(ll x,ll y)
{
x=find_par(x);
y=find_par(y);
if (x==y)
return false;
if (par[x]>par[y])
swap(x,y);
par[x]+=par[y];
par[y]=x;
return true;
}
vector<pair<ll,pll>> gr[maxn1];
vector<pll> adjq[maxn];
long long res[maxn1*10];
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
if (fopen("t.inp","r"))
{
freopen("test.inp","r",stdin);
freopen("test.out","w",stdout);
}
ll n, m;
cin>> n>> m;
vector<pair<ll,pll>> vt;
vector<ll> vt1;
for (int i=1; i<=m; i++)
{
ll x, y, w;
cin>> x>> y>> w;
vt.pb(make_pair(w,make_pair(x,y)));
vt1.pb(w);
}
sort(vt.begin(),vt.end());
sort(vt1.begin(),vt1.end());
vt1.pb(base);
vt1.resize(unique(vt1.begin(),vt1.end())-vt1.begin());
ll q;
cin>> q;
for (int i=1; i<=q; i++)
{
ll x;
cin>> x;
auto p=lower_bound(vt1.begin(),vt1.end(),x)-vt1.begin();
adjq[p].pb(make_pair(x,i));
}
vector<pair<ll,pll>> vt2;
vector<pair<ll,pll>> vtp;
ll id=0;
for (int i=0; i<vt1.size(); i++)
{
memset(par,-1,sizeof(par));
vtp.clear();
while (id<vt.size()&&vt[id].ff==vt1[i])
{
auto p=vt[id].ss;
if (dsu(p.ff,p.ss))
{
vtp.pb(vt[id]);
}
id++;
}
for (auto to:vt2)
{
if (dsu(to.ss.ff,to.ss.ss))
vtp.pb(to);
}
gr[i]=vtp;
swap(vtp,vt2);
}
vt2.clear();
id=vt.size()-1;
for (int i=vt1.size()-1; i>=0; i--)
{
memset(par,-1,sizeof(par));
vtp.clear();
while (id>=0&&vt[id].ff==vt1[i])
{
auto p=vt[id].ss;
if (dsu(p.ff,p.ss))
{
vtp.pb(vt[id]);
}
id--;
}
for (auto to:vt2)
{
if (dsu(to.ss.ff,to.ss.ss))
vtp.pb(to);
}
for (auto p:adjq[i])
{
memset(par,-1,sizeof(par));
ll idr=0;
ll idl=0;
ll cnt=0;
ll x=p.ff;
ll id=p.ss;
long long ans=0;
while (cnt!=n-1)
{
ll val=base+3;
if (idr<vtp.size()) val=vtp[idr].ff-x;
ll val1=base+3;
if (i&&idl<gr[i-1].size()) val1=x-gr[i-1][idl].ff;
if (val<val1)
{
ll h=dsu(vtp[idr].ss.ff,vtp[idr].ss.ss);
cnt+=h;
ans+=(h*val);
idr++;
}
else
{
ll h=dsu(gr[i-1][idl].ss.ff,gr[i-1][idl].ss.ss);
cnt+=h;
ans+=(h*val1);
idl++;
}
}
res[id]=ans;
}
swap(vtp,vt2);
}
for (int i=1;i<=q;i++) cout <<res[i]<<endl;
}
Compilation message (stderr)
reconstruction.cpp: In function 'int main()':
reconstruction.cpp:81:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
81 | for (int i=0; i<vt1.size(); i++)
| ~^~~~~~~~~~~
reconstruction.cpp:85:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
85 | while (id<vt.size()&&vt[id].ff==vt1[i])
| ~~^~~~~~~~~~
reconstruction.cpp:134:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
134 | if (idr<vtp.size()) val=vtp[idr].ff-x;
| ~~~^~~~~~~~~~~
reconstruction.cpp:136:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
136 | if (i&&idl<gr[i-1].size()) val1=x-gr[i-1][idl].ff;
| ~~~^~~~~~~~~~~~~~~
reconstruction.cpp:51:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
51 | freopen("test.inp","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
reconstruction.cpp:52:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
52 | freopen("test.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... |