103312024-03-31 12:15:43111Városokcpp17Accepted 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;
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted3ms2104 KiB
2Accepted3ms2088 KiB
subtask210/10
3Accepted3ms2308 KiB
4Accepted3ms2532 KiB
5Accepted3ms2728 KiB
6Accepted3ms2780 KiB
subtask35/5
7Accepted61ms9216 KiB
8Accepted10ms5688 KiB
9Accepted59ms10568 KiB
10Accepted63ms11956 KiB
11Accepted61ms12864 KiB
subtask440/40
12Accepted7ms8308 KiB
13Accepted57ms13456 KiB
14Accepted57ms13900 KiB
15Accepted57ms14432 KiB
16Accepted7ms10060 KiB
17Accepted59ms14988 KiB
18Accepted50ms14988 KiB
19Accepted16ms12380 KiB
20Accepted37ms14388 KiB
21Accepted41ms12876 KiB
subtask545/45
22Accepted61ms17172 KiB
23Accepted59ms18128 KiB
24Accepted48ms18012 KiB
25Accepted46ms18872 KiB
26Accepted59ms20696 KiB
27Accepted64ms22016 KiB