Submission #693980

#	Time	Username	Problem	Language	Result	Execution time	Memory
693980		penguin133	Phone Plans (CCO22_day2problem2)	C++17	5 / 25	206 ms	25432 KiB

Main

#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;
  if(k == 0){
	cout << 0; return;}
	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;
	stuf.push_back({0, 0});
	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)];
		if(cur >= k)ans = min(ans, w);
		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:66:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   66 | main(){
      | ^~~~

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