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 int long long
#define pi pair<int, int>
#define pii pair<int, pi>
#define fi first
#define se second
#ifdef _WIN32
#define getchar_unlocked _getchar_nolock
#endif
int n, a, b, k;
int par[200005], sz[200005];
int getr(int x){return (par[x] == x ? x : par[x] = getr(par[x]));}
void merge(int a, int b){
a = getr(a), b = getr(b);
if(a == b)return;
sz[a] += sz[b];
par[b] = a;
}
vector <pi> stuf;
vector <pii> adj, adj2;
int ans = 1e18;
void solve(){
cin >> n >> a >> b >> k;
for(int i=1;i<=a;i++){
int x, y, z; cin >> x >> y >> z;
adj.push_back({z, {x, y}});
}
for(int i=1;i<=b;i++){
int x, y, z; cin >> x >> y >> z;
adj2.push_back({z, {x, y}});
}
sort(adj.begin(), adj.end());
sort(adj2.begin(), adj2.end());
for(int i=1;i<=n;i++)par[i] = i, sz[i] = 1;
int cur = 0;
for(auto i : adj){
int w = i.fi, x = i.se.fi, y = i.se.se;
if(getr(x) == getr(y))continue;
cur += sz[getr(x)] * sz[getr(y)];
merge(x, y);
stuf.push_back({cur, w});
}
cur = 0;
for(int i=1;i<=n;i++)par[i] = i, sz[i] = 1;
for(auto i : adj2){
int w = i.fi, x = i.se.fi, y = i.se.se;
if(getr(x) == getr(y))continue;
cur += sz[getr(x)] * sz[getr(y)];
merge(x, y);
pi bruh = {k - cur, -1};
auto it = lower_bound(stuf.begin(), stuf.end(), bruh);
if(it == stuf.end())continue;
ans = min(ans, (*it).se + w);
}
cout << (ans == (int)1e18 ? -1 : ans);
}
main(){
ios::sync_with_stdio(0);cin.tie(0);
int tc = 1;
//cin >> tc;
for(int tc1=1;tc1<=tc;tc1++){
// cout << "Case #" << tc1 << ": ";
solve();
}
}
Compilation message (stderr)
Main.cpp:62:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
62 | main(){
| ^~~~
# | 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... |