Submission #886482

#	Time	Username	Problem	Language	Result	Execution time	Memory
886482		tsumondai	Phone Plans (CCO22_day2problem2)	C++14	25 / 25	1812 ms	161424 KiB

Main

#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 = 1e18, 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 == oo ? -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 (stderr)

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);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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