#include <bits/stdc++.h>
using namespace std;
#define Task "problemname"
#define int long long
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define foru(i, l, r) for(int i = l; i <= r; i++)
#define ford(i, r, l) for(int i = r; i >= l; i--)
#define __TIME (1.0 * clock() / CLOCKS_PER_SEC)
typedef pair<int, int> ii;
typedef tuple<int, int, int> iii;
const int N = 4e3 + 5;
const int oo = 1e9, mod = 1e9 + 7;
int n, a, b, k, ans = oo, cur, u_a[200005], v_a[200005], l_a[200005], u_b[200005], v_b[200005], l_b[200005], lnk_a[200005], sz_a[200005], lnk_b[200005], sz_b[200005], pf_a[200005], pf_b[200005], f[200005], s[200005];
iii t_a[200005], t_b[200005];
vector<int> vec_a[200005], vec_b[200005];
vector<iii> upd_a[200005], upd_b[200005];
map<ii, int> freq;
int nc2(int n) {
return n * (n - 1) / 2;
}
int find(int x, int lnk[]) {
if (x == lnk[x]) return x;
return lnk[x] = find(lnk[x], lnk);
}
vector<iii> unite(int a, int b, int lnk[], int sz[], vector<int> vec[]) {
a = find(a, lnk);
b = find(b, lnk);
assert(a != b);
if (sz[b] > sz[a]) swap(a, b);
sz[a] += sz[b];
lnk[b] = a;
vector<iii> upds;
for (int i : vec[b]) {
upds.pb({i, b, a});
vec[a].pb(i);
}
return upds;
}
void process() {
cin >> n >> a >> b >> k;
if (k == 0) {
cout << "0\n";
return;
}
for (int i = 1; i <= a; i++) {
cin >> u_a[i] >> v_a[i] >> l_a[i];
t_a[i] = make_tuple(l_a[i], u_a[i], v_a[i]);
}
sort(t_a + 1, t_a + 1 + a);
for (int i = 1; i <= b; i++) {
cin >> u_b[i] >> v_b[i] >> l_b[i];
t_b[i] = make_tuple(l_b[i], u_b[i], v_b[i]);
}
sort(t_b + 1, t_b + 1 + b);
for (int i = 1; i <= n; i++) {
lnk_a[i] = lnk_b[i] = i;
sz_a[i] = sz_b[i] = 1;
vec_a[i].pb(i);
vec_b[i].pb(i);
}
for (int i = 1; i <= a; i++) {
tie(l_a[i], u_a[i], v_a[i]) = t_a[i];
int x = 0;
if (find(u_a[i], lnk_a) != find(v_a[i], lnk_a)) {
x = sz_a[find(u_a[i], lnk_a)] * sz_a[find(v_a[i], lnk_a)];
upd_a[i] = unite(u_a[i], v_a[i], lnk_a, sz_a, vec_a);
}
pf_a[i] = pf_a[i - 1] + x;
}
for (int i = 1; i <= b; i++) {
tie(l_b[i], u_b[i], v_b[i]) = t_b[i];
int x = 0;
if (find(u_b[i], lnk_b) != find(v_b[i], lnk_b)) {
x = sz_b[find(u_b[i], lnk_b)] * sz_b[find(v_b[i], lnk_b)];
upd_b[i] = unite(u_b[i], v_b[i], lnk_b, sz_b, vec_b);
}
pf_b[i] = pf_b[i - 1] + x;
if (pf_b[i] >= k) {
ans = min(ans, l_b[i]);
}
}
for (int i = 1; i <= n; i++) {
s[i] = find(i, lnk_b);
f[i] = i;
freq[mp(f[i], s[i])]++;
}
for (int i = 1, ptr = b; i <= a; i++) {
// add edge i
for (auto tmp : upd_a[i]) {
int u, prv, c;
tie(u, prv, c)=tmp;
cur -= nc2(freq[mp(f[u], s[u])]);
freq[mp(f[u], s[u])]--;
cur += nc2(freq[mp(f[u], s[u])]);
f[u] = c;
cur -= nc2(freq[mp(f[u], s[u])]);
freq[mp(f[u], s[u])]++;
cur += nc2(freq[mp(f[u], s[u])]);
}
while (pf_a[i] + pf_b[ptr] - cur >= k && ptr >= 1) {
// remove edge ptr
for (auto tmp : upd_b[ptr]) {
int u, prv, c;
tie(u, prv, c)=tmp;
cur -= nc2(freq[mp(f[u], s[u])]);
freq[mp(f[u], s[u])]--;
cur += nc2(freq[mp(f[u], s[u])]);
s[u] = prv;
cur -= nc2(freq[mp(f[u], s[u])]);
freq[mp(f[u], s[u])]++;
cur += nc2(freq[mp(f[u], s[u])]);
}
ptr--;
}
if (pf_a[i] + pf_b[ptr] - cur >= k) {
ans = min(ans, l_a[i]);
} else if (ptr + 1 <= b) {
ans = min(ans, l_a[i] + l_b[ptr + 1]);
}
}
cout << (ans == LLONG_MAX ? -1 : ans) << '\n';
}
signed main() {
cin.tie(0)->sync_with_stdio(false);
if (fopen(Task".INP", "r")) {
freopen(Task".INP", "r", stdin);
freopen(Task".OUT", "w", stdout);
}
process();
cerr << "Time elapsed: " << __TIME << " s.\n";
return 0;
}
// dont stop
Compilation message
Main.cpp: In function 'int main()':
Main.cpp:139:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
139 | freopen(Task".INP", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:140:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
140 | freopen(Task".OUT", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
15 ms |
43612 KB |
Output is correct |
| 2 |
Correct |
4 ms |
21336 KB |
Output is correct |
| 3 |
Incorrect |
6 ms |
31392 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
795 ms |
116212 KB |
Output is correct |
| 2 |
Correct |
521 ms |
97504 KB |
Output is correct |
| 3 |
Correct |
475 ms |
98120 KB |
Output is correct |
| 4 |
Correct |
5 ms |
21080 KB |
Output is correct |
| 5 |
Correct |
4 ms |
21080 KB |
Output is correct |
| 6 |
Incorrect |
7 ms |
31324 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
21084 KB |
Output is correct |
| 2 |
Incorrect |
6 ms |
31324 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
15 ms |
43612 KB |
Output is correct |
| 2 |
Correct |
4 ms |
21336 KB |
Output is correct |
| 3 |
Incorrect |
6 ms |
31392 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
