103312024-03-31 12:15:43111Városokcpp17Elfogadva 100/10064ms22016 KiB
#include <bits/stdc++.h>
using namespace std;

#define int long long

vector<int> kuhn(vector<vector<int>>& g, int n, int m) {
	vector<int> a(n), b(m, -1);
	auto dfs = [&](auto self, int i) {
		if (a[i]) {
			return 0;
		}
		a[i] = 1;
		for (int j : g[i]) {
			if (b[j] == -1 || self(self, b[j])) {
				b[j] = i;
				return 1;
			}
		}
		return 0;
	};
	for (int i = 0; i < n; i++) {
		fill(a.begin(), a.end(), 0);
		dfs(dfs, i);
	}
	return b;
}

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int N,A,B;
	cin>>N>>A>>B;
	vector<int>x(N),y(N);
	for(int i=0;i<N;i++){
		cin>>x[i]>>y[i];
	}
	vector<int>xx=x,yy=y;
	sort(xx.begin(),xx.end());
	sort(yy.begin(),yy.end());
	xx.erase(unique(xx.begin(),xx.end()),xx.end());
	yy.erase(unique(yy.begin(),yy.end()),yy.end());
	vector<vector<int>>g(xx.size());
	for(int i=0;i<N;i++){
		x[i]=lower_bound(xx.begin(),xx.end(),x[i])-xx.begin();
		y[i]=lower_bound(yy.begin(),yy.end(),y[i])-yy.begin();
		g[x[i]].push_back(y[i]);
	}
	vector<int>b=kuhn(g,xx.size(),yy.size());
	int no=count(b.begin(),b.end(),-1);
	cout<<B*(xx.size()+yy.size())+A*(xx.size()+no)<<'\n';
	return 0;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva3ms2104 KiB
2Elfogadva3ms2088 KiB
subtask210/10
3Elfogadva3ms2308 KiB
4Elfogadva3ms2532 KiB
5Elfogadva3ms2728 KiB
6Elfogadva3ms2780 KiB
subtask35/5
7Elfogadva61ms9216 KiB
8Elfogadva10ms5688 KiB
9Elfogadva59ms10568 KiB
10Elfogadva63ms11956 KiB
11Elfogadva61ms12864 KiB
subtask440/40
12Elfogadva7ms8308 KiB
13Elfogadva57ms13456 KiB
14Elfogadva57ms13900 KiB
15Elfogadva57ms14432 KiB
16Elfogadva7ms10060 KiB
17Elfogadva59ms14988 KiB
18Elfogadva50ms14988 KiB
19Elfogadva16ms12380 KiB
20Elfogadva37ms14388 KiB
21Elfogadva41ms12876 KiB
subtask545/45
22Elfogadva61ms17172 KiB
23Elfogadva59ms18128 KiB
24Elfogadva48ms18012 KiB
25Elfogadva46ms18872 KiB
26Elfogadva59ms20696 KiB
27Elfogadva64ms22016 KiB