제출 #1184880

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1184880		UmairAhmadMirza	Phone Plans (CCO22_day2problem2)	C++20	0 / 25	201 ms	36404 KiB

Main

#include <bits/stdc++.h>
using namespace std;

#define int long long
int const N=4e5+5;
int const inf=2e9+7;

int n,a,b,k;

int rep[N];
vector<int> st[N];

signed main(){
	cin>>n>>a>>b>>k;
	for (int i = 0; i <=n; ++i)
	{
		rep[i]=i;
		st[i].push_back(i);
	}
	vector<vector<int>> edg1,edg2;
	for (int i = 0; i < a; ++i)//odd
	{
		int u,v,l;
		cin>>u>>v>>l;
		edg1.push_back({l,u,v});
	}
	for (int i = 0; i < b; ++i)//even
	{
		int u,v,l;
		cin>>u>>v>>l;
		edg2.push_back({l,u,v});
	}
	vector<pair<int,int>> lst1,lst2;
	sort(edg1.begin(), edg1.end());
	sort(edg2.begin(), edg2.end());
	lst1.push_back({0,0});
	lst2.push_back({0,0});
	int tot1=0,tot2=0;
	for (int i = 0; i < a; ++i)
	{
		int u=edg1[i][1],v=edg1[i][2],l=edg1[i][0];
		u=rep[u];
		v=rep[v];
		if(u==v)
			continue;
		if(st[u].size()<st[v].size())
			swap(u,v);
		int c=(st[u].size());
		c*=(st[v].size());
		tot1+=c;
		for(int i:st[v]){
			rep[i]=u;
			st[u].push_back(i);
		}
		st[v].clear();
		lst1.push_back({tot1,l});
	}
	for (int i = 0; i < a; ++i)
	{
		int u=edg2[i][1],v=edg2[i][2],l=edg2[i][0];
		u=rep[u];
		v=rep[v];
		if(u==v)
			continue;
		if(st[u].size()<st[v].size())
			swap(u,v);
		int c=(st[u].size());
		c*=(st[v].size());
		tot2+=c;
		for(int i:st[v]){
			rep[i]=u;
			st[u].push_back(i);
		}
		st[v].clear();
		lst2.push_back({tot2,l});
	}
	int cost=inf;
	int p2=(lst2.size())-1;
	for(auto [nm1,c1]:lst1){
		while(p2>0 && lst2[p2-1].first+nm1>=k){
			p2--;
		}
		if(lst2[p2].first+nm1>=k)
			cost=min(cost,c1+lst2[p2].second);
	}
	if(cost==inf){
		cout<<-1<<endl;
		return 0;
	}
	cout<<cost<<endl;
	return 0;
}

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