#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define fi first
#define se second
const int maxN=2e5+5;
const ll inf=2e18;
int n,A,B,k,pa[maxN+1],par[maxN+1];
ll ca[maxN+1],cb[maxN+1];
map<pii,int> mp;
struct canh
{
int u,v;
ll w;
};
struct node
{
int u,pre,cur;
};
vector<node> vec_a[maxN+1],vec_b[maxN+1];
canh a[maxN+1],b[maxN+1];
struct dsu
{
int parent[maxN+1];
ll cnt;
vector<int> vec[maxN+1];
dsu()
{
memset(parent,-1,sizeof(parent));
for(int i=1;i<=n;i++)
{
vec[i].clear();
}
cnt=0;
}
void clr()
{
memset(parent,-1,sizeof(parent));
for(int i=1;i<=n;i++)
{
vec[i].clear();
}
cnt=0;
}
int Find(int v)
{
if(parent[v]<0)
{
return v;
}
return Find(parent[v]);
}
vector<node> Union(int a,int b)
{
a=Find(a);
b=Find(b);
vector<node> vt;
if(a==b)
{
return vt;
}
if(-parent[a]<-parent[b])
{
swap(a,b);
}
cnt+=(parent[a]*parent[b]);
parent[a]+=parent[b];
parent[b]=a;
//cout<<vec[a].size()<<" "<<vec[b].size()<<" ";
for(auto i:vec[b])
{
vec[a].push_back(i);
vt.push_back({i,b,a});
}
return vt;
}
}ds;
int main()
{
//freopen("","r",stdin);
//freopen("","w",stdout);
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n>>A>>B>>k;
for(int i=1;i<=A;i++)
{
cin>>a[i].u>>a[i].v>>a[i].w;
}
sort(a+1,a+A+1,[&](canh x,canh y)
{
return x.w<y.w;
});
for(int i=1;i<=B;i++)
{
cin>>b[i].u>>b[i].v>>b[i].w;
}
sort(b+1,b+B+1,[&](canh x,canh y)
{
return x.w<y.w;
});
ll ans=inf;
for(int i=1;i<=n;i++)
{
ds.vec[i].push_back(i);
}
for(int i=1;i<=A;i++)
{
//cout<<a[i].u<<" "<<a[i].v<<" "<<a[i].w<<'\n';
vec_a[i]=ds.Union(a[i].u,a[i].v);
ca[i]=ds.cnt;
if(ca[i]>=k)
{
ans=min(ans,a[i].w);
}
}
ds.clr();
for(int i=1;i<=n;i++)
{
ds.vec[i].push_back(i);
}
for(int i=1;i<=B;i++)
{
vec_b[i]=ds.Union(b[i].u,b[i].v);
cb[i]=ds.cnt;
if(cb[i]>=k)
{
ans=min(ans,b[i].w);
}
}
for(int i=1;i<=n;i++)
{
pa[i]=i;
par[i]=ds.Find(i);
mp[{pa[i],par[i]}]++;
}
ll ch=0;
for(int i=1,j=B;i<=A;i++)
{
for(auto [u,pre,cur]:vec_a[i])
{
mp[{pa[u],par[u]}]--;
ch-=mp[{pa[u],par[u]}];
pa[u]=cur;
ch+=mp[{pa[u],par[u]}];
mp[{pa[u],par[u]}]++;
}
while(j>1&&ca[i]+cb[j]-ch>=k)
{
for(auto [u,pre,cur]:vec_b[j])
{
mp[{pa[u],par[u]}]--;
ch-=mp[{pa[u],par[u]}];
par[u]=pre;
ch+=mp[{pa[u],par[u]}];
mp[{pa[u],par[u]}]++;
}
j--;
}
if(j!=B)
{
//cout<<i<<" "<<j<<" "<<ch<<'\n';
ans=min(ans,a[i].w+b[j+1].w);
}
}
if(ans==inf)
{
cout<<-1;
}
else cout<<ans;
}
Compilation message
Main.cpp: In function 'int main()':
Main.cpp:142:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
142 | for(auto [u,pre,cur]:vec_a[i])
| ^
Main.cpp:152:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
152 | for(auto [u,pre,cur]:vec_b[j])
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
15196 KB |
Output is correct |
| 2 |
Incorrect |
6 ms |
15196 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
549 ms |
72392 KB |
Output is correct |
| 2 |
Correct |
336 ms |
58056 KB |
Output is correct |
| 3 |
Correct |
323 ms |
58312 KB |
Output is correct |
| 4 |
Incorrect |
6 ms |
15448 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
15192 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
15196 KB |
Output is correct |
| 2 |
Incorrect |
6 ms |
15196 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
