Submission #1126194

#	Time	Username	Problem	Language	Result	Execution time	Memory
1126194		Haikm13579	Phone Plans (CCO22_day2problem2)	C++17	0 / 25	48 ms	3768 KiB

Main

#include<bits/stdc++.h>
#define ll long long
#define ldb long double
#define fi first
#define se second
#define pir pair<int,int>
using namespace std;
const int maxn = 2e5 + 5;

template <class t1,class t2> inline void maxi(t1 &x,t2 y){if (x < y) x = y;}
template <class t1,class t2> inline void mini(t1 &x,t2 y){if (x > y) x = y;}

struct edge{
	int u = 0,v = 0,w = 0;
	bool operator <(const edge &other) const{
		return (w < other.w);
	}
};

vector <edge> A,B;

void input(int n,int a,int b,ll k){
	while (a--){
		int u,v,w;
		cin >> u >> v >> w;
		A.push_back({u,v,w});
	}
	
	while (b--){
		int u,v,w;
		cin >> u >> v >> w;
		B.push_back({u,v,w});
	}
}

namespace subtask1{
    bool subtask1(int n,int a,int b,ll k){
    	return (n <= 2000);
	}	
	
	const int maxN = 2e3 + 5;
	const ll inf = 1e17;
	
	int cnt[maxN][maxN],par[maxN];
	vector <int> lst[maxN];
	vector <edge> va,vb; 
	
	void init(int n){
		for (int i = 1 ; i <= n ; i++){
			par[i] = i;
			lst[i].clear();
			lst[i].push_back(i);
		}
	}
	
	int findp(int x){
		return (x == par[x]) ? x : par[x] = findp(par[x]);
	}	
	void add(int u,int v,int w,bool state){
		int x = findp(u),y = findp(v);
		if (x != y){
			if (lst[x].size() < lst[y].size()) swap(x,y);
			
			for (int t1 : lst[x])
			   for (int t2 : lst[y]){
			   	   int x1 = min(t1,t2),x2 = max(t1,t2);
			   	   
			   	   if (!state) va.push_back({x1,x2,w});
			   	   if (state) vb.push_back({x1,x2,w});
			}
			
			par[y] = x;
			for (int t2 : lst[y])
			  lst[x].push_back(t2);
		}
	}
		
	void prepare_edge(int n,int a,int b){
		init(n);
		sort(A.begin(),A.end());
		for (edge e : A){
			int u = e.u,v = e.v,w = e.w;
			add(u,v,w,0);
		}
		
		init(n);
		sort(B.begin(),B.end());
		for (edge e : B){
			int u = e.u,v = e.v,w = e.w;
			add(u,v,w,1);
		}
	}
	
	ll lone_case(int n,int a,int b,ll k){
		//only using a
		ll res = inf;
		
		if (va.size() >= k)
		   mini(res,va[k - 1].w);
		
		if (vb.size() >= k)
		   mini(res,vb[k - 1].w);
		
		return res;
	}
	
	ll getsolve(int n,int a,int b,ll k){
		int pointer = 0;
		ll res = inf,cur = 1;
		cnt[vb[0].u][vb[0].v] = 1;
		
		for (edge e : va){
			////empty pointer
			if (pointer < 0) break;
			int u = e.u,v = e.v,w = e.w;
			
			cur += (!cnt[u][v]);
			cnt[u][v]++;
			
			if (cur < k)
				while (pointer < (int)vb.size() - 1 && cur < k){
					pointer++;
					int nu = vb[pointer].u,nv = vb[pointer].v,nw = vb[pointer].w;
					cur += (!cnt[nu][nv]);
					
					cnt[nu][nv]++;
				}
			
			while (pointer >= 0 && cur >= k){
					int nu = vb[pointer].u,nv = vb[pointer].v,nw = vb[pointer].w;
					//new u,v,pointer
					mini(res,(ll)w + (ll)nw);
					
					cnt[nu][nv]--;
					cur -= (!cnt[nu][nv]);
					pointer--;
				}
			}
			
			return res;
	}
	
	ll solve(int n,int a,int b,ll k){
		prepare_edge(n,a,b);
		
		//lone state 
		ll res = lone_case(n,a,b,k);
		
		if (!A.size() || !B.size()){
			if (res >= inf) return -1;
			return res;
		}
		
		mini(res,getsolve(n,a,b,k));
		
		if (res >= inf) return -1;
		return res;
	}
};

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	
	int n,a,b;
	ll k;
	cin >> n >> a >> b >> k;
	input(n,a,b,k);
	
	if (subtask1::subtask1(n,a,b,k)){
		cout << subtask1::solve(n,a,b,k);
		return 0;
	}

	return 0;
}

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