10331 2024. 03. 31 12:15:43 111 Városok cpp17 Elfogadva 100/100 64ms 22016 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 Összpont Teszt Verdikt Idő Memória
subtask1 0/0
1 Elfogadva 3ms 2104 KiB
2 Elfogadva 3ms 2088 KiB
subtask2 10/10
3 Elfogadva 3ms 2308 KiB
4 Elfogadva 3ms 2532 KiB
5 Elfogadva 3ms 2728 KiB
6 Elfogadva 3ms 2780 KiB
subtask3 5/5
7 Elfogadva 61ms 9216 KiB
8 Elfogadva 10ms 5688 KiB
9 Elfogadva 59ms 10568 KiB
10 Elfogadva 63ms 11956 KiB
11 Elfogadva 61ms 12864 KiB
subtask4 40/40
12 Elfogadva 7ms 8308 KiB
13 Elfogadva 57ms 13456 KiB
14 Elfogadva 57ms 13900 KiB
15 Elfogadva 57ms 14432 KiB
16 Elfogadva 7ms 10060 KiB
17 Elfogadva 59ms 14988 KiB
18 Elfogadva 50ms 14988 KiB
19 Elfogadva 16ms 12380 KiB
20 Elfogadva 37ms 14388 KiB
21 Elfogadva 41ms 12876 KiB
subtask5 45/45
22 Elfogadva 61ms 17172 KiB
23 Elfogadva 59ms 18128 KiB
24 Elfogadva 48ms 18012 KiB
25 Elfogadva 46ms 18872 KiB
26 Elfogadva 59ms 20696 KiB
27 Elfogadva 64ms 22016 KiB