Submission #693873

#	Time	Username	Problem	Language	Result	Execution time	Memory
693873		pavement	Phone Plans (CCO22_day2problem2)	C++17	25 / 25	2278 ms	161284 KiB

Main

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define int long long
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define ppb pop_back
#define eb emplace_back
#define g0(a) get<0>(a)
#define g1(a) get<1>(a)
#define g2(a) get<2>(a)
#define g3(a) get<3>(a)
#define g4(a) get<4>(a)
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
using db = double;
using ll = long long;
using ld = long double;
using ii = pair<int, int>;
using iii = tuple<int, int, int>;
using iiii = tuple<int, int, int, int>;
template<class key, class value = null_type, class cmp = less<key> >
using ordered_set = tree<key, value, cmp, rb_tree_tag, tree_order_statistics_node_update>;

int n, a, b, k, ans = LLONG_MAX, 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.eb(i, b, a);
		vec[a].pb(i);
	}
	return upds;
}

main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> a >> b >> k;
	if (k == 0) {
		cout << "0\n";
		return 0;
	}
	for (int i = 1; i <= a; i++) {
		cin >> u_a[i] >> v_a[i] >> l_a[i];
		t_a[i] = mt(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] = mt(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 [u, prv, c] : upd_a[i]) {
			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 [u, prv, c] : upd_b[ptr]) {
				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';
}

Compilation message (stderr)

Main.cpp:57:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   57 | main() {
      | ^~~~

• Subtask 1: 6 / 6
• Subtask 2: 5 / 5
• Subtask 3: 6 / 6
• Subtask 4: 8 / 8